17-伪代码详解

7.3.4　伪代码详解

（1）找可增广路

采用普通队列实现对残余网络的广度搜索。从源点u（u=s）开始，搜索u的邻接点v。如果v未被访问，则标记已访问，且记录v结点的前驱为u；如果u结点不是汇点则入队；如果u结点恰好是汇点，则返回，找到汇点时则找到一条可增广路。如果队列为空，则说明已经找不到可增广路。

bool bfs(int s,int t)
{
     memset(pre,-1,sizeof(pre)); 
     memset(vis,false,sizeof(vis)); 
     queue<int>q;
     vis[s]=true;
     q.push(s);
     while(!q.empty())
     {
          int now=q.front();
          q.pop();
          for(int i=1;i<=n; i++)            //寻找可增广路
          {
               if(!vis[i]&&g[now][i]>0)     //未被访问且有边相连
               {
                      vis[i] = true;
                      pre[i] = now;
                      if(i==t)  return true;//找到一条可增广路
                      q.push(i);
               }
          }
     }
     return false;                          //找不到可增广路
}

（2）沿可增广路增流

根据前驱数组，从汇点向前，一直到源点，找可增广路上所有边的最小值，即为可增量 d。然后从汇点向前，一直到源点，残余网络中同向（与可增广路同向）边减流，反向边增流；实流网络中如果是反向边，则减流，否则正向边增流。

int EK(int s, int t) 
{
     int v,w,d,maxflow; 
     maxflow = 0; 
     while(bfs(s,t))                        //可以增广
     {
          v=t; 
          d=INF;
          while(v!=s)                       //找可增量d
          {
               w=pre[v];                    //w记录v的前驱
               if(d>g[w][v])
                    d=g[w][v];
               v=w;
          }
          maxflow+=d;
          v=t;
          while(v!=s)                       //沿可增广路增流
          {
               w=pre[v];
               g[w][v]-=d;   //残余网络中正向边减流
               g[v][w]+=d;   //残余网络中反向边增流
               if(f[v][w]>0) //实流网络中如果是反向边,则减流,否则正向边增流
                     f[v][w]-=d;
               else
                     f[w][v]+=d;
               v=w;
           }
     }
     return maxflow; 
}