Graph

Vertices(Nodes)와 Edges로 이루어진 Data Structure, G( V, E )

다음은, Undirected Graph의 예시이다.

0 - 1
| / | 
2 - 3 - 4 

Representation

다음의 두 가지 방법으로 그래프를 표현할 수 있다.
1) Adjacency Matrix
2) Adjacency List

1) Adjacency Matrix

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)의 공간을 요구하는 단점이 있다.

2) Adjacency List

adj[0] -> 1 -> 2 /
adj[1] -> 0 -> 2 -> 3 /
adj[2] -> 0 -> 1 -> 3 /
adj[3] -> 1 -> 2 -> 4 /
adj[4] -> 3 /

존재하는 edges만 나타내므로 공간을 덜 차지한다.

Traversal Algorithm

Graph Traversal 알고리즘에는 크게 두 가지가 있다.
1) BFS(Breadth First Search)
2) DFS(Depth First Search)

1) BFS(Breadth 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) 이다.

2) DFS(Depth First Search)

Stack을 이용하여 순회한다. 이때, recursive call을 통해 Stack을 자동으로 사용한다.

DFS( curNode )
{
	visited[curNode] = true
    for ( dst: curNode와 연결된 Node ){
    	if ( dst != visited )
    		DFS( dst )
    }
}

시간 복잡도는 O(V+E) 이다.

BFS vs DFS

먼저, 문제 상황에 맞게 선택하는 것이 가장 중요하다. 그렇지만, 일반적으로, 가까운 거리부터 전수조사 해야하는 경우 BFS가 더 좋고, Backtracking 시에는 DFS가 더 좋다.