DFS遍历图

DFS

采用DFS遍历图的步骤：
1.从一个未被访问的顶点开始，准备访问所有与它邻接的顶点。
2.把访问过的顶点标记好，递归地处理之后的顶点，直到所有顶点都被访问过。

• 连通分量：在无向图中，如果两个顶点之间可以相互到达，那么这两个顶点就是连通的。如果图G(V,E)的任意两个顶点都连通，则称G为连通图。否则，G为非连通图，称其中的极大连通子图为连通分量。
• 强连通分量：在有向图中，如果两个顶点可以各自通过一条有向路径到达另一个顶点，那么他们是强连通的。如果图G(V,E)中任意两顶点都强连通，那么G是强连通图。否则就是非强连通图，那么它的极大强连通子图就是强连通分量。
• 连通块：连通分量和强连通分量的统称。
  下图中，图A有三个连通分量：V₁V₂V₃, V₄V₅V₆V₇V₈, V₉. 图B有两个强连通分量：V₁V₂V₃, V₄V₅V₆V₇.
  
  一个非连通图 和 一个非强连通图

DFS模板

const int MAXV = 1000; // 顶点数
const int INF = 1000000000 // 表示无穷大，G[a][b]==INF表示ab两点不连通

// 用邻接矩阵 表示图
int n, G[MAXV][MAXV]; // n表示顶点数
bool vis[MAXV] = { false }; // 访问标记

void dfs( int u, int depth ) // u表示当前访问的顶点编号，depth表示深度
{
    vis[u] = true;
    // 这里对u进行其他操作
    // 接下来访问所有与u邻接的顶点
    for( int v = 0; v<n; ++v )
        if( vis[v]==false && G[u][v]!=INF )
            dfs(v,depth+1);
}

void dfsGraph()
{
    for( int u = 0; u<n; ++u )
        if(vis[u]==false)
            dfs(u,1);
}

// 用邻接表 表示
#include <vector>

vector<int> Adj[MAXV];
int n; // 顶点数
bool vis[MAXV] = { false };

void dfs( int u, int depth )
{
    vis[u] = true;
    // 这里对u进行其他操作
    // 接下来要访问的是Adj[u]这个vector
    for( int i = 0; i < Adj[u].size(); ++i )
    {
        int v = Adj[u][v];
        if( vis[v]==false )
            dfs(v,depth+1);
    }
}

void dfsGraph()
{
    for( int u = 0; u < n; ++u )
        if( vis[u]==false )
            dfs(u,1);
}