[Python] DFS / BFS 정리

🌝BFS : 너비우선탐색

 

가까운 노드부터 탐색하는 알고리즘 

 

선입선출 방식인 큐 자료구조를 이용

 

🌜동작 방식 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

🌜탐색 소요 시간 : O(N) 

 

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        v=queue.popleft()
        print(v,end='')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]
visited = [False] * 9

bfs(graph,1,visited)

---

🌝DFS : 깊이 우선 탐색

 

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

 

특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘

 

🌜스택 자료구조 이용

 

🌜동작과정

1. 탐색 시작 노드를 스택에 삽입하고 방문처리한다.

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

🌻 방문 처리는 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것. 방문처리를 함으로써 각 노드를 한번씩만 처리할 수 있다.

 

def dfs(graph, v, visited):
    #현재 노드를 방문처리
    visited[v] = True
    print(v, end=" ")
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i , visited)
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]
visited = [False] * 9

dfs(graph,1,visited)

 

 

 

---

🌝그래프를 표현하는 2가지 방법

 

🌜인접행렬 ( Adjacency Matrix )

: 2차원 배열로 그래프의 연결 관계를 표현하는 방식

: 메모리가 불필요하게 낭비됨

: 정보를 얻는 속도가 빠르다

 

🌜인접리스트 ( Adjacency List )

: 리스트로 그래프의 연결 관계를 표현하는 방식

: 메모리를 효율적으로 사용 ( 연결된 정보만을 저장 )

: 정보를 얻는 속도 느림 ( 연결된 데이터를 하나씩 확인해야하기 때문 )

 

 

==> 파이썬에서는 단순히 2차원 리스트를 이용하면 된다!

파이썬은 기본 자료형인 리스트 자료형이 append()와 메소드를 제공하기 때문