EdmondsKarp算法是Ford-Fulkerson算法的特例区别在于Ford-Fulkerson算法没有给出残存网络中增广路径的寻找方法而EdmondsKarp算法使用广度优先搜索寻找增广路径找到增广路径后沿其递增或递减流得到更大的流重复下去直到残存网络不存在增广路径为止具体见算法导论(第三版):26.2节算法实现如下(C)#includeiostream#includevector#includedequeusingnamespacestd;#includegraph.hconstintN6;size_t s0;size_t t5;vectorvectorintflow_function(N,vectorint(N,0));//流函数vectorvectorintcapacity{{0,16,13,0,0,0},{0,0,0,12,0,0},{0,4,0,0,14,0},{0,0,9,0,0,20},{0,0,0,7,0,4},{0,0,0,0,0,0}};//流网络每一条边的容量intmain(){GraphCf(N);//残存网络vectorpairsize_t,size_tinput{{0,1},{0,2},{1,3},{2,1},{2,4},{3,2},{3,5},{4,3},{4,5}};vectorvectorbooladj_matrix(N,vectorbool(N,false));//流网络的邻接矩阵vectorvectorintcapacity_f(N,vectorint(N,0));//残存网络中每条边的容量c(u,v)for(constautorun:input){adj_matrix[run.first][run.second]true;}for(size_t i0;iN;i){for(size_t j0;jN;j){if(adj_matrix[i][j]){capacity_f[i][j]capacity[i][j];if(capacity_f[i][j]!0){Cf.insertEdge(i,j);}}}}while(true)//广度优先搜索寻找残存网络中的由源点至汇点的增广路径{boolhas_find_pathfalse;vectorboolvisited(N,false);vectorlonglongpre(N,-1);dequesize_twork_queue;work_queue.push_back(s);visited[s]true;while(work_queue.empty()false){size_t curwork_queue.front();work_queue.pop_front();for(EdgeNode*runCf.getFirstEdge(cur);run!nullptr;runCf.nextEdge(run)){if(visited[run-vertex_id]false){pre[run-vertex_id]cur;visited[run-vertex_id]true;if(run-vertex_idt){has_find_pathtrue;break;}work_queue.push_back(run-vertex_id);}}if(has_find_path){break;}}if(has_find_pathfalse){break;}intCp-1;size_t runt;while(pre[run]!-1){if(Cp-1||Cpcapacity_f[pre[run]][run]){Cpcapacity_f[pre[run]][run];}runpre[run];}runt;while(pre[run]!-1)//沿增广路径递增流{if(adj_matrix[pre[run]][run]){if(flow_function[pre[run]][run]0){Cf.insertEdge(run,pre[run]);}flow_function[pre[run]][run]Cp;capacity_f[pre[run]][run]-Cp;if(capacity_f[pre[run]][run]0){Cf.deleteEdge(pre[run],run);}}else{if(flow_function[run][pre[run]]capacity[run][pre[run]]){flow_function[run][pre[run]]-Cp;Cf.insertEdge(run,pre[run]);capacity_f[run][pre[run]]Cp;}else{flow_function[run][pre[run]]-Cp;capacity_f[run][pre[run]]Cp;}if(flow_function[run][pre[run]]0){Cf.deleteEdge(pre[run],run);capacity_f[pre[run]][run]0;}else{capacity_f[pre[run]][run]flow_function[run][pre[run]];}}runpre[run];}}cout最大流为endl;for(size_t i0;iN;i)//输出最大流{for(size_t j0;jN;j){if(flow_function[i][j]!0){couti-j:flow_function[i][j]endl;}}}return0;}
