그래프의 표현에는 인접 리스트가 유용한 경우가 많다. 인접 행렬의 탐색 시간은 N^2인 반면에, 인접 리스트의 경우 N+E에 비례하기 때문이다.
다음과 같은 예시 그래프를 사용할 것이다.
graph = {
1: [2, 3],
2: [1, 4],
3: [1, 5, 6],
4: [2],
5: [3, 6],
6: [3, 5],
}
import networkx as nx
import matplotlib.pyplot as plt
class GraphVisualization:
def __init__(self, graph):
self.graph = []
for i in graph:
for j in graph[i]:
self.graph.append([i,j])
def addEdge(self, a, b):
temp = [a, b]
self.graph.append(temp)
def show(self):
G = nx.Graph()
G.add_edges_from(self.graph)
nx.draw_networkx(G)
plt.show()
G = GraphVisualization(graph)
G.show()
그래프의 각 정점을 방문하는 방법은 깊이 우선 탐색과 너비 우선 탐색으로 나뉜다.
그래프 순회 과정에서 각 노드의 하위 노드를 우선적으로 탐색하는 것을 깊이 우선 탐색이라고 한다.
# 재귀적 구조를 이용한 DFS
graph={}
visited = [0]*len(graph)
def dfs(vertex):
visited[vertex-1] = 1
print(vertex)
for i in graph[vertex]:
if visited[i-1]==0:
dfs(i)
return
dfs(1)
# 스택을 이용한 DFS
graph = {}
queue = [1]
visited = [0]*len(graph)
vertex = 1
visited[vertex-1] = 1
while queue:
print(vertex, queue, visited)
for i in graph[vertex]:
if visited[i-1]==0:
visited[i-1] = 1
queue.append(i)
vertex = queue.pop()
만약 그래프에 루프가 포함되어 있다면 재귀 또는 스택이 계속해서 호출되어 순회가 끝나지 않게된다. 이 때문에 방문 여부를 확인해야 하며, 위 예시에서는 루프가 없어 visited가 필요하지 않다.
DFS 과정에서 하위 노드를 탐색하고 난 뒤 지나온 경로를 따라 부모 노드를 찾아가는 과정을 백트래킹이라고 한다. 현재 노드에 하위 노드가 존재하지 않는다면, 재귀 구조의 경우 재귀를 종료시켜 부모 노드로 돌아간다. 스택을 통해 구현된 경우 미리 경로를 기억하기 위한 리스트를 만들어 놓은 뒤, 하나씩 되짚어보며 탐색하지 않은 하위 노드가 있는지를 살펴보아야 한다.
그래프를 순회하는 목적 중 하나는 특정 조건을 만족하는 노드를 찾는 것이다. 예를 들어, DFS를 통해 올바른 순서 배열을 찾는 경우 앞 순서가 맞지 않는 경우 하위 노드를 탐색할 필요가 없다. 따라서 조건을 만족하지 않는 분기를 탐색 과정에 포함하지 않기 위해 백트래킹이 사용된다.