그래프 정의
그래프는 정점(Vertex)의 집합과 간선(Edge)의 집합으로 이루어진 자료구조입니다. 정점의 집합을 V, 간선의 집합을 E, 그래프를 G라고 했을 때 G = (V, E) 입니다. 정점은 위치를 의미하고, 간선은 정점과 정점을 연결하는 선을 의미합니다.
간선으로 연결되어 있는 두 정점을 가리켜 서로 인접(adjacent)해 있다고 표현합니다. 인접한 두 정점은 경로를 형성하기도 하는데 위 그림을 보면 1, 2, 3, 4 가 경로를 형성합니다. 경로 1, 2, 3, 4 사이에는 간선이 (1, 2), (2, 3), (3, 4) 3개가 있으므로 길이는 3이 됩니다.
경로가 정점 하나를 두 번 이상 거치게 된다면 그 경로는 사이클(Cycle)이 있다고 표현합니다. 위 그림에서 1, 2, 3 경로가 사이클을 가지고 있습니다.
간선이 방향성을 가지고 있으면 방향성 그래프(Directed Graph)가 되고, 방향성이 없으면 무방향성 그래프(Undirected Graph)가 됩니다.
그래프 표현
그래프는 주로 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)로 표현합니다.
인접 행렬(Adjacency Matrix)
인접 행렬은 2차원 배열로 정점 사이의 인접한 관계를 나타냅니다. 두 정점이 연결 되어 있을 경우 1, 연결 되어 있지 않은 경우 0으로 나타냅니다.
무방향성 그래프에서는 정점 1과 정점 2가 인접할 경우 정점 2와 정점 1 또한 인접하기 때문에 인접행렬은 대각선에 대해 대칭을 이룹니다. 반면 방향성 그래프에서는 정점이 인접해 있는 경우에만 1로 나타냅니다.
인접 행렬은 인접한 정점을 빠르게 알아낼 수 있는 장점이 있지만, N개의 정점을 가지고 있다면 N^2 만큼 메모리 공간을 차지하게 되는 단점이 있습니다.
인접 리스트(Adjacency List)
인접 리스트는 정점 사이의 인접한 관계를 리스트로 표현합니다. 인접 리스트는 인접 행렬 보다 메모리를 적게 차지하지만, 인접 리스트를 순차적으로 탐색해야 하는 단점이 있습니다.
그래프 순회
그래프를 순회하는 것은 모든 정점을 방문하는 것을 의미합니다. 그래프를 순회하는 방법으로는 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이 있습니다.
깊이 우선 탐색(Depth First Search)
깊이 우선 탐색은 더 이상 갈 수 없을 때까지 탐색하는 방법입니다.
깊이 우선 탐색의 방법은 다음과 같습니다.
- 방문한 정점을 표시한다.
- 정점과 인접한 정점 중 방문하지 않은 정점을 선택하여 다시 깊이 우선 탐색을 한다.(1번 반복)
- 방문하지 않은 인접한 정점이 없으면 이전 정점으로 돌아가서 깊이 우선 탐색을 한다. (2번 반복)
- 더 이상 방문할 인접 정점이 없다면 탐색을 종료한다.
이해를 돕기 위해 예를 들어 보겠습니다.
위 그래프에서 정점 1 부터 시작해서 DFS로 방문하겠습니다. 정점 1을 방문했으므로 방문 표시를 합니다. 방문은 파란색으로 표시했습니다.
정점 1과 인접한 정점인 정점 2를 방문하고 방문 표시를 합니다.(정점 3을 먼저 방문해도 상관 없지만 정점 2를 먼저 방문하겠습니다.)
정점 2와 인접한 정점 4를 방문하고 방문 표시를 합니다.
정점 4와 인접한 정점 6을 방문하고 방문 표시를 합니다. 정점 6은 더 이상 방문할 정점이 없으므로 이전 정점으로 되돌아 갑니다. 정점 4로 되돌아가면 방문하지 않은 곳이 없으므로 정점 2로 되돌아갑니다.
정점 2은 방문하지 않은 정점 5가 있으므로 정점 5를 방문하고 방문 표시를 합니다. 정점 5는 인접한 정점 4 와 정점 6이 있지만 이미 방문했으므로 더 이상 방문할 정점이 없습니다. 따라서 이전 정점인 정점 2로 되돌아 갑니다. 정점 2는 방문하지 않은 정점이 없으므로 이전 정점인 정점 1로 되돌아갑니다.
정점 1은 방문하지 않은 정점 3이 있으므로 정점 3을 방문하고 방문 표시를 합니다. 정점 3은 방문하지 않은 정점이 없으므로 이전 정점인 정점 1로 돌아가고 정점 1 또한 방문하지 않은 정점이 없으므로 탐색을 종료합니다.
DFS 구현
그래프는 인접 행렬로 간단하게 표현했고, 방문 표시는 빠른 성능을 위해 집합을 사용했습니다.
다음은 DFS를 구현한 예제 코드입니다.
def dfs(vertex, graph):
visited.add(vertex)
print(vertex + 1, end = '') # 출력용
for i, v in enumerate(graph[vertex]):
if v == 1 and i not in visited:
print(end=' -> ') # 출력용
dfs(i, graph)
global visited # 방문 표시
if __name__ == "__main__":
visited = set()
graph = [
[0, 1, 1, 0, 0, 0],
[0, 0, 0, 1, 1, 0],
[0, 0, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 1, 0, 1],
[0, 0, 0, 0, 0, 0]
]
dfs(0, graph)1 -> 2 -> 4 -> 6 -> 5 -> 3너비 우선 탐색(Breadth First Search)
너비 우선 탐색은 정점으로부터 깊이가 1인 정점를 방문하고 나서 깊이가 2, 3인 정점을 방문하는 방법입니다. 너비 우선 탐색은 자료구조 큐를 사용합니다.
너비 우선 탐색의 방법은 다음과 같습니다.
- 시작 정점을 방문 표시하고, 시작 정점을 큐에 삽입한다.
- 큐에 있는 정점을 꺼내고 꺼낸 정점과 인접한 정점 중 방문하지 않은 정점을 방문 표시하고, 큐에 삽입한다.
- 큐가 빌 때까지 2번의 과정을 반복하고 큐가 비면 탐색이 종료된다.
이해를 돕기 위해 DFS에서 예를 들었던 정점을 BFS로 예를 들어 보겠습니다. 마찬가지로 정점 1 부터 시작해서 BFS 로 방문하겠습니다.
시작 정점 1을 방문표시하고 정점 1을 큐에 삽입합니다.
큐에 있는 정점 1을 꺼내고 정점 1과 인접한 정점 2, 정점 3 을 방문 표시한 후 큐에 삽입합니다.
큐에 있는 정점 2 를 꺼내고 정점 2 와 인접한 정점 4, 정점 5 를 방문 표시한 후 큐에 삽입합니다.
큐에 있는 정점 3 을 꺼내고 정점 3 과 인접한 정점 4, 5 는 이미 방문했으므로 다시 큐에 있는 정점 4를 꺼냅니다. 정점 4와 인접한 정점 6 을 방문 표시한 후 큐에 삽입합니다.
큐에 있는 정점 5 를 꺼내고 정점 5 와 인접한 정점 4, 정점 6 은 이미 방문했으므로 다시 큐에 있는 정점 6을 꺼냅니다. 정점 6은 인접한 정점이 없고 큐는 비어 있으므로 탐색을 종료합니다.
BFS 구현
파이썬에서는 큐를 배열로 구현하게 되면 데이터를 꺼내는데 시간복잡도가 O(n)가 되므로 collections 모듈의 deque를 사용하였습니다.
다음은 BFS를 구현한 예제 코드입니다.
from collections import deque
def bfs(vertex, graph):
visited = set()
queue = deque()
visited.add(vertex)
queue.append(vertex)
while len(queue) > 0:
curr_v = queue.popleft()
print(curr_v + 1, end=" -> ") # 출력용
for i, v in enumerate(graph[curr_v]):
if v == 1 and i not in visited:
visited.add(i)
queue.append(i)
if __name__ == "__main__":
graph = [
[0, 1, 1, 0, 0, 0],
[0, 0, 0, 1, 1, 0],
[0, 0, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 1, 0, 1],
[0, 0, 0, 0, 0, 0]
]
bfs(0, graph)1 -> 2 -> 3 -> 4 -> 5 -> 6 ->
댓글