Vertices(Nodes)와 Edges로 이루어진 Data Structure, G( V, E )
다음은, Undirected Graph의 예시이다.
0 - 1
| / |
2 - 3 - 4
다음의 두 가지 방법으로 그래프를 표현할 수 있다.
1) Adjacency Matrix
2) Adjacency List
VxV Array에 (u,v) edge 가 존재하면 1, 없으면 0으로 둔다.
0 1 2 3 4
0 0 1 1 0 0
1 1 0 1 1 0
2 1 1 0 1 0
3 0 1 1 0 1
4 0 0 0 1 0
이 방식은 접근이 빠르고 구현하기 쉽다.
하지만, O(V^2)의 공간을 요구하는 단점이 있다.
adj[0] -> 1 -> 2 /
adj[1] -> 0 -> 2 -> 3 /
adj[2] -> 0 -> 1 -> 3 /
adj[3] -> 1 -> 2 -> 4 /
adj[4] -> 3 /
존재하는 edges만 나타내므로 공간을 덜 차지한다.
Graph Traversal 알고리즘에는 크게 두 가지가 있다.
1) BFS(Breadth First Search)
2) DFS(Depth First Search)
Queue를 이용해서 순회한다.
while( Queue != empty ){
curNode = Queue.pop()
for ( dst: curNode와 연결된 Node ){
if ( dst != visited ){
visited[dst] = true;
Queue.push(dst);
}
}
}
시간 복잡도는 O(V+E) 이다.
Stack을 이용하여 순회한다. 이때, recursive call을 통해 Stack을 자동으로 사용한다.
DFS( curNode )
{
visited[curNode] = true
for ( dst: curNode와 연결된 Node ){
if ( dst != visited )
DFS( dst )
}
}
시간 복잡도는 O(V+E) 이다.
먼저, 문제 상황에 맞게 선택하는 것이 가장 중요하다. 그렇지만, 일반적으로, 가까운 거리부터 전수조사 해야하는 경우 BFS가 더 좋고, Backtracking 시에는 DFS가 더 좋다.