网络流问题如下左图所示，有一个顶点s，称为源点（source）；还有一个顶点t，称为汇点（sink）。对于顶点c，它最大流出2，因此它的最大流入为2，如下右图所示。而t的最大流也就是5。
要想计算最大流，同样可是使用前面的思想——分阶段进行。令开始时所有边都没有流，如下中间图所示。我们可以用残余图（residual graph）来表示对于每条边还能再添加上多少流。对于每一条边，可以从容量中减去当前的流而计算出残留的流。
第一步：假设我们选择s−b−d−t路径，此时会发出2个单位的流通过这条路径的每一边，如下中间图所示。对比左图，我们做如下约定：一旦注满（使饱和）一条边，例如a到b和b到d，就将这条边从残余图（也就是中间图）去掉，如下右图所示。
第二步：接下来选择s−a−c−t路径，此时也会发出2个单位的流通过这条路径的每一边，如下中间图所示（只看s−a−c−t即可，s−b−d−t为上一步说走过的路径）。同样将残余图更新如下右图所示。
第三步：从上图的残余图中我们已经可以看出来最后一步的唯一一种走法了，也就是从s−a−d−t。做如下图所示更新。
很显然从t无法走到s，因此算法至此便终止了。因此正好5个单位的流是最大值。前面的三步我们走的如此顺利，那么问题真的如此简单么？
如果一开始我们选择了s−a−d−t，那么算法就会失败了，因为路已经被堵死了。
为了使算法得以成功运作，那么就要让流图中具有以相反方向发送流的路径，如下所示。那么对于如下右图中的残余图而言，从d返回到a的便成了3而非4，这是因为从t流到d的流量是3个单位。现在在残余图中就有a和d之间有2个方向，或者还有1个单位的流可以从a导向d，或者是3个单位的流导向相反的反向，当然，我们也可以撤销流。
紧接着如果通过d到a导入2个单位的流，算法就会从边（a，d）取走2个单位的流，更新流图如下。
思考：找出下面网络中的一个拓扑排序以及最大流。
活动网络AOV网络除了一些不能再简单的工程外，所有的工程都可以划分为若干个成为活动（activities）的子工程。比如说大学的课程，得修完了大学英语1才能修大学英语2，也得修完了高等数学才能修线性代数、概率论、离散数学等。将这些作为顶点标记为图时，它便是一个有向图。
顶点表示活动的网（activity on vertex network）或AOV网，是用顶点表示活动或任务，边表示活动或任务之间的优先关系的有向图G。在AOV网络G中，当且仅当从顶点i到j存在一条有向路径，则顶点i称为顶点j的前驱（predecessor）；当且仅当<i,j>是G中的一条边，则称顶点i为顶点j的直接前驱（immediate predecessor）。如果顶点i是顶点j的前驱，则称顶点j为顶点i的后继（successor）；如果顶点i是顶点j的直接前驱，则称顶点j为顶点i的直接后继。
拓扑排列是由有向图中所有顶点形成一个线性序列，对图中任意两个顶点i和j，如果顶点i是顶点j的前驱，则顶点i在拓扑序列中排在顶点j的前面。
我们在前面已经介绍了拓扑排序，这里给出它的伪代码。
for(i=0;i<n;i++) { if every vertex has a predecessor { fprintf(stderr,"Network has a cycle.n"); exit(1); } pick a vertex v that has no predecessors; output v; delete v and all edges leading out of v from the netwok; }对于拓扑排序问题，所需的操作主要有：
1）判断顶点是否有前驱；
2）删除顶点和关联于该顶点的所有边。
在操作1中，我们可以在每个顶点中都保存其直接前驱个数的计数。对于操作2，可以使用前面介绍过的邻接表来表示AOV网络。于是可以将其实现为以下C代码：
// 声明 typedef struct node *node_pointer; typedef struct node { int vertex; node_pointer link; }; typedef struct { int count; node_pointer link; }hdnodes; hdnodes graph[MAX_VERTICES]; // 函数 void topsort(hdnodes graph[],int n) { int i,j,k,top; node_pointer ptr; top=-1; for(i=0;i<n;i++) { if(!graph.count) { graph.count=top; top=i; } } for(i=0;i<n;i++) { if(top==-1) { fprintf(stderr,"nNetwork has a cycle. Sort terminated.n"); exit(1); } else { j=top; top=graph[top].count; printf("v%d, ",j); for(ptr=graph[j].link;ptr;ptr=ptr->link) { k=ptr->vertex; graph[k].count--; if(!graph[k].count) { graph[k].count=top; top=k; } } } } } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
在topsort的声明中，count域用来保存顶点的入度，而link域则是指向邻接表首结点的指针。邻接表中的每个结点又包含了两个域：vertex和link。在输入时，可以方便地设置count域的值。当输入一条边<i,j>时，顶点j的count就会加1。用一个栈来保存count值为0的顶点序列。当然也可以使用队列，但栈更容易实现。由于在count域减至0以后，count域就没有用了，所以通过头结点的count域把栈中的各个结点链接起来。
对于topsort的分析：对于具有n个顶点和e条边的AOV网络，第一个for循环的时间开销为O(n)。而第二个for循环执行n次。if子句在常数时间内完成；else子句中的for循环时间开销为O(di)，其中di是顶点i的出度。由于这个循环会在每个顶点输出时执行一次，所以总时间为：
O((∑n−1i=odi)+n)=O(e+n)
因此这个算法的渐进时间为O(e+n)，与问题的规模呈线性关系。 |
