本文介绍了一下深度优先遍历（depth-first search，DFS）的框架。下面代码使用了 vector 式的邻接表，其中 G[u][i] 表示结点 u 的第 i 个子结点。每条边用（u，v）表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>

int maxn=100;
std::vector<int> G[maxn];  //图
int vis[maxn];

dfs(int u)
{
    vis[u]=1;
    PREVISIT(u);    //访问结点u之前的操作
    int i=0,v=-1;
    int d=G[u].size();
    for(i=0;i<d;++i)     //枚举每条边
    {
        v=G[u][i];
        if(!vis[v])  dfs(v);
    }
    POSTVISIT(u);   //访问结点u之后的操作
}

我们把相互可达的结点称为一个连通分量，则很容易用DFS在线性时间内求出任意无向图的连通分量。下面代码为每个结点计算出了该结点所属的连通分量编号。

1
2
3
4
5
6
7
8
9
10
11
void find_cc()
{
    current_cc=0;
    memset(vis,0,sizeof(vis));
    for(int u=0;u<n;u++)    //依次检查图中的每个结点
        if(!vis[u])
        {
            current_cc++;  //如果结点u没有被访问过，意味着它属于一个新的连通分量
            dfs(u);  //从结点u开始DFS可以访问到它所在的整个连通分量
        }
}

这里current_cc表示当前连通分量的编号。如果要记录每个结点的连通分量编号，需要在PREVISIT(u) 中赋值cc[u]=current_cc。

如果我们只需要求连通分量，可以使用并查集，不需要保存图，只需按照某种顺序处理所有的边。

二分图的判定

对于无向图 G=(V,E)，如果可以把结点集分成不相交的两部分，即 X 和 Y=V-X，使得每条边的其中一个端点在X中，另一个端点在Y中，则称 G 是二分图（bipartite graph）。 二分图的另一种说法是，可以把每个结点着以黑色和白色之一，是的每条边的两个端点颜色不同。不难发现，非连通的图是二分图当且仅当每个连通分量都是二分图，因此我们只需考虑无向连通图。

下面我们用 DFS 给任意无向图 G 进行黑白二着色。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int color[maxn];   //调用函数之前color数组清零

//判断结点u所在的连通分量是否为二分图
bool bipartite(int u)
{
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i]; 		//枚举每条边
        if(color[v]==color[u])  return false;
        if(!color[v])
        {
            color[v]=3-color[u];
            if(!bipartite(v))  return false;
        }
    }
    return true;
}

摘自白书。