6. 그래프 탐색 - DFS,BFS

그래프란?

• 객체와 객체 간의 연결 관계 표현
• vertex + edge 로 구성
• 선형 자료구조나 트리 자료구조로 표현하기 힘든 N : N 관계를 가지는 구조를 표현하기에 용이

 

그래프의 종류 

무향 그래프(Undirected Graph)
유향 그래프 (Directed Graph)
가중치 그래프 (Weighted Graph)

 

그래프를 표현하는 방법

인접행렬 : 두 정점을 연결하는 간선의 유무를 행렬로 표현

단점 - 정점의 개수가 커지면 인접 행렬에 필요한 메모리 크기는 n^2에 비례해서 커짐

 

인접 리스트 : 각 정점마다 인접 정점으로 나가는 간선의 정보 저장

• 하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결 리스트로 저장
• 파이썬에서는 dictionary를 사용!
• key 값이 하나의 vertex가 되고, 해당하는 value에는 인접한 vetex들을 set으로 저장

---

가중치가 없는 그래프는 DFS, BFS를 통해 문제를 해결한다.

 

DFS (깊이 우선 탐색)

• 스택 이용

# graph : 그래프, S : 스택, V : 시작정점
# visited : 정점의 방문 정보 표시, False로 초기화

visited = [False]*(N+1)
S = [V]

while S:
    vertex = S.pop()
    if visited[vertex] == False:
        visited[vertex] = True
        print(vertex, end=' ')
        for neighbor in graph[vertex]:
            S.append(neighbor)

 

• 재귀호출 이용

# G : 그래프, v : 시작정점
# visited : 정점의 방문 정보 표시, False로 초기화
# G[v] : 그래프에 G에서 v의 인접 정점 리스트

def DFS(G, v):
    visited[v] = True
    visit(v)
    
    for w in G[v]:
        if not visited[w]:
            DFS(G, w)

 

시간 복잡도 : for loop을 vertex 개수만큼 반복하기 때문에 O(v) + 방문할 때마다 연결된 간선을 방문하므로 O(e)

=> O(v+e)

근데 인접행렬로 표현하면, O(v^2)

 

 

BFS (너비 우선 탐색)

• 큐 이용 

# graph : 그래프, S : 스택, V : 시작정점
# visited : 정점의 방문 정보 표시, False로 초기화

visited = [False]*(N+1)
S = collections.deque()
S.append(V)

while S:
    vertex = S.popleft()
    if visited[vertex] == False:
        visited[vertex] = True
        print(vertex, end=' ')
        for neighbor in sorted(graph[vertex]):
            S.append(neighbor)

시간 복잡도 : for loop을 vertex 개수만큼 반복하기 때문에 O(v) + 방문할 때마다 연결된 간선을 방문하므로 O(e)

=> O(v+e)

근데 인접행렬로 표현하면, O(v^2)

 

 

결국, DFS와 BFS의 시간복잡도는 동일하다. 탐색이 끝났을 때를 생각해보면 vertex와 edge는 각각 한 번 씩 방문됨을 알 수 있다.