Zhejiang University

1
2
3
4
5
6
7
void DFS(Vertex V){   
visited[V] = true;
for(each adjacent vertex w){
if(!visited[w])
DFS(w);
}
}

Complexity
Adjacent List: O(N+E)O(N+E)
Adjacent Matrix: O(N2)O(N^2)

1
2
3
4
5
6
7
8
9
10
11
void BFS(Vertex V){ 
visited[V] = true;
Enqueue(V, Q);
while(!IsEmpty(Q)){
V = Dequeue(Q);
for(each adjacent vertex W of V) if(!visited[V]){
visited[V] = true;
Enqueue(W, Q);
}
}
}

Complexity
Adjacent List: O(N+E)O(N+E)
Adjacent Matrix: O(N2)O(N^2)

Problem: Disconnected Graph

Connected Component: Extreme large subGraph of a undirected graph.

  • Extreme large number of vertexes
  • Extreme large number of edges

Strongly Connected: V and W are connected in both directions.

  • Remark: The 2 paths need not be the same!

Strongly Connected Graph: Any given pair of vertexes are strongly connected.

Strongly Connected Component: Extreme large subGraph of a directed graph.

1
2
3
4
5
void ListComponents(Graph G){  
for (each V in G)
if(!visited[V])
DFS(V);
}