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가 더 좋다.

Tip.

• BFS는 queue를 쓴다. 매번 adj를 전부 queue에 넣으면 금방 터질 것이다. 따라서, queue에 넣는 동시에 visited든 dpMemo든 기록해야한다. 추후 queue에 넣기 직전에 이것을 확인하여 불필요한 push를 막을 수 있다.
• DFS는 stack을 쓴다. 일단 끝까지 들어가봐야 알기 때문에 보통, 자손 dfs가 return 됐을 때 push 한다.
  ex)