[서울대학교 논자시 준비] 알고리즘 : chapter 10 그래프 : dfs, bfs

1. dfs와 bfs의 시간 복잡도

 

dfs와 bfs 모두 인접리스트, 인접 행렬로 구현할 수 있다.

 

N이 그래프의 노드의 수, E가 그래프의 간선의 수라고 하자.

 

dfs와 bfs 모두 

인접리스트로 그래프를 구현했을 때 O(N+E)의 시간 복잡도를 가지며 

인접행렬로 구현했을 때 O(N^2)의 시간 복잡도를 갖는다.

 

2. bfs 소스코드 C++

BFS(G, s){
	for each v ( s 
    	visited[v] = NO;
    }
    visited[s] = YES;
    enqueue(Q, s)
    while (Q!=0){
    u <- dequeue(Q);
    for each v ( L(u)
    	if (visited[v]=NO) then {
        	visited[v] <- YES;
            enqueue(Q, v);
        }
  }

bfs의 수행 시간은 O(V+E)이다

 

 

3. dfs 소스코드 C++

DFS(G)
{
for each v ( V
	visited[v] <- NO;
for each v ( V
	if (visited[v]=NO) then aDFS(v);
}

aDFS(v)
{
visited[v]<-YES;
for each x ( V
	if (visited[x]=NO) then aDFS(x);
}
}

DFS의 시간복잡도 역시 O(V+E) 이다.