12. 그래프 기초 (Graph Basics): 파이썬 자료구조와 알고리즘

그래프란 여러 노드 (node, 또는 정점, vertex) 들이 간선 (edge, 또는 아크, arc) 으로 연결된 추상 네트워크를 뜻한다. 가장 기본적인 용어들부터 알아보도록 하자.

 

용어

그래프

그래프는 아까 말했듯 여러 노드와 간선으로 연결된 추상 네트워크를 뜻한다. 즉, 그래프는 노드와 간선의 집합으로 정의되며 이를 수식으로 쓰면 다음과 같다.

G는 그래프 (graph), V는 노드 (vertex) 의 집합, 즉 아래와 같은 그래프에선 {a,b,c,d} 이고, E는 간선 (edge) 의 집합, 즉 노드 쌍들의 집합이며, 아래와 같은 그래프에선 {{a,b}, {b,c}, {c,d}, {d,a}}이다.

그래프의 방향

그래프에는 방향이 있는 유향 (directed) 그래프와 방향이 없는 무향 (undirected) 그래프가 있다. 무향 그래프는 말 그대로 간선에 방향이 지정되어 있지 않으며, 간선으로 연결된 노드들은 서로 인접 (adjacent) 해 있으며 이웃 (neighbor) 이라고 한다. 아래와 같은 모양을 띈다.

유향 그래프의 경우 순서가 존재하므로, 말단 (leaf) 노드가 존재한다. 유향 그래프 G에서 함수 E(G) 는 V(G) 에 대한 관계라고도 말할 수 있다.

또는

부분 그래프

부분 그래프 (subgraph) 는 그래프 G에서 집합 V와 E로 구성된 그래프의 일부이다. 노드 몇 개가 빠질 수도, 또는 간선 몇 개가 빠질 수도 있다. 다음과 같은 그래프 G가 있다고 했을 때,

부분 그래프는 아래와 같은 것들이 있을 수 있다.

간선이 하나 빠진 부분 그래프

노드가 하나 빠진 부분 그래프

노드가 하나 빠진 부분 그래프

등. 또한, 유도 부분 그래프 (induced subgraph) 란 부분 그래프의 부분 그래프를 의미하며, 신장 부분 그래프 (spanning subgraph) 란 원본 그래프의 모든 노드를 포함하는 부분 그래프를 의미한다. 즉 위의 부분 그래프 예시 중 가장 위의 예시가 신장 부분 그래프의 예시이다.

 

완전 그래프

완전 그래프 (complete graph) 란 그래프의 모든 노드가 서로 인접한 그래프를 말한다. 다음완 완전 그래프들의 예시이다. 익숙한 모양이 그려지는 것을 확인할 수 있다.

차수

한 노드에 이어져 있는 간선의 수를 차수 (degree) 라고 한다. 차수가 0인 노드는 고립 (isolated) 되었다고 한다. 유향 그래프의 경우, 입력 차수 (in-degree) 와 출력 차수 (out-degree) 로 나눌 수 있으며, 각각 노드로 들어오는 간선과 노드에서 나가는 간선의 수를 뜻한다.

 

경로, 보행, 순환

그래프에서 경로 (path) 는 간선이 어느 노드도 다시 방문하지 않고 노드가 일렬로 연결된 부분 그래프다. 유향 그래프에서 경로는 간선의 방향을 따른다.

 

보행 (walk) 은 노드와 간선을 번갈아 가며 반복적으로 방문하는 노드와 간선이다. 경로는 노드와 간선이 모두 중복되지 않는 보행과 같다 (즉, 경로의 상위 집합이다).

 

순환 (cycle) 은 경로와 같으나 마지막에 연결된 간선의 노드가 다시 첫 번째 노드에 연결된다.

 

경로 또는 보행의 길이 (length) 는 지나가는 간선의 수를 뜻한다.

 

가중 그래프

가중 그래프는 간선에 가중치 (weight) 가 있는 그래프다. 경로 또는 순환의 가중치는 해당하는 간선들의 가중치의 총합이다. 가중 그래프가 아닌 경우에는 경로와 순환의 가중치가 간선의 수와 같다.

 

평면 그래프

평면 그래프 (planar graph) 는 간선을 서로 횡단하지 않고 평면에 그릴 수 있는 그래프 (즉, 간선이 교차하지 않는) 를 뜻한다. 이 그래프는 간선에 의해 경계면 (bounded face) 을 가진다. 연결된 평면 그래프의 오일러 공식 (Euler's formula) 에 따르면, V - E + F = 2 이다 (V는 노드 수, E는 간선 수, F는 면 수 왠지 화공과에서 배운 자유도의 법칙, the law of degree of freedom, 이 기억나는 식이다). 오일러 공식에 대한 정리는 아래 위키를 참고하도록 하자.

 

https://librewiki.net/wiki/%ED%8F%89%EB%A9%B4%EA%B7%B8%EB%9E%98%ED%94%84

평면그래프

 

그렇다면 아래 그래프는 평면 그래프일까?

 

정답은 예이다. 왜냐하면 얼핏 보면 교차하는 것처럼 보이지만 (그렇게 그려 놨지만), 위 그래프를 변환을 통해 아래와 같은 평면 그래프로 다시 나타낼 수 있기 때문이다.

 

오일러 정리에 대한 더 자세한 내용은 아래 블로그를 참고하도록 하고,

 

https://suhak.tistory.com/189

오일러 정리

 

이 외에 오일러 정리에 대한 20가지 증명 방법은 아래 글을 참고하도록 하자.

 

https://www.ics.uci.edu/~eppstein/junkyard/euler/

Euler's Formula

 

한 편, 평면 그래프가 아닌 그래프는 대표적으로 아래 두 그래프가 있다.

 

각각 K₅, K_3,3 이라고 불리는 그래프이며, 쿠라토프스키 정리에 따르면 그래프 G가 평면 그래프일 필요충분조건은 G가 K₅ 나 K_3,3 의 세분할 (subdivision) 과 동형 (isomorphic) 인 부분 그래프를 갖지 않는 것이다. 물론 이해하지 못했다.

 

순회

순회 (traversal) 란 그래프에 연결된 모든 요소를 탐색하는 일을 말한다. 순회에서 중요한 것은 (아직 방문하지 않은) 노드의 순회 순서다.

 

강한 연결 요소

무향 그래프는 모든 노드에서 다른 모든 노드로 가는 경로가 존재할 때 연결 (connected) 되어 있다고 한다. 유향 그래프도 마찬가지다. 즉 아래 그래프는 연결된 그래프이다. a에서 c로 가고 싶다면 a-b-c 또는 a-d-c 순으로 이동하면 된다.

 

연결 요소 (conneceted component) 는 모든 노드가 연결된 최대 부분 그래프를 뜻한다. 연결 요소는 깊이 우선 탐색 (DFS) 과 너비 우선 탐색 (BFS) 같은 순회 알고리즘을 사용하여 찾을 수 있다.

 

유향 그래프에서 모든 노드에서 다른 모든 노드까지의 경로가 있으면, 강하게 연결 (strongly connected) 되었다고 한다. 이 때 강한 연결 요소 (strongly connected component) 는 강하게 연결된 최대 하위 그래프를 뜻한다.

 

트리와 포레스트

포레스트 (forest) 는 순환이 없는 (cycle-free) 그래프다. 트리 (tree) 는 비순환적 (acyclic) 이고 연결되어 있는 유향 그래프를 말한다. 포레스트는 하나 이상의 트리로 구성되어 있으며, 즉 서로 독립적인 트리의 모임이다.

 

트리에서 두 노드는 정확히 하나의 경로로 연결된다. 트리에 새로운 간선을 하나 추가하면 순환이 생기고 어떤 간선을 제거하면 연결되지 않은 요소가 생성된다.

 

이웃 함수

그래프의 이웃 함수 (neighborhood) N(V) 는 모든 이웃 V의 컨테이너 (또는 반복 가능한 객체) 다. 그래프의 이웃 함수로 가장 잘 알려진 자료구조는 인접 리스트와 인접 행렬이다. 이와 관련된 정보는 아래를 확인하도록 하자.

 

https://kingpodo.tistory.com/46

6-2. 그래프의 표현(인접 행렬, 인접 리스트, 인접 다중 리스트)

 

인접 리스트

인접 리스트 (adjacency list) 에서는 각 노드에서 이웃 리스트 (셋 또는 컨테이너와 같은 반복 가능 객체) 에 접근할 수 있다. n개의 노드가 있을 때, 각 노드의 인접 (또는 이웃) 리스트는 단순한 숫자 리스트다. 숫자로 노드에 접근 가능한 (인덱싱 가능한) n 개의 메인 리스트에 각 노드의 인접 리스트를 추가하면 된다. 인접 리스트의 추가 순서는 보통 임의적이다.

 

셋을 이용한 인접 리스트 구현

파이썬에서 셋을 사용하여 인접 리스트를 구현해보자.

 

>>> a,b,c,d,e,f = range(6) # 6개 노드
>>> N = [{b,c,d,f}, {a,d,f}, {a,b,d,e}, {a,e}, {a,b,c}, {b,c,d,e}]
>>> b in N[a] # 멤버십 테스트
True
>>> b in N[b]
False
>>> len(N[f]) # 차수
4

 

리스트를 이용한 인접 리스트 구현

리스트를 사용하여 인접 리스트를 구현할 수도 있다. 이 경우 모든 노드 V에서 N(V)를 효율적으로 순회할 수 있다. 셋을 리스트로 바꾸면 멤버십 테스트의 시간복잡도가 O(n)이 된다 (셋의 경우 평균 시간 복잡도는 O(1), 최악 시간 복잡도는 O(n) 이다). 알고리즘을 수행하는 어떤 작업이 이웃 노드를 반복해서 접근하는 경우 리스트를 사용하는 게 좋을 것이다. 그래프가 촘촘한 경우 (간선이 많은 경우) 에는 셋을 사용하는 게 더 좋다.

 

>>> a,b,c,d,e,f = range(6)
>>> N = [[b,c,d,f], [a,d,f], [a,b,d,e], [a,e], [a,b,c], [b,c,d,e]]
>>> b in N[a]
True
>>> b in N[b]
False
>>> len(N[f])
4

 

파이썬 리스트의 중간에서 어떤 한 객체를 삭제하는 시간 복잡도는 O(n) 이지만 리스트 끝에서의 삭제는 O(1) 이다. 이웃 노드의 순서가 중요하지 않다면, 삭제하려는 임의의 이웃을 마지막 항목으로 위치를 바꾼 후 pop()을 호출하여 O(1)에 임의의 이웃을 삭제할 수 있다.

 

딕셔너리를 이용한 인접 리스트 구현

딕셔너리를 이용하면 각 노드를 간선 가중치 등의 값으로 연결할 수 있다.

 

>>> a,b,c,d,e,f = range(6)
>>> N = [{b:2,c:1,d:4,f:1}, {a:4,d:1,f:4}, {a:1,b:1,d:2,e:4}, {a:3,e:2}, {a:3,b:4,c:1}, {b:1,c:2,d:4,e:3}]
>>> b in N[a]
True
>>> len(N[f])
4
>>> N[a][b] # (a,b)의 간선 가중치, weight
2

 

또는 딕셔너리의 기본 구조를 활용하여 조금 더 유연한 인접 리스트를 만들 수 있다. 예를 들어 다음과 같이 딕셔너리를 인접 셋에 활용할 수 있다.

 

>>> a,b,c,d,e,f = range(6)
>>> N = { 'a':set('bcdf'), 'b':set('adf'), 'c':set('abde'), 'd':set('ae'), 'e':set('abc'), 'f':set('bcde')}
>>> 'b' in N['a']
True
>>> len(N['f'])
4

 

인접 행렬

인접 행렬 (adjacent matrix) 은 각 노드의 모든 이웃에 대해 하나의 행을 갖는다. 각 행의 값은 1(True) 와 0(False)으로 이루어진다. 인접 행렬은 중첩 리스트로 간단하게 구현할 수 있다. 행렬의 대각선 요소는 항상 0이다.

 

>>> a,b,c,d,e,f = range(6)
>>> N = [[0,1,1,1,0,1], [1,0,0,1,0,1], [1,1,0,1,1,0], [1,0,0,0,1,0], [1,1,1,0,0,0], [0,1,1,1,1,0]]
>>> N[a][b] # 멤버십 테스트: True
1
>>> N[a][e] # 멤버십 테스트: False
0
>>> sum(N[f]) # 차수
4

 

무향 그래프의 인접 행렬은 항상 대칭 (symmetric) 이다. 인접 행렬에 가중치를 추가하려면 1과 0 값을 다른 숫자로 바꾸면 된다. 존재하지 않는 간선은 float('inf') (양의 무한대), None, -1, 혹은 매우 큰 값 등으로 나타내면 된다.

 

>>> _ = float('inf')
>>> N = [[_,2,1,4,_,1], [4,_,_,1,_,4], [1,1,_,2,4,_], [3,_,_,_,2,_], [3,4,1,_,_,_], [1,2,_,4,3,_]]
>>> N[a][b] # 가중치, weight
2
>>> N[a][b] < _ # 멤버십 테스트
True
>>> sum(1 for w in N[f] if w < _) # 차수
4

 

인접 행렬에서 간선을 찾는 시간 복잡도는 O(1)이며 어떤 노드의 이웃을 순회하는 시간 복잡도는 O(n)이다.

 

트리와의 연결점

그래프에서 어떤 노드는 다른 노드에 의해 다중 참조될 수 있다. 하지만 트리에서 각 노드는 최대 하나의 부모 (parent) 노드 (상위 노드) 에 의해서만 참조된다. 루트 (root) 노드는 부모가 없는 노드를 말한다. 부모 노드를 참조하는 노드는 자식 (child) 노드이다. 트리에 대한 용어는 다음 포스트에서 다시 자세히 살펴보자.

 

트리의 구현

트리를 구현하는 가장 간단한 방법은 중첩 리스트를 사용하는 것이다.

위와 같은 트리를 리스트로 구현해보자.

 

>>> T = ['a', ['b', ['d','f']], ['c',['e','g']]]
>>> T[0]
'a'
>>> T[1][0]
'b'
>>> T[1][1][0]
'd'

 

그러나 이러한 코드는 가지 (branch) 가 두 개 이상으로 늘어나면 트리를 다루기 불편해진다. 따라서 트리를 클래스로 정의하는 것이 좋다. 이는 다음 포스트에서 다뤄보도록 하자.

 

출처

파이썬 자료구조와 알고리즘 - 한빛미디어, 미아 스타인

https://librewiki.net/wiki/%ED%8F%89%EB%A9%B4%EA%B7%B8%EB%9E%98%ED%94%84

https://en.wikipedia.org/wiki/Planar_graph

https://kingpodo.tistory.com/46