[关闭]
@skyword 2017-09-01T08:36:21.000000Z 字数 11328 阅读 2312

图论经典问题的几种算法


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

①最短路问题

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

1. Dijstra算法

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


相应地,定义稀疏度为:

易得稀疏度和稠密度都是中的有理数。
Dijkstra算法的理论时间复杂度上界是
测试: 给出以下几组测试样例
下面我们约定稀疏图是稀疏度的图,稠密图是稀疏度的图.

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

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

2. SPFA算法

SPFA算法用于解决单源最短路问题,其比dijstra算法优越在spfa算法可以在带负权边图中求解最短路。若图中有负权圈,则可能造成某点对最短路为-∞,spfa算法可以判定出这种情况。
算法流程:对于集合S中的每一结点s,逐步减小从源s到v的最短路径估计d[v]直至其到达实际最短路径的权。最多进行E-1次松弛操作。算法返回True当且仅当图中不存在负权圈。通过采用队列来实现。
SPFA算法的理论复杂度上界是,其中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) 设最小生成树为T=(V, E),设置边的集合E的初始状态为空集
(2) 将图G中的边按权值从小到大排好序
(3) 从小的开始依次选取,若选取的边使生成树T不形成回路,则把它并入E中,保留作为T的一条边;若选取的边使生成树形成回路,则将其舍弃
(4) 重复3直到E中包含n-1条边为止(n为顶点数)。最后的T即为最小生成树。
总结说来,Kruskal算法的核心思想是并查集+贪心。
记e=|E|,即图的边数,该算法的渐进复杂度为
测试:

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

2. Prim算法

它的考虑是基于顶点的,从起始顶点出发,每一步选择和已经建好的生成树相连的边中最小权重的边,这样就能把下一个顶点拉到生成树当中来。具体步骤如下:
(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算法是贪心思想。
,该算法的渐进复杂度为
测试:

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

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

③网络流问题

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

1. Dinic算法

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

算法的基本思想如下:
(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算法的理论时间复杂度上界是
测试:
使用同最短路,生成树算法相同的数据

测试数据 运行结果 运行时间
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算法

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

测试数据 运行结果 运行时间
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++)

  1. /*
  2. * 单源最短路径,Dijkstra算法,邻接矩阵形式,复杂度为O(n^2)
  3. * 求出源beg到所有点的最短路径,传入图的顶点数,和邻接矩阵cost[][]
  4. * 返回各点的最短路径lowcost[], 路径pre[].pre[i]记录beg到i路径上的父结点,pre[beg]=-1
  5. * 可更改路径权类型,但是权值必须为非负 *
  6. */
  7. const int MAXN=1010;
  8. #define typec int const typec INF=0x3f3f3f3f;//防止后面溢出,这个不能太大
  9. bool vis[MAXN];
  10. int pre[MAXN];
  11. void Dijkstra(typec cost[][MAXN],typec lowcost[],int n,int beg)
  12. {
  13. for(int i=0; i<n; i++)
  14. {
  15. lowcost[i]=INF;
  16. vis[i]=false;
  17. pre[i]=-1;
  18. }
  19. lowcost[beg]=0;
  20. for(int j=0; j<n; j++)
  21. {
  22. int k=-1;
  23. int Min=INF;
  24. for(int i=0; i<n; i++)
  25. if(!vis[i]&&lowcost[i]<Min)
  26. {
  27. Min=lowcost[i];
  28. k=i;
  29. }
  30. if(k==-1)break;
  31. vis[k]=true;
  32. for(int i=0; i<n; i++)
  33. if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i])
  34. {
  35. lowcost[i]=lowcost[k]+cost[k][i];
  36. pre[i]=k;
  37. }
  38. }
  39. }
  40. //测试样例为数千规模的矩阵,只打印出一部分
  41. 样例①
  42. 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... ...
  43. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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
  44. 样例②
  45. 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
  46. 样例③
  47. 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++)

  1. /*
  2. * 单源最短路SPFA
  3. * 时间复杂度 0(kE)
  4. * 这个是队列实现,有时候改成栈实现会更加快,很容易修改
  5. * 这个复杂度是不定的
  6. */
  7. const int MAXN=1010;
  8. const int INF=0x3f3f3f3f;
  9. struct Edge
  10. {
  11. int v;
  12. int cost;
  13. Edge(int _v=0,int _cost=0):v(_v),cost(_cost) {}
  14. };
  15. vector<Edge>E[MAXN];
  16. void addedge(int u,int v,int w)
  17. {
  18. E[u].push_back(Edge(v,w));
  19. }
  20. bool vis[MAXN];//在队列标志
  21. int cnt[MAXN];//每个点的入队列次数
  22. int dist[MAXN];
  23. bool SPFA(int start,int n)
  24. {
  25. memset(vis,false,sizeof(vis));
  26. for(int i=1; i<=n; i++)dist[i]=INF;
  27. vis[start]=true;
  28. dist[start]=0;
  29. queue<int>que;
  30. while(!que.empty())que.pop();
  31. que.push(start);
  32. memset(cnt,0,sizeof(cnt));
  33. cnt[start]=1;
  34. while(!que.empty())
  35. {
  36. int u=que.front();
  37. que.pop();
  38. vis[u]=false;
  39. for(int i=0; i<E[u].size(); i++)
  40. {
  41. int v=E[u][i].v;
  42. if(dist[v]>dist[u]+E[u][i].cost)
  43. {
  44. dist[v]=dist[u]+E[u][i].cost;
  45. if(!vis[v])
  46. {
  47. vis[v]=true;
  48. que.push(v);
  49. if(++cnt[v]>n)return false;
  50. //cnt[i]为入队列次数,用来判定是否存在负环回路
  51. }
  52. }
  53. }
  54. }
  55. return true;
  56. }
  57. //测试样例同上

附录3

Kruskal算法代码(C++)

  1. /*
  2. * Kruskal算法求MST
  3. */
  4. const int MAXN=110;//最大点数
  5. const int MAXM=10000;//最大边数
  6. int F[MAXN];//并查集使用
  7. struct Edge
  8. {
  9. int u,v,w;
  10. } edge[MAXM]; //存储边的信息,包括起点/终点/权值
  11. int tol;//边数,加边前赋值为0
  12. void addedge(int u,int v,int w)
  13. {
  14. edge[tol].u=u;
  15. edge[tol].v=v;
  16. edge[tol++].w=w;
  17. }
  18. bool cmp(Edge a,Edge b) //排序函数,讲边按照权值从小到大排序
  19. {
  20. return a.w<b.w;
  21. }
  22. int find(int x)
  23. {
  24. if(F[x]==-1)return x;
  25. else return F[x]=find(F[x]);
  26. }
  27. int Kruskal(int n)//传入点数,返回最小生成树的权值,如果不连通返回-1
  28. {
  29. memset(F,-1,sizeof(F));
  30. sort(edge,edge+tol,cmp);
  31. int cnt=0;
  32. //计算加入的边数
  33. int ans=0;
  34. for(int i=0; i<tol; i++)
  35. {
  36. int u=edge[i].u;
  37. int v=edge[i].v;
  38. int w=edge[i].w;
  39. int t1=find(u);
  40. int t2=find(v);
  41. if(t1!=t2)
  42. {
  43. ans+=w;
  44. F[t1]=t2;
  45. cnt++;
  46. }
  47. if(cnt==n-1)break;
  48. }
  49. if(cnt<n-1)return -1;//不连通
  50. else return ans;
  51. }

附录4

Prim算法代码(C++)

  1. /*
  2. * Prim求MST
  3. * 耗费矩阵cost[][],标号从0开始,0~n-1
  4. * 返回最小生成树的权值,返回-1表示原图不连通
  5. */ const int INF=0x3f3f3f3f;
  6. const int MAXN=110;
  7. bool vis[MAXN];
  8. int lowc[MAXN];
  9. int Prim(int cost[][MAXN],int n)//点是0~n-1
  10. {
  11. int ans=0;
  12. memset(vis,false,sizeof(vis));
  13. vis[0]=true;
  14. for(int i=1; i<n; i++)lowc[i]=cost[0][i];
  15. for(int i=1; i<n; i++)
  16. {
  17. int minc=INF;
  18. int p=-1;
  19. for(int j=0; j<n; j++) if(!vis[j]&&minc>lowc[j])
  20. {
  21. minc=lowc[j];
  22. p=j;
  23. }
  24. if(minc==INF)return -1;//原图不连通
  25. ans+=minc;
  26. vis[p]=true;
  27. for(int j=0; j<n; j++) if(!vis[j]&&lowc[j]>cost[p][j]) lowc[j]=cost[p][j];
  28. }
  29. return ans;
  30. }

附录5

Dinic算法代码(C++)

  1. const int MAX=0x5fffffff;//
  2. int tab[250][250];//邻接矩阵
  3. int dis[250];//距源点距离,分层图
  4. int q[2000],h,r;//BFS队列 ,首,尾
  5. int N,M,ANS;//N:点数;M,边数
  6. int BFS()
  7. {
  8. int i,j;
  9. memset(dis,0xff,sizeof(dis));//以-1填充
  10. dis[1]=0;
  11. h=0;r=1;
  12. q[1]=1;
  13. while (h<r)
  14. {
  15. j=q[++h];
  16. for (i=1;i<=N;i++)
  17. if (dis[i]<0 && tab[j][i]>0)
  18. {
  19. dis[i]=dis[j]+1;
  20. q[++r]=i;
  21. }
  22. }
  23. if (dis[N]>0)
  24. return 1;
  25. else
  26. return 0;//汇点的DIS小于零,表明BFS不到汇点
  27. }
  28. //Find代表一次增广,函数返回本次增广的流量,返回0表示无法增广
  29. int find(int x,int low)//Low是源点到现在最窄的(剩余流量最小)的边的剩余流量
  30. {
  31. int i,a=0;
  32. if (x==N)return low;//是汇点
  33. for (i=1;i<=N;i++)
  34. if (tab[x][i] >0 //联通
  35. && dis[i]==dis[x]+1 //是分层图的下一层
  36. &&(a=find(i,min(low,tab[x][i]))))//能到汇点(a <> 0)
  37. {
  38. tab[x][i]-=a;
  39. tab[i][x]+=a;
  40. return a;
  41. }
  42. return 0;
  43. }
  44. /*
  45. //数据
  46. 样例①
  47. 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... ...
  48. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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
  49. 样例②
  50. 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
  51. 样例③
  52. 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
  53. */

附录6

Tarjan算法代码(C++)

  1. /*
  2. * Tarjan算法
  3. * 复杂度O(N+M)
  4. */
  5. const int MAXN = 20010;//点数
  6. const int MAXM = 50010;//边数
  7. struct Edge
  8. {
  9. int to,next;
  10. } edge[MAXM];
  11. int head[MAXN],tot;
  12. int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~scc
  13. int Index,top;
  14. int scc;//强连通分量的个数
  15. bool Instack[MAXN];
  16. int num[MAXN];//各个强连通分量包含点的个数,数组编号1~scc
  17. //num数组不一定需要,结合实际情况
  18. void addedge(int u,int v)
  19. {
  20. edge[tot].to = v;
  21. edge[tot].next = head[u];
  22. head[u] = tot++;
  23. }
  24. void Tarjan(int u)
  25. {
  26. int v;
  27. Low[u] = DFN[u] = ++Index;
  28. Stack[top++] = u;
  29. Instack[u] = true;
  30. for(int i = head[u]; i != -1; i = edge[i].next)
  31. {
  32. v = edge[i].to;
  33. if( !DFN[v] )
  34. {
  35. Tarjan(v);
  36. if( Low[u] > Low[v] )Low[u] = Low[v];
  37. }
  38. else if(Instack[v] && Low[u] > DFN[v]) Low[u] = DFN[v];
  39. }
  40. if(Low[u] == DFN[u])
  41. {
  42. scc++;
  43. do
  44. {
  45. v = Stack[--top];
  46. Instack[v] = false;
  47. Belong[v] = scc;
  48. num[scc]++;
  49. }
  50. while( v != u);
  51. }
  52. }
  53. void solve(int N)
  54. {
  55. memset(DFN,0,sizeof(DFN));
  56. memset(Instack,false,sizeof(Instack));
  57. memset(num,0,sizeof(num));
  58. Index = scc = top = 0;
  59. for(int i = 1; i <= N; i++) if(!DFN[i]) Tarjan(i);
  60. }
  61. void init()
  62. {
  63. tot = 0;
  64. memset(head,-1,sizeof(head));
  65. }

附录7

Kahn算法代码(C++)

  1. const int maxn = 505;
  2. struct node
  3. {
  4. int v, next;
  5. }edge[maxn*maxn];
  6. int degree[maxn], head[maxn];
  7. queue<int> q;
  8. list<int> ans;
  9. int n, m, no;
  10. inline void init()
  11. {
  12. no = 0;
  13. while(!q.empty()) q.pop();
  14. memset(degree, 0, sizeof degree);
  15. memset(head, -1, sizeof head);
  16. }
  17. inline void add(int u, int v)
  18. {
  19. edge[no].v = v;
  20. edge[no].next = head[u];
  21. head[u] = no++;
  22. }
  23. int Kahn()
  24. {
  25. int count = 0;
  26. while(!q.empty())
  27. {
  28. int tp = q.front(); q.pop();
  29. ++count; ans.push_back(tp); //加入链表中,加入数组或者vector或者queue都无所谓
  30. int k = head[tp];
  31. while(k != -1)
  32. {
  33. --degree[edge[k].v];
  34. if(!degree[edge[k].v]) q.push(edge[k].v);
  35. k = edge[k].next;
  36. }
  37. }
  38. if(count == n) return 1;
  39. return 0;
  40. }
  41. int main()
  42. {
  43. int u, v;
  44. scanf("%d %d", &n, &m); init();
  45. for(int i = 1; i <= m; ++i)
  46. {
  47. scanf("%d %d", &u, &v);
  48. add(u, v); ++degree[v];
  49. }
  50. for(int i = 1; i <= n; ++i)
  51. {
  52. if(!degree[i]) q.push(i);
  53. }
  54. Kahn();
  55. list<int>::iterator it;
  56. for(it = ans.begin(); it != ans.end(); ++it)
  57. {
  58. cout << *it << " ";
  59. }
  60. cout << endl;
  61. return 0;
  62. }

参考文献

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注