알고리즘) 그래프와 BFS, DFS

그래프는 실제 세계의 현상이나 사물을 정점(Vertex 또는 Node)와 간선(Edge 또는 Link, branch)으로 표현하는 것입니다. 

그래프의 구성요소는 다음과 같아요

- 정점 : vertex : 위치, 정점, 노드

- 간선 : 노드들간의 관계를 나타내는 선

- 인접 정점 : Adjacent Vertex : 간선으로 이어진 정점

- 정점 차수 : Degree : 무방향 그래프에서 하나의 정점으로 인접한 정점의 수

- 진입 차수 : In-Degree : 외부 정점에서 들어오는 간선 수

- 진출 차수 : Out - Degree :외부 정점으로 나가는 간선의 수

- 경로 길이 : Path Length : 경로를 구성하기 위해 사용된 간선의 수

- 단순 경로 : Simple Path : 처음 정점과 마지막 정점을 제외하고 중복 정점이 없는 경로

- 사이클 : 단순경로의 시작 정점과 종료 정저이 동일한 경우

 

그래프는 여러 특성의 조합으로 종류가 다양합니다.

방향이 없는 무방향 그래프, 방향이 있는 방향 그래프, 간선이나 노드의 가중치가 다른 가중치 그래프, 모든 정점이 연결된 연결 그래프, 그렇지 않은 비연결 그래프, 사이클이 존재하는 사이클 그래프, 사이클이 없는 비순환 그래프, 모든 노드끼리 서로서로 다 연결된 완전 그래프...

파이썬에서는 딕셔너리와 리스트로 그래프를 표현할 수 있습니다. 

graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

이런 그래프를 탐색하는 대표적인 방법으로 BFS와 DFS가 있습니다. 

먼저 BFS를 살펴볼까요

BFS는 Breadth-First Search 라고 해서 너비 우선 탐색 입니다. 

BFS는 사이클이 없는 그래프에서 같은 레벨의 형제 노드들을 먼저 탐색하는 방식입니다. 가로로 지그재그 하는 방식이지요

BFS는 2개의 큐, visited, need_visit로 구현할 수 있습니다. 

need_visit 큐에는 방문해야 할 노드를 넣고, visited 큐에는 이미 방문한 노드를 넣습니다. 

큐 라이브러리를 쓸 수 있지만 python의 리스트로 간단하게 구현해볼 수 있습니다. 

def bfs(graph, start_node):
	visited = list()
    need_visit = list()
    
    need_visit.append(start_node):
    
    while need_visit :
    	node = need_visit.pop(0)
        if node not in visited :
        	visited.append(node)
            need_visit.extend(graph[node])
            
    return visited

DFS는 Depth First-Search로 깊이 우선탐색입니다. 

그래프가 주어졌을때 한 노드의 자식노드까지 탐색한 후 그 다음 옆 형제 노드로 이동해서 다시 그 형제 노드의 자식노드까지 탐색해 나가는 과정입니다. BFS와 달리 세로로 지그재그 형태이지요

DFS는 스택과 큐를 사용합니다. BFS가 2개의 큐를 사용하는 것과 조금 다르지요

need_visit는 스택, visited는 큐 입니다. 

need_visit 큐에는 방문해야 할 노드를 넣고, visited 큐에는 이미 방문한 노드를 넣습니다. 

def dfs(graph, start_node):
	visited, need_visit = list(), list()
    need_visit.append(start_node)
    
    while need_visit:
    	node = need_visit.pop()
        if node not in visited :
        	visited.append(node)
            need_visited.extend(graph[node])
    
    return visit

 

BFS, DFS 둘 모두 시간복잡도는 O(V+E)입니다. 

V는 정점 수, E는 간선 수 입니다. 

둘 모두 while need_visit에서 V+E만큼 반복하기 때문입니다.