图的遍历

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 <math> <semantics> <mrow> <msup> <mn> 2 </mn> </msup> <mi mathvariant="normal"> ​ </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> ^2​ </annotation> </semantics> </math>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 ){
            visited[W] = true;
            q.push(W);
        }
    }
}

若有 N 个顶点、E 条边，时间复杂度是

  • 用邻接表存储，O(N + E)
  • 用邻接矩阵存储，O(N <math> <semantics> <mrow> <msup> <mn> 2 </mn> </msup> </mrow> <annotation encoding="application&#47;x&#45;tex"> ^2 </annotation> </semantics> </math>2)