1. 개요
-
그래프는 비-선형적인 자료구조이며, vertice(node)와 vertice사이를 연결하는 edge를 총망라한 자료구조이다. 결과적으로, 일종의 연결망을 생성한다고 볼 여지가 있다.
-
그래프의 용어는 다음과 같다.
1. Vertice: 그래프를 구성하는 node를 의미한다. 2. Edge: Vertice와 vertice를 이은 선을 의미한다. Vertice A와 E를 연결하는 선은 AE로 표현한다. 3. Order: 그래프를 구성하는 vertice의 총 개수를 의미한다. 4. Size: 그래프를 구성하는 edge의 총 개수를 의미한다. 5. Degree: 특정 vertice의 속성으로, 특정 vertice에 연결이 되어있는 edge의 수를 의미한다. 6. Direction: 그래프의 edge가 특정 방향으로만 이동이 가능한 경우, directed graph라 하며, 항상 쌍방향으로 이동이 가능한 경우 undirected graph라 한다. 7. Weight: Edge에 부여할 수 있는 특징으로, vertice간의 거리를 나타낸다고 볼 수 있다. 특정 edge를 이동하는 것에 필요한 cost로도 볼 수 있다. 8. Dense/Sparse: Edge의 수에 따른 분류로, vertice간 존재할 수 있는 edge의 최대 개수에 근접하면 dense하다고 하며, 그렇지 않으면 sparse하다고 한다. 9. Connected/Disconnected : 그래프 내의 어떤 두 vertice라도, edge를 통해 갈 수 없는 상태에 있으면 disconnected graph이며, 어떻게든 edge를 통해 모든 vertice를 갈 수 있으면 connected graph로 분류한다. 10. Simple/Non-Simple: 자기 자신으로 이어진 edge가 없거나, 한 vertice에서 한 vertice로 이어진 여러 평행한 edge가 없으면 simple graph이다. 그렇지 않으면 non-simple graph이다. 11. Cyclic/Acyclic: 한 vertice에서 시작하여 그 vertice로 이어지는 방법이 있으면 cyclic, 아니면 acyclic이다. 12. Path: 특정 vertice에서 특정 vertice로 이어지는 길 가운데, vertice와 edge를 반복하지 않은 경우를 의미한다. 13. Trail: 특정 vertice에서 특정 vertice로 이어지는 길 가운데, vertice는 반복해서 들를 수 있으나 edge를 반복하지 않은 경우를 의미한다. 14. Walk: 특정 vertice에서 특정 vertice로 이어지는 길 가운데, vertice와 edge를 반복하여 들른 경우를 의미한다. 15. Cycle: 시작과 끝의 vertice가 같으나, path를 지나온 경우를 의미한다. 16. Circuit: 시작과 끝의 vertice가 같으나, trail을 지나온 경우를 의미한다. -
BST/LinkedList 또한 그래프의 일종이다.
2. 그래프 순회
-
그래프에 존재하는 vertice를 모두 방문하는 알고리즘은 BST와 마찬가지로 Depth-First search와 Breadth-First search가 존재한다.
-
DFS는 한 edge를 정하면, 이미 들렀던 vertice로 밖에 갈 수 없을 때까지 진행을 한다. 막다른 길에 몰린 경우, 가장 최근에 들렀던 vertice에서 다른 vertice로 뻗어나가고, 전부 들를때까지 이를 반복한다.
-
Set과 stack을 이용한다.
DFS1(G, u)
initialize VisitedSet, VS
initialize Stack, S
S.push(u)
while S is not empty
v = s.pop
if v is not in VS
mark v in VS
for w adhacent to v
if w is not in VS
S.push(w)
DFS2(G, u)
u in VS
for w adjacent to u
if w is not in VS
DFS2(G, w)-
첫 코드는 재귀 없이, 두번째는 재귀를 이용한 방법이다. 시간복잡도는 O(V+E)이다.
-
BFS는 BST의 level-order와 비슷하다. 우선, 시작 vertice에서 edge하나로 연결된 vertice를 모두 들른 후, edge 2개로 갈 수 있는 vertice를 들르는 것을 반복한다.
-
Set과 queue를 이용한다.
BFS(G, s)
VisitedSet, VS
Queue, Q
s in VS
Q.enqueue(s)
while Q is not empty
v = Q.dequeue
for w adjacent v
if w is not VS
w in VS
Q.enqueue(w)-
시간복잡도는 DFS와 동일하다.
-
DFS와 BFS는 다음과 같은 특징을 가지고 있다.
1. 그래프가 connected한지 아닌지 알 수 있으며, 한 vertice에서 다른 vertice로의 path를 알려준다. 2. Cycle인지도 알 수 있기 때문에, 그래프가 tree인지도 알 수 있다. 3. 최소한의 edge로 그래프를 연결한 spanning tree를 얻을 수 있다. 4. Bipartite한 그래프인지도 알 수 있다. -
BFS와 DFS간 선택은, 그래프의 깊이와 크기에 따라, 그리고 목적에 따라 다른 결과가 나온다.
출처: https://learning.edx.org/course/course-v1:GTx+CS1332xIV+2T2020/home
이상의 내용은 edx 플랫폼을 통해 GTx에서 제공하는 Data Structures & Algorithms 강의의 내용을 개인적으로 정리한 것입니다. 그렇기 때문에, 부정확한 내용 혹은 잘못 이해하고 있는 내용이 있을 수 있으니 양해 부탁드립니다.
