資料結構（十三）圖的周遊

圖的周遊

1. DFS

深度優先搜尋（Depth First Search)，類似于樹的先序周遊

void DFS ( Vertex V ){
    visited[ V ] = true;
    for ( V 的每個鄰接點 W )
        if( !visited[ W ])
            DFS( W );
}
           

若有 N 個頂點、E 條邊，時間複雜度是

• 用鄰接表存儲，O(N + E)
• 用鄰接矩陣存儲，O(N 2 ​ ^2​ 2​)

2. BFS

廣度優先搜尋（Breadth First Search)，相當于樹的層序周遊

void BFS( Vertex V ){
    queue<Vertex> q;
    visited[V] = true;
    q.push(V);
    while(!q.empty()){
        V = q.front(); q.pop();
        for( V 的每個鄰接點 W ){
        	if( !visited[ W ]){
            	visited[W] = true;
            	q.push(W);
            }
        }
    }
}
           

若有 N 個頂點、E 條邊，時間複雜度是

• 用鄰接表存儲，O(N + E)
• 用鄰接矩陣存儲，O(N 2 ^2 2)