그래프에서의 DFS

강의 사이트

• http://www.kocw.net/home/search/kemView.do?kemId=1148815

그래프 순회

1. 깊이 우선 순회 (DFS)

1.1 트리로 표현

2. Psuedo Code

DFS(G, v)
	visited[v] <- YES;
	for each node u adjacent to v do
		if visited[u] = NO then
			DFS(G, u);
	end.
end.

• 그래프가 disconnected이거나 혹은 방향 그래프라면 DFS에 의해서 모든 노드가 방문되지 않을 수도 있음

• DFS를 반복하여 모든 노드 방문