图论经典问题的几种算法

---

图论是离散数学和计算机科学领域交叉的一个分支。图是由顶点和边组成的集合，作为一种抽象模型，解释自然事物的抽象关系。图论有几个基础问题，旨在揭示图的基本性质。
几种典型的图论问题有：最短路问题，最小生成树问题，网络流问题，极大强连通分量问题，图的拓扑排序问题。每个问题都有若干个基本的算法，具体到工程领域，它们有各自的优化方式。下面阐述这五个问题和对应的算法描述、实现和测试。

①最短路问题

问题描述：给定带权图G(V,E)，求定点s到定点v的最短路径。其中点s到点v的路径，定义为：存在一个边序列，第一条边以s为起点，最后一条边以v为终点，其中后一条边的起点为前一条边的终点。最短路径是指，s到v的路径上边权和最小。
最短路问题的实际意义非常显然，例如，在地图类软件中，给定起点和终点，程序可以给出满足各种条件的路径，如用时最短，红绿灯最少，换乘数最少等。这些都可以转化为最短路问题，区别在于建图的方式，尤其是不同的情形下“边权”的含义。因此这个问题有非常大的价值。

1. Dijstra算法$^{[1]}$$^{[2]}$

算法描述：Dijstra算法用于解决单源最短路问题。即在有向带权图中，给定源点（起点）s，该算法求出s到其他所有点的最短路径。
由于该算法为贪心思想，带权图中不能有负权环。否则s到某点的最短路长度可能是负无穷（跑无穷多次负权环）。
另外，无向图也能作为有向图来处理，对于s到t的无向边，只需拆成s到t和t到s的两条有向边即可。
算法流程：
①定义结点集合S，从源s到集合S中所有点的最短路径均已求出。显然初始时S中只有点s.
②反复挑选出最短路径估计为最小的结点u加入集合S，并对所有离开结点u的边进行松弛操作，直到所有结点进入集合S.
③每次找到离源顶点最近的顶点，然后以该顶点为中心扩展，最终得到源顶点到其余所有顶点的最短路径。
同时，采用堆进行实现。
基于该算法的贪心思想，不难证明它的正确性。
在最短路问题以及下面的生成树等问题中，图的稀疏和稠密是一个比较重要的指标。因此在这里我们定义“稀疏度”：
对于$|V|=N$的图G，其边数与同规模完全图的边数的比值，称为图的稠密度，即

$$η=\frac{|E|}{|G_W|}=\frac{2|E|}{N(N-1)}$$
相应地，定义稀疏度为：
$$\phi=1-\frac{2|E|}{N(N-1)}$$
易得稀疏度和稠密度都是$(0,1)$中的有理数。
Dijkstra算法的理论时间复杂度上界是$O(n^2)$
测试： 给出以下几组测试样例
下面我们约定稀疏图是稀疏度$\phi\le10\%$的图，稠密图是稀疏度$\phi\ge60\%$的图.

测试数据	运行结果	运行时间
V=3000 的稀疏图	14	2.469s
V=5000 的稀疏图	28	5.967s
V=5000 的稠密图	4	6.565s

具体的数据和代码、运行机器配置见于附录1.

2. SPFA算法$^{[1]}$$^{[2]}$

SPFA算法用于解决单源最短路问题，其比dijstra算法优越在spfa算法可以在带负权边图中求解最短路。若图中有负权圈，则可能造成某点对最短路为-∞，spfa算法可以判定出这种情况。
算法流程：对于集合S中的每一结点s，逐步减小从源s到v的最短路径估计d[v]直至其到达实际最短路径的权。最多进行E-1次松弛操作。算法返回True当且仅当图中不存在负权圈。通过采用队列来实现。
SPFA算法的理论复杂度上界是$O(kE)$，其中k是算法执行过程中的常数系数。

测试：

测试数据	运行结果	运行时间
V=3000 的稀疏图	14	0.246s
V=5000 的稀疏图	28	0.277s
V=5000 的稠密图	4	3.565s

具体的数据和代码、运行机器配置见于附录2.

②最小生成树问题

问题描述：对于带权图G(V,E)，它的一颗生成树定义为满足如下要求的树状子图：它的点集为V，边集为E的子集。最小生成树是子图内全体边权和最小的生成树。

1. Kruskal算法$^{[1]}$$^{[2]}$

它的考虑是从边出发的，每一步尝试把所有剩余的边中权重最小的边加进来，如果会导致产生回路的话就放弃，然后尝试下一条边。具体步骤如下：
(1) 设最小生成树为T=(V, E)，设置边的集合E的初始状态为空集
(2) 将图G中的边按权值从小到大排好序
(3) 从小的开始依次选取，若选取的边使生成树T不形成回路，则把它并入E中，保留作为T的一条边；若选取的边使生成树形成回路，则将其舍弃
(4) 重复3直到E中包含n-1条边为止（n为顶点数）。最后的T即为最小生成树。
总结说来，Kruskal算法的核心思想是并查集+贪心。
记e=|E|，即图的边数，该算法的渐进复杂度为$O(eloge)$
测试：

测试数据	运行结果	运行时间
V=3000 的稀疏图	534422	2.474s
V=5000 的稀疏图	1831121	6.967s
V=5000 的稠密图	13212137	55.565s

2. Prim算法$^{[1]}$$^{[2]}$

它的考虑是基于顶点的，从起始顶点出发，每一步选择和已经建好的生成树相连的边中最小权重的边，这样就能把下一个顶点拉到生成树当中来。具体步骤如下：
(1) 设置一个顶点的集合V和一个边的集合E，V和E的初始状态均为空集
(2) 选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S
(3) 选取一条权值最小的边(X, Y)，其中X在S中，Y不在S中
(4) 将顶点Y加入集合S，边(X, Y)加入集合E
(5) 重复3、4，直到选取了n-1条边（n为顶点数）。最后的T=(V, E)即为最小生成树
总体说来，Prim算法是贪心思想。
记$n=|V|$，该算法的渐进复杂度为$O(n^2)$
测试：

测试数据	运行结果	运行时间
V=3000 的稀疏图	534422	2.474s
V=5000 的稀疏图	1831121	6.967s
V=5000 的稠密图	13212137	7.565s

可以得到，对于稠密图，用prim算法通常效果更好（这是由于prim算法的复杂度由图的点规模决定）

③网络流问题

问题描述：在一个有向图中，对每条边定义一个容量值。选取一个点为源点s，一个点为汇点t。定义可行流为：从s到t的流量，按照有向图的边进行分布，且不超过任意边的容量。在所有可行流中，流量最大的，称为最大流。
特别的，若对于每条边，另外定义了一个费用值，在所有可行流中，费用最小，在此基础上流量最大的，成为最小费用最大流。
求解网络流问题基于一个最核心的定理，称为“最大流最小割定理”：一个有向图的最大流量等于图的最小割集的容量和。
抽象理解：将整个图看作一个复杂的流量管道，管道的流量肯定由“横截面”最小的位置决定。图中的最小割集就代表着“横截面”最小的地方。

1. Dinic算法$^{[2]}$

Dinic算法的思想是分阶段地在层次网络中增广。它结合了广度优先遍历(BFS)与深度优先遍历(DFS)的优势，采用构造分层网络的方法可以较快找到最短增广路。它与最短增广路算法不同之处是：最短增广路每个阶段执行完一次BFS增广后，要重新启动BFS从源点Vs开始寻找另一条增广路；而在Dinic算法中，只需一次 DFS过程就可以实现多次增广。算法的具体步骤如下：
(1) 初始化容量网络和网络流；
(2) 构造残留网络和层次网络，若汇点不再层次网络中，则算法结束；
(3) 在层次网络中用一次DFS过程进行增广，DFS执行完毕，该阶段的增广也执行完毕；
(4) 转步骤(2)。
Dinic算法的理论复杂度上界为$O(n^2m)$
需要指出的是，尽管Dinic算法的理论复杂度较高，在实际运行中，它的运行效率往往比该上界好很多。根据相关文献：$^{[3]}$$^{[4]}$
可以证明，Dinic算法的时间复杂度的理论上界是$O(N^2M)$（N是结点数，M是边数），但实际上Dinic算法比这个理论上界好得多。如果所有边容量均为1，那么时间复杂度是$O(min(N^{0.67},M^{0.5})*M)$；对于二分图最大匹配这样的特殊图，时间复杂度是$O(N^{0.5}*M)$。
测试：
尽管有细致的算法上界分析，相比于前几个算法，Dinic的复杂度还是大得多，这里用更小规模的数据测试

测试数据	运行结果	运行时间
V=100 的稀疏图	165	2.474s
V=250 的稀疏图	199	2.967s
V=250 的稠密图	547	3.565s

④极大强连通分量问题

问题描述：有向图G(V,E)，它的强连通分量定义为G的一个子图，子图中任意两点v1,v2,在子图中都有v1到v2的路径，也有v2到v1的路径。所有G的强连通分量中的极大者，称为图的极大强连通分量。下面的算法用于给定有向图G，求解这样的极大强连通分量。
强连通分量的意义在于，这样的分量里的联通属性是直观的，只要在这样的分量里的点，一定互相联通。因此在实际处理中，这样的分量可以拓扑地“缩点”，即将强连通分量看成图中一个顶点，从而简化图。

1. Tarjan算法$^{[2]}$

算法的基本思想如下：
(1) 遍历一个点,指定一个唯一时间戳DFN[i]；指定该点向前追溯可追溯到的最老时间戳LOW[i]
(2) 枚举当前点所有边
　a.若DFN[j]=0表明未被搜索过,递归搜索之
　b.若DFN[j]不为0，则j被搜索过，这时判断j是否在栈中，且j的时间戳DFN[j]小于当前时间戳DFN[i]，可判定成环。将LOW[i]设定为DFN[j]
　c.若这个点LOW[i]和DFN[i]相等，说明这个节点是所有强连通分量的元素中在栈中最早的节点
(3) 弹栈，将这个强连通分量全部弹出，缩成点
Tarjan算法的理论时间复杂度上界是$O(n+m)$
测试：
使用同最短路，生成树算法相同的数据

测试数据	运行结果	运行时间
V=3000 的稀疏图	4	3.469s
V=5000 的稀疏图	5	6.178s
V=5000 的稠密图	4	7.321s

⑤拓扑排序问题

有向图G(V,E)，在代数意义下就是点集V和边集E基于某种拓扑关系得到的结构。则点集可以定义一个合理的全序：这个序列里包括G的所有非孤立点，且只出现一次。且对于E中任意边(e1,e2)，在序列里e1一定在e2之前。
从离散的角度上说，有向图赋予了V上一个偏序关系，拓扑排序则是根据E将偏序关系得出全序关系。基于此可以知道，对于强连通图G，拓扑序是唯一的，对于非强连通图，拓扑序不一定唯一。

1. Kahn算法$^{[5]}$

算法描述：
(1) 计算图中所有点的入度，把入度为0的点加入栈
(2) 如果栈非空：取出栈顶顶点a，输出该顶点值，删除该顶点; 从图中删除所有以a为起始点的边，如果删除的边的另一个顶点入度为0，则把它入栈
(3) 重复步骤（2）
如果图中还存在顶点，则表示图中存在环；否则输出的顶点就是一个拓扑排序序列。
算法复杂度为$O(n+m)$
测试：
使用同最短路，生成树算法相同的数据

测试数据	运行结果	运行时间
V=3000 的稀疏图	4	4.221s
V=5000 的稀疏图	5	5.972s
V=5000 的稠密图	4	8.221s

附录

所有测试在同一台计算机上进行，关键配置为：
CPU：Intel core i3 1.70GHZ
RAM：2G

附录1

Dijkstra算法代码（C++）

/* 
* 单源最短路径，Dijkstra算法，邻接矩阵形式，复杂度为O(n^2) 
* 求出源beg到所有点的最短路径，传入图的顶点数，和邻接矩阵cost[][] 
* 返回各点的最短路径lowcost[], 路径pre[].pre[i]记录beg到i路径上的父结点，pre[beg]=-1 
* 可更改路径权类型，但是权值必须为非负 * 
*/ 
const int MAXN=1010;
#define typec int const typec INF=0x3f3f3f3f;//防止后面溢出，这个不能太大 
bool vis[MAXN];
int pre[MAXN];
void Dijkstra(typec cost[][MAXN],typec lowcost[],int n,int beg)
{
    for(int i=0; i<n; i++)
    {
        lowcost[i]=INF;
        vis[i]=false;
        pre[i]=-1;
    }
    lowcost[beg]=0;
    for(int j=0; j<n; j++)
    {
        int k=-1;
        int Min=INF;
        for(int i=0; i<n; i++) 
            if(!vis[i]&&lowcost[i]<Min)
            {
                Min=lowcost[i];
                k=i;
            }
        if(k==-1)break;
        vis[k]=true;
        for(int i=0; i<n; i++) 
            if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i])
            {
                lowcost[i]=lowcost[k]+cost[k][i];
                pre[i]=k;
            }
    }
}
//测试样例为数千规模的矩阵，只打印出一部分
样例①
0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 5 0 0 0 11 0 0 0 0 0 6 0 0 12 0 0 0 0 14 0 0 0 0 0 0 0 0 0 10 0 0 9 0 0 2 0 4 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 4 0 0 5 0 0 0 0... ...
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
样例②
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 12 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 0 6 0 0 0 0 0 0 0 0 12 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0... ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
样例③
4 12 0 10 0 1 6 7 5 0 12 8 8 13 5 13 6 0 9 14 0 0 5 7 15 5 0 14 7 9 3 11 6 0 7 2 14 0 5 15 5 11 11 11 4 2 0 13 11 0 11 14 7 2 8 12 9 0 1 7 0 11 3 9 2 0 7 1 5 4 0 12 4 0 11 6 0 13 0 0 3 7 0 8 0 2 5 14 4 10 1 7 12 12 11 4 15 0 2 7 2 11 ......0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 

附录2

SPFA算法代码（C++）

/*
* 单源最短路SPFA 
* 时间复杂度 0(kE) 
* 这个是队列实现，有时候改成栈实现会更加快，很容易修改 
* 这个复杂度是不定的 
*/
const int MAXN=1010;
const int INF=0x3f3f3f3f;
struct Edge
{
    int v;
    int cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost) {}
};
vector<Edge>E[MAXN];
void addedge(int u,int v,int w)
{
    E[u].push_back(Edge(v,w));
}
bool vis[MAXN];//在队列标志
int cnt[MAXN];//每个点的入队列次数
int dist[MAXN];
bool SPFA(int start,int n)
{
    memset(vis,false,sizeof(vis));
    for(int i=1; i<=n; i++)dist[i]=INF;
    vis[start]=true;
    dist[start]=0;
    queue<int>que;
    while(!que.empty())que.pop();
    que.push(start);
    memset(cnt,0,sizeof(cnt));
    cnt[start]=1;
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=false;
        for(int i=0; i<E[u].size(); i++)
        {
            int v=E[u][i].v;
            if(dist[v]>dist[u]+E[u][i].cost)
            {
                dist[v]=dist[u]+E[u][i].cost;
                if(!vis[v])
                {
                    vis[v]=true;
                    que.push(v);
                    if(++cnt[v]>n)return false;     
                    //cnt[i]为入队列次数，用来判定是否存在负环回路
                }
            }
        }
    }
    return true;
}
//测试样例同上

附录3

Kruskal算法代码（C++）

/* 
* Kruskal算法求MST 
*/
const int MAXN=110;//最大点数
const int MAXM=10000;//最大边数
int F[MAXN];//并查集使用
struct Edge
{
    int u,v,w;
} edge[MAXM]; //存储边的信息，包括起点/终点/权值
int tol;//边数，加边前赋值为0
void addedge(int u,int v,int w)
{
    edge[tol].u=u;
    edge[tol].v=v;
    edge[tol++].w=w;
}
bool cmp(Edge a,Edge b)  //排序函数，讲边按照权值从小到大排序
{
    return a.w<b.w;
}
int find(int x)
{
    if(F[x]==-1)return x;
    else return F[x]=find(F[x]);
}
int Kruskal(int n)//传入点数，返回最小生成树的权值，如果不连通返回-1
{
    memset(F,-1,sizeof(F));
    sort(edge,edge+tol,cmp);
    int cnt=0;
//计算加入的边数
    int ans=0;
    for(int i=0; i<tol; i++)
    {
        int u=edge[i].u;
        int v=edge[i].v;
        int w=edge[i].w;
        int t1=find(u);
        int t2=find(v);
        if(t1!=t2)
        {
            ans+=w;
            F[t1]=t2;
            cnt++;
        }
        if(cnt==n-1)break;
    }
    if(cnt<n-1)return -1;//不连通
    else return ans;
}

附录4

Prim算法代码（C++）

/*
* Prim求MST
* 耗费矩阵cost[][]，标号从0开始，0~n-1
* 返回最小生成树的权值，返回-1表示原图不连通
*/ const int INF=0x3f3f3f3f;
const int MAXN=110;
bool vis[MAXN];
int lowc[MAXN];
int Prim(int cost[][MAXN],int n)//点是0~n-1
{
    int ans=0;
    memset(vis,false,sizeof(vis));
    vis[0]=true;
    for(int i=1; i<n; i++)lowc[i]=cost[0][i];
    for(int i=1; i<n; i++)
    {
        int minc=INF;
        int p=-1;
        for(int j=0; j<n; j++) if(!vis[j]&&minc>lowc[j])
            {
                minc=lowc[j];
                p=j;
            }
        if(minc==INF)return -1;//原图不连通
        ans+=minc;
        vis[p]=true;
        for(int j=0; j<n; j++) if(!vis[j]&&lowc[j]>cost[p][j]) lowc[j]=cost[p][j];
    }
    return ans;
}

附录5

Dinic算法代码（C++）

const int MAX=0x5fffffff;//
int tab[250][250];//邻接矩阵 
int dis[250];//距源点距离,分层图 
int q[2000],h,r;//BFS队列 ,首,尾 
int N,M,ANS;//N:点数;M,边数 
int BFS()
{
     int i,j;
     memset(dis,0xff,sizeof(dis));//以-1填充 
     dis[1]=0;
     h=0;r=1;
     q[1]=1;
     while (h<r)
     {
           j=q[++h];
           for (i=1;i<=N;i++)
               if (dis[i]<0 && tab[j][i]>0)
               {
                  dis[i]=dis[j]+1; 
                  q[++r]=i;
               }
     }
     if (dis[N]>0)
        return 1;
     else
        return 0;//汇点的DIS小于零,表明BFS不到汇点 
}
//Find代表一次增广,函数返回本次增广的流量,返回0表示无法增广 
int find(int x,int low)//Low是源点到现在最窄的(剩余流量最小)的边的剩余流量
{
    int i,a=0;
    if (x==N)return low;//是汇点 
    for (i=1;i<=N;i++)
    if (tab[x][i] >0 //联通 
     && dis[i]==dis[x]+1 //是分层图的下一层 
     &&(a=find(i,min(low,tab[x][i]))))//能到汇点(a <> 0) 
    {
       tab[x][i]-=a;
       tab[i][x]+=a;
       return a;
    }
    return 0;
}
/*
//数据
样例①
0 0 0 0 0 0 0 9 0 0 0 0 0 4 0 0 0 0 0 0 0 0 11 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 5 0 0 0 11 0 0 0 0 0 6 0 0 12 0 0 0 0 9 0 0 0 0 0 0 0 0 0 10 0 0 9 0 0 2 0 4 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 4 0 0 5 0 0 0 0... ...
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
样例②
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 12 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 0 6 0 0 0 0 0 0 0 0 12 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0... ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
样例③
4 12 0 10 0 1 6 7 5 0 12 8 8 13 5 13 6 0 9 14 0 0 5 7 15 5 0 14 7 9 3 11 6 0 7 2  2 0 13 11 0 11 14 7 2 8 12 9 0 1 7 0 11 3 9 2 0 7 1 5 4 0 12 4 0 11 6 0 13 0 0 3 7 0 8 0 2 5 14 4 10 1 7 12 12 11 4 15 0 2 7 2 11 ......0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 
*/

附录6

Tarjan算法代码（C++）

/*
* Tarjan算法
* 复杂度O(N+M)
*/
const int MAXN = 20010;//点数
const int MAXM = 50010;//边数
struct Edge
{
    int to,next;
} edge[MAXM];
int head[MAXN],tot;
int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~scc
int Index,top;
int scc;//强连通分量的个数
bool Instack[MAXN];
int num[MAXN];//各个强连通分量包含点的个数，数组编号1~scc
//num数组不一定需要，结合实际情况
void addedge(int u,int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
void Tarjan(int u)
{
    int v;
    Low[u] = DFN[u] = ++Index;
    Stack[top++] = u;
    Instack[u] = true;
    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        v = edge[i].to;
        if( !DFN[v] )
        {
            Tarjan(v);
            if( Low[u] > Low[v] )Low[u] = Low[v];
        }
        else if(Instack[v] && Low[u] > DFN[v]) Low[u] = DFN[v];
    }
    if(Low[u] == DFN[u])
    {
        scc++;
        do
        {
            v = Stack[--top];
            Instack[v] = false;
            Belong[v] = scc;
            num[scc]++;
        }
        while( v != u);
    }
}
void solve(int N)
{
    memset(DFN,0,sizeof(DFN));
    memset(Instack,false,sizeof(Instack));
    memset(num,0,sizeof(num));
    Index = scc = top = 0;
    for(int i = 1; i <= N; i++) if(!DFN[i]) Tarjan(i);
}
void init()
{
    tot = 0;
    memset(head,-1,sizeof(head));
}

附录7

Kahn算法代码（C++）

const int maxn = 505;  
struct node  
{  
    int v, next;  
}edge[maxn*maxn];  
int degree[maxn], head[maxn];  
queue<int> q;  
list<int> ans;   
int n, m, no;  
inline void init()  
{  
    no = 0;  
    while(!q.empty()) q.pop();  
    memset(degree, 0, sizeof degree);  
    memset(head, -1, sizeof head);  
}  
inline void add(int u, int v)  
{  
    edge[no].v = v;  
    edge[no].next = head[u];  
    head[u] = no++;  
}  
int Kahn()  
{  
    int count = 0;  
    while(!q.empty())  
    {  
        int tp = q.front(); q.pop();  
        ++count; ans.push_back(tp); //加入链表中，加入数组或者vector或者queue都无所谓   
        int k = head[tp];  
        while(k != -1)  
        {  
            --degree[edge[k].v];  
            if(!degree[edge[k].v]) q.push(edge[k].v);  
            k = edge[k].next;  
        }  
    }  
    if(count == n) return 1;  
    return 0;  
}  
int main()  
{  
    int u, v;  
    scanf("%d %d", &n, &m); init();  
    for(int i = 1; i <= m; ++i)  
    {  
        scanf("%d %d", &u, &v);  
        add(u, v); ++degree[v];  
    }  
    for(int i = 1; i <= n; ++i)  
    {  
        if(!degree[i]) q.push(i);  
    }  
    Kahn();  
    list<int>::iterator it;  
    for(it = ans.begin(); it != ans.end(); ++it)  
    {  
        cout << *it << " ";  
    }  
    cout << endl;  
    return 0;  
}  

参考文献

【1】教材编写组. 《运筹学》（第三版）. 清华大学出版社. 2008
【2】刘汝佳. 《算法竞赛入门经典》（第二版）. 清华大学出版社. 2009
【3】百度百科. Dinic算法. 2014
【4】王欣. 《浅谈基于分层思想的网络流算法》. 全国信息学冬令营论文组. 2007
【5】百度百科. Kahn算法. 2016