第十章圖和網(wǎng)絡問題

第十章圖和網(wǎng)絡問題10.1圖的遍歷10.2網(wǎng)絡流10.3二分圖的最大匹配問題10.1圖的遍歷圖的遍歷：從圖的某個頂點出發(fā)，沿著與頂點相關聯(lián)的邊，訪問圖中的所有頂點各一次。兩種方法：深度優(yōu)先搜索和廣度優(yōu)先搜索。10.1圖的遍歷10.1.1圖的深度優(yōu)先搜索遍歷10.1.2圖的廣度優(yōu)先搜索遍歷10.1.3無向圖的接合點10.1.4有向圖的強連通分支10.1.1圖的深度優(yōu)先搜索遍歷一、深度優(yōu)先搜索（DepthFirstSearch）的思想方法二、數(shù)據(jù)結構三、深度優(yōu)先搜索算法的步驟四、算法實現(xiàn)五、樹邊和后向邊六、時間復雜性七、空間復雜性一、思想方法令G=(V,E)是一個有向圖或無向圖。1、開始時，圖G中的所有頂點都標記為未訪問過。2、從G中任選一點u∈V作為初始出發(fā)點，訪問出發(fā)點u，把它標記為訪問過，3、從u出發(fā)，搜索u的下一個鄰接頂點v；4、若v未被訪問過，把它標記為訪問過，并把v作為新的出發(fā)點u，轉3，繼續(xù)遞歸地進行深度優(yōu)先搜索。5、若v已被訪問過，重新從u出發(fā)，選擇另一個未經(jīng)搜索過的鄰接頂點w，并w把作為新的出發(fā)點u，轉3，繼續(xù)遞歸地進行深度優(yōu)先搜索。6、若u的所有頂點v都已訪問過，就從u回溯到之前的頂點。如果u是初始出發(fā)點，則結束搜索過程。二、數(shù)據(jù)結構1、用圖的鄰接表來表示圖中各頂點及其關聯(lián)邊之間的關系：structadj_list{ /*鄰接表結點的數(shù)據(jù)結構*/int v; /*鄰接頂點的編號*/structadj_list*next; /*下一個鄰接頂點*/};typedefstructadj_listNODE;NODE node[n]; /*圖的鄰接表*/二、數(shù)據(jù)結構2、用兩個數(shù)組，來登記各個頂點在遍歷中被訪問的順序號：int pren[n]; /*相應頂點的前序遍歷的順序號*/int postn[n]; /*相應頂點的后序遍歷的順序號*/int tra[n]; /*按遍歷順序存放的頂點序號*/三、深度優(yōu)先搜索算法的步驟1.把所有頂點標記為未訪問過；2.令i=0；3.若頂點I未訪問過，則調用dfs(i)，進行深度優(yōu)先搜索；4.i=i+1；若i<n轉3；否則，算法結束；對于函數(shù)dfs(i)，則步驟如下：1.把頂點i標記為訪問過；使指針p初始化為頂點的鄰接表的首元素；2.若p指針為空，函數(shù)運行結束；否則取該指針所指向的元素，設該元素頂點編號為v；3.若頂點v已訪問過，則不作處理；否則，調用dfs(v)；4.使指針p指向下一個鄰接頂點，轉2；四、算法實現(xiàn)

1.voidtraver_dfs(NODEnode[],intn,intpren[],intpostn[],inttra[])2.{3.inti,prefdn,postfdn,count;4.BOOL*b=newBOOL[n];5.prefdn=0;postfdn=0;count=0;6.for(i=;i<n;i++)7.b[i]=FALSE;8.for(i=0;i<n;i++)9.if(!b[i])10.dfs(i,node,n,pren,postn,b,prefdn,postfdn,tra,count);11.deleteb;12.}

1.voiddfs(intv,NODEnode[],intn,intpren[],intpostn[],BOOLb[],int&prefdn,int&postfdn,inttra[],int&count)2.{3.NODE*p;4.b[v]=TRUE;tra[count++]=v;5.pren[v]=++prefdn;6.p=node[v].next;7.while(p!=NULL){8.if(!b[p->v])9.dfs(p-v,node,n,pren,postn,b,prefdn,postfdn,tra,count);10.p=p->next11.}12.postn[v]=++postfdn;13.}五、樹邊和后向邊1、是無向圖：樹邊（Treeedges）：深度優(yōu)先搜索生成樹中的邊。如果在搜索時，邊(u,v)∈E是從頂點出發(fā)進行搜索的邊，而頂點v尚未被訪問過，則邊(u,v)就是圖中的樹邊，它是生成樹中的一條邊。后向邊（Backedges）：其它的所有邊。例一個無向圖的深度優(yōu)先搜索遍歷的情況。五、樹邊和后向邊2、有向圖：樹邊（Treeedges）：深度優(yōu)先搜索生成樹中的邊。在搜索時，邊(u,v)∈E是從頂點u出發(fā)進行搜索的邊，而頂點v尚未被訪問過，則邊(u,v)就是樹邊，是生成樹中的一條邊。后向邊（Backedges）：與邊(u,v)相關聯(lián)的頂點u和v，在深度優(yōu)先搜索樹中，v是u的祖先；在從u出發(fā)沿著邊(u,v)進行搜索時，v已標記為訪問過。前向邊（Forwardedges）：與邊(u,v)相關聯(lián)的頂點u和v，在深度優(yōu)先搜索樹中，u是v的祖先；在從u出發(fā)沿著邊(u,v)進行搜索時，v已標記為訪問過。交叉邊（Crossedges）：其它的所有邊。例一個有向圖的深度優(yōu)先搜索遍歷的情況六、時間復雜性假定圖有n個頂點和m條邊算法traver_dfs的花費時間：第6~7行，把頂點的訪問標記初始化為FALSE，需花費

Θ(n)時間第8~10行執(zhí)行for循環(huán)測試頂點是否被訪問過，共花費Θ(n)時間，調用函數(shù)dfs進行遍歷所花費的時間。函數(shù)dfs的花費時間:登記n個頂點的訪問標記需Θ(n)時間；按鄰接表判斷鄰接頂點是否被訪問過，共有m條邊，鄰接表登記項有m個。因此，用于函數(shù)dfs的總花費是Θ(n+m)算法總的花費時間：

Θ(n+m)。當m=O(n2)時，算法總的花費時間是O(n2)。七、空間復雜性存放作為輸入用的鄰接表需要Θ(m)=O(n2)的空間用于存放頂點的遍歷順序號和登記頂點的訪問標志，需要Θ(n)的工作空間。10.1.2圖的廣度優(yōu)先搜索遍歷一、思想方法二、數(shù)據(jù)結構三、廣度優(yōu)先搜索算法的步驟四、算法實現(xiàn)五、復雜性分析一、思想方法廣度優(yōu)先搜索（BreadthFirstSearch）的思想方法1、從圖中選擇一個頂點v作為初始出發(fā)點，2、首先訪問出發(fā)點v，然后訪問v的所有鄰接點w1，…wi3、接著依次訪問與w1，…wi相鄰接的、未曾訪問過的所有頂點。4、依此類推，直到與初始頂點存在通路的所有頂點都已全部訪問完畢為止。二、數(shù)據(jù)結構1、圖的鄰接表structadj_list{ /*鄰接表結點的數(shù)據(jù)結構*/int v; /*鄰接頂點的編號*/structadj_list*next; /*下一個鄰接頂點*/};typedefstructadj_listNODE;NODE node[n]; /*圖的鄰接表*2、先進先出搜索隊列typedefstruct{NODE *head; /*隊列的頭指針*/NODE *tair; /*隊列的尾指針*/}QUEUE;三、廣度優(yōu)先搜索算法的步驟1.把所有頂點標記為未訪問過；2.令i=0；3.若頂點I未訪問過，則調用bfs(i)，進行廣度優(yōu)先搜索；4.i=i+1；若i<n轉3；否則，算法結束；三、廣度優(yōu)先搜索算法的步驟函數(shù)bfs(i)步驟如下：1.把頂點i標記為訪問過，建立頂點i的待搜索元素，把其放入搜索隊列尾巴；2.若搜索隊列為空，函數(shù)運行結束；否則取下隊首元素，設該元素頂點編號為v；3.對頂點v的所有鄰接頂點w，若w已訪問過，則不作處理；否則，把w標記為訪問過；建立頂點w的待搜索元素，把其放入搜索隊列尾巴；繼續(xù)對頂點v的其它鄰接頂點w作上述處理；若頂點v的所有鄰接頂點已處理完，轉2；例對圖10.3(a)采用廣度優(yōu)先搜索遍歷生成的樹四、算法實現(xiàn)

1、隊列的幾種基本操作：初始化隊列

voidinitial_Q(QUEUE&queue)；把元素放入隊列尾巴

voidappend_Q(QUEUE&queue，NODE*node)；取下隊首元素

NODE*delete_Q(QUEUE&queue)；判斷隊列是否為空 BOOLempty_Q(QUEUEqueue)； 2、圖的廣度優(yōu)先搜索遍歷算法的實現(xiàn)1.voidtraver_bfs(NODEnode[],intn,intbfn[])2.{3.inti,count=0;4.QUEUEqueue;5.BOOL*b=newBOOL[n];6.initial_Q(queue); /*初始化結點隊列*/7.for(i=0;i<n;i++) /*把所有頂點標記為未訪問過*/8.b[i]=FALSE;9.for(i=0;i<n;i++) /*從頂點0開始進行廣度優(yōu)先搜索*/10.if(!b[i])11.bfs(i,node,n,queue,bfn,count);12.deleteb;13.}

1.voidbfs(intv,NODEnode[],intn,QUEUE&queue,intbfn[],int&count)2.{3.intw;4.NODE*p1,*p=newNODE;/*建立待搜索頂點隊列元素*/5.p->v=v; /*賦予待搜索隊列元素頂點編號*/6.append_Q(queue,p);/*把該元素放到搜索隊列尾巴*/7.b[v]=TRUE; /*把該頂點標記為訪問過*/8.bnf[v]=count++; /*登記頂點的遍歷順序號*/9.while(!(empty(queue)){ /*搜索隊列非空?*/10.p=delete_Q(queue); /*取下搜索隊列的隊首元素*/11.w=p->v; /*該元素的頂點編號保存于w*/12.deletep; /*刪去該元素*/13.p1=node[w].next; /*取該頂點的鄰接表指針于p1*/14.while(p1!=NULL){ /*該頂點的鄰接頂點處理完?*/15.if(!b[p1->v]){ /*若鄰接頂點未訪問過*/16.b[p1->v]=TRUE; /*把該頂點標記為訪問過*/17.bfn[p1->v]=count++; /*登記頂點的遍歷順序號*/17.p=newNODE; /*建立一個待搜索的隊列元素*/18.p->v=p1->v; /*賦予該元素的頂點編號*/19.append_Q(queue,p); /*把該元素放到搜索隊列尾巴*/20.}21.p1=p1->next; /*準備處理下一個鄰接頂點*/22.}23.}24.}五、復雜性分析1、時間復雜性：假定圖具有個n頂點和m條邊1）算法traver_bfs：第5~6行把頂點的訪問標記初始化為False，需Θ(n)時間第7行開始的for循環(huán)，執(zhí)行n個判斷，需Θ(n)時間如果圖有k個連通分支，則執(zhí)行k次bfs調用2）函數(shù)bfs：隊列的各個操作均花費Θ(1)時間在k次bfs的調用中，共執(zhí)行n個頂點的入隊和出隊操作因為有m條邊，共需執(zhí)行2m個鄰接頂點的判斷處理工作。則算法的運行時間為Θ(n+m)。當m=O(n2)時，算法總的花費時間是O(n2)。五、復雜性分析2、空間復雜性：算法存放作為輸入用的鄰接表需要的m=O(n2)空間用于存放頂點的遍歷順序號和登記頂點的訪問標志，以及頂點的搜索隊列所需的工作單元，需要的Θ(n)工作空間。10.1.3無向圖的接合點一、接合點的概念二、尋找接合點的思想方法三、尋找無向圖的接合點的步驟四、算法的實現(xiàn)五、復雜性分析一、接合點的概念1、接合點的定義：定義10.1圖G=<V,E>是連通圖，頂點集SE，若刪去S中的所有頂點，將使圖G不連通，S就稱是圖G的割集。若S={v}，則稱v為圖G的割點（cut_nodes）或接合點（articulationpoint）。2、接合點的性質：性質1：當且僅當深度優(yōu)先搜索樹的根結點至少有兩個以上兒子，則根結點是接合點。性質2：當且僅當深度優(yōu)先搜索樹中，v的每一個兒孫結點不能通過后向邊到達v的祖先結點，則結點v是接合點二、尋找接合點的思想方法

1、進行深度優(yōu)先搜索時，對每個頂點v∈E，維護兩個變量pren[n]，及backn[n]pren[n]：頂點的遍歷順序號，即深度優(yōu)先搜索算法中的prefdn，每一次調用深度優(yōu)先搜索過程、訪問某個頂點時，該值加1；backn[n]：頂點v的后向可達頂點的最小遍歷順序號二、尋找接合點的思想方法

2、變量pren[n]，及backn[n]的維護開始時，backn[n]初始化為pren[n]，在深度優(yōu)先搜索過程中，若(v,w)是從頂點v出發(fā)進行搜索的邊，令backn[v]是下列數(shù)值中之最小者：pren[v]；pren[w]，若(v,w)是后向邊；backn[w]，若(v,w)是樹邊； 3、只要頂點v有一個兒子w，使得backn[w]≥pren[v]，說明v的兒孫w不能通過后向邊到達v的祖先，因此v是接合點。例如，在圖10.4中，以w為根的子樹不能通過后向邊到達v，使得backn[w]≥pren[v]成立，因此，在圖10.4中，v是接合點。三、尋找無向圖的接合點的步驟：

令root是開始搜索的頂點；所有頂點標記為未訪問過；調用artdfs從v開始進行搜索。artdfs的搜索步驟如下：1.把v標記為訪問過，初始化pren[v]、backn[v]；使指針p指向v的鄰接表登記項；2.若p為空，處理搜索到的接合點的計數(shù)和登記，算法結束；否則，令p所指向的鄰接點是w；若(v,w)是樹邊，轉3；否則轉5；三、尋找無向圖的接合點的步驟：

3.遞歸調用artdfs對w進行搜索，若v是根結點，按性質1判斷v是否為接合點；否則，更新v的后向可達頂點的遍歷順序號，按性質2判斷v是否為接合點；4.使p指向下一個鄰接點，轉2；5.若(v,w)是后向邊，更新v的后向可達頂點的遍歷順序號，轉4；四、算法的實現(xiàn)：

1.intart_point(NODEnode[],intn,intart[],introot)2.{3.inti,prefdn,count,degree;4.BOOL*b=newBOOL[n];5.int*pren=newint[n];6.int*backn=newint[n];7.prefdn=0;count=0;degree=0; 8.for(i=;i<n;i++)9.b[i]=FALSE;10.artdfs(root,node,pren,backn,b,prefdn,art,count,root,degree);11.deleteb;deletepren;deletebackn;12.returncount;13.}

1.voidartdfs(intv,NODEnode[],intpren[],intbackn[],BOOLb[],int&prefdn,intart[],int&count,introot,int°ree)2.{3.intw;4.BOOLartpoint=FALSE;5.NODE*p=node[v].next; /*把v標記為訪問過,初始化pren,backn*/6.b[v]=TRUE;pren[v]=++prefdn;backn[v]=prefdn;

7.while{p!=NULL}{ /*v的所有鄰接頂點處理完畢?*/8.w=p->v; /*處理v的鄰接頂點w*/9.if(!b[w]){ /*(v,w)為樹邊，對w進行深度優(yōu)先搜索*/10.artdfs(w,node,pren,backn,b,prefdn,art,count,root,degree); 11.if(v==root){ /*v是根結點?*/12.degree++; /*根結點的度增1*/13.if(degree>=2) /*若根結點的度大于等于2*/14.artpoint=TRUE; /*則根結點是接合點*/15.}16.else{ /*處理v后向可達的頂點*/17.backn[v]=min(backn[v],backn[w]);18.if(backn[w]>=pren[v])artpoint=TRUE;19.} /*w后向可達的頂點至多是v*/20.} /*則v是接合點*/21.else/*(v,w)是后向邊,更新v的后向可達頂點的遍歷順序號*/22.backn[v]=min(backn[v],pren[w]);23.p=p->next; /*處理下一個鄰接頂點*/24.}25.if(artpoint){ /*如果v是接合點,則登記于art*/26.count++;art[count]=v;27.}28.}例在圖10.5(a)中尋找接合點

五、復雜性分析1、時間復雜性：artdfs函數(shù)除增加處理和判斷接合點的代碼外，其余與dfs函數(shù)的工作過程一樣。處理和判斷接合點的代碼的運行時間為Θ(1)時間。因此，算法仍然是時間Θ(n+m)。當m=O(n2)時，算法總的花費時間是O(n2)。2、空間復雜性：存放作為輸入用的鄰接表需Θ(m)=O(n2)的空間存放頂點的遍歷順序號、后向可達頂點的最小遍歷順序號、登記頂點的訪問標志、及圖的接合點序號等所需的工作單元，需要Θ(n)的工作空間。10.1.4有向圖的強連通分支一、強連通分支的概念二、尋找強連通分支的步驟三、數(shù)據(jù)結構四、算法的實現(xiàn)五、復雜性分析一、強連通分支的概念1、強連通圖的定義：給定有向圖G=(V,E)，圖中任意兩個頂點u∈V,v∈V，若u和v互相可達，則稱圖G是強連通圖。2、強連通分支的定義：有向圖的極大強連通子圖稱為強連通分支。3、強連通分支的特點：有向圖G的強連通分支是一個最大的頂點集合，在這個集合中，每一對頂點之間都有路徑可達。二、尋找強連通分支的步驟尋找圖中每一對頂點之間都有路徑可達的所有頂點集合，1.對G執(zhí)行深度優(yōu)先搜索，求出每個頂點的后序遍歷順序號postn；2.反轉有向圖G中的邊，構造一個新的有向圖G*；3.由最高postn編號的頂點開始，對G*執(zhí)行深度優(yōu)先搜索。如果深度優(yōu)先搜索未達到所有頂點，由未訪問的最高postn編號的頂點開始，繼續(xù)深度優(yōu)先搜索；4.第3步所產(chǎn)生的森林中的每一棵樹，對應于一個強連通分支。例求圖10.6(a)所示有向圖的強連通子圖三、數(shù)據(jù)結構1、用圖的鄰接表來表示圖中各頂點及其關聯(lián)邊之間的關系：structadj_list{ /*鄰接表結點的數(shù)據(jù)結構*/int v; /*鄰接頂點的編號*/structadj_list*next; /*下一個鄰接頂點*/};typedefstructadj_listNODE;NODE node[n]; /*圖的鄰接表*/2、用兩個數(shù)組，來登記各個頂點在遍歷中被訪問的順序號：int pren[n]; /*相應頂點的前序遍歷的順序號*/int postn[n]; /*相應頂點的后序遍歷的順序號*/int tra[n]; /*按遍歷順序存放的頂點序號*/3、其它變量：int sn; /*強連通分支個數(shù)*/int trapos[n];/*相應強連通分支的頂點集在數(shù)組art的起始位置*/int postv[n]; /*按后序遍歷順序存放的頂點序號*/四、算法的實現(xiàn)

1.intstrongly_con_com(NODEnode[],intn,inttra[],inttrapos[])2.{3.inti,prefdn,postfdn,count,sn;4.int*pren=newint[n];5.int*postn=newint[n];6.int*postv=newint[n];7.BOOL*b=newBOOL[n];8.NODE*arnode=newNODE[n];9.prefdn=0;postfdn=0;count=0;四、算法的實現(xiàn)

10.for(i=;i<n;i++) /*頂點訪問標志初始化為假*/11.b[i]=FALSE;12.for(i=0;i<n;i++) /*對G執(zhí)行深度優(yōu)先搜索*/13.if(!b[i])14.dfs(i,node,n,pren,postn,b,prefdn,postfdn,tra,count);15.for(i=0;i<n;i++){16.postv[postn[i]-1]=i;/*按后序遍歷順序存放的頂點序號*/17.b[i]=FALSE; /*頂點訪問標志初始化為假*/18.}19.reverse(node,arnode); /*反轉有向圖的邊,構造新圖的鄰接表*/20.prefdn=0;postfdn=0;count=0;sn=0;21.for(i=n-1;i>=0;i--){22.if(!b[postv[i]]){23.trapos[sn]=count;/*登記強連通分支頂點集在tra中的位置*/24.sn++; /*強連通分支計數(shù)*/25.dfs(postv[i],arnode,n,pren,postn,b,prefdn,postfdn,tra,count); /*對新的圖執(zhí)行深度優(yōu)先搜索*/26.}27.}28.deletepren;deletepostn;29.deletepostv;deleteb;30.delete_arnode(arnode);31.returnsn;32.}函數(shù)reverse的實現(xiàn)如下：1.voidreverse(NODE*node,NODE*arnode)2.{3.inti,k;4.NODE*p,*p1;5.for(k=0;k<n;k++) /*arnode為新圖鄰接表的頭結點*/6.arnode[k].next=NULL; /*頭結點指針初始化為空*/7.for(k=0;k<n;k++){8.p=node[k].next;9.while(p!=NULL){ /*反向登記新圖鄰接表的登記項*/10.p1=newNODE;11.p1->v=k;12.p1->next=arnode[p->v].next;13.arnode[p->v].next=p1;14.p=p->next;15.}16.}17.}五、復雜性分析1、時間復雜性：第9~11行的初始化工作需Θ(n)時間；第12~14行的第一次深度優(yōu)先搜索，需Θ(n+m)時間；第15~18行的初始化工作需Θ(n)時間；第19行的reverse函數(shù)，對m條邊構造新的鄰接表，因此，需要Θ(m)時間；第21行開始的第二次深度優(yōu)先搜索，需Θ(n+m)時間。整個算法的時間復雜性是Θ(n+m)時間。2、空間復雜性：存放輸入用的鄰接表需要Θ(m)=O(n2)的空間存放頂點的遍歷順序號、登記頂點的訪問標志等等所需要的工作單元為Θ(n)；存放反向圖的鄰接表需要Θ(m)空間。算法所需要的工作空間為Θ(m)=O(n2)。10.2網(wǎng)絡流量10.2.1網(wǎng)絡流概念10.2.2Ford_Fulkerson方法和最大容量增廣10.2.3最短路徑增廣一、有關網(wǎng)絡流量基本概念1、流量函數(shù)f(u,v)的基本概念定義10.4給定網(wǎng)絡(G,s,t,c)中，頂點對u、v的流量函數(shù)f(u,v)滿足下面四個條件：C1.斜對稱（skewsymmetry）。

u,v∈V,f(u,v)=-f(v,u)。如果f(u,v)>0，就說，這是從u到v的流量。C2.容量約束（capacityconstraints）。u,v∈V,f(u,v)≤c(u,v)。如果f(u,v)=c(u,v)，就說，邊(u,v)是飽和的。一、有關網(wǎng)絡流量基本概念C3.流量守恒（flowconservation）。，u∈V-{s,t}，即任何內部頂點的凈流量（出去的總流量減去進來的總流量）為0。C4.v∈V,f(v,v)=0圖10.6帶流量的網(wǎng)絡及其剩余圖10.2.2Ford_Fulkerson方法和最大容量增廣一、Ford_Fulkerson方法和最大容量增廣的思想方法二、最大容量增廣方法的步驟四、數(shù)據(jù)結構五、算法的實現(xiàn)六、復雜性分析一、思想方法1、出發(fā)點：1）根據(jù)最大流量最小割定理，若網(wǎng)絡G的流量f不存在增廣路徑，則f就是G中的最大流量。2）令G的初始流量f為0，重復地在f的剩余圖中尋找增廣路徑，用該路徑的瓶頸容量來增廣流量f，直到剩余圖中不存在增廣路徑為止。2、最大容量增廣方法的思想方法：令G的初始流量f為0，重復地在f的在剩余圖中搜索具有最大瓶頸容量的增廣路徑，從而加快算法的運行時間二、最大容量擴張方法的步驟：四、數(shù)據(jù)結構假定網(wǎng)絡的流量用實數(shù)表示。網(wǎng)絡各邊的流量和容量用圖的鄰接矩陣表示。float c[n][n]; /*網(wǎng)絡各頂點之間的初始容量*/float f[n][n]; /*最大流量下網(wǎng)絡各頂點之間流量*/float r[n][n]; /*剩余圖中各頂點之間的容量*/float cap[n]; /*搜索中的增廣路徑的瓶頸容量*/float flow； /*增廣路徑的最大瓶頸容量*/float maxflow; /*網(wǎng)絡的最大流量*/四、數(shù)據(jù)結構

int path[n]; /*正在搜索中的擴張路徑的頂點序號*/int path1[n]; /*最大瓶頸容量的擴張路徑的頂點序號*/int count; /*正在搜索中的擴張路徑上的頂點個數(shù)*/int count1; /*最大瓶頸容量的擴張路徑的頂點個數(shù)*/BOOLflag; /*搜索到擴張路徑標志*/int v; /*被搜索的頂點序號*/int s; /*網(wǎng)絡的源點序號*/int t; /*網(wǎng)絡的收點序號*/五、算法的實現(xiàn)1.floatmax_capacity_aug(floatc[][],floatf[][],intn,ints,intt)2.{3.inti,j,k,count,count1;4.intpath[n],path1[n],cap[n];5.floatr[n][n],flow,maxflow=0;6.BOOLflag=TRUE;7.for(i=0;i<n;i++) /*初始化網(wǎng)絡流量和剩余圖容量*/8.for(j=0;j<n;j++){9.f[i][j]=0;r[i][j]=c[i][j];10.}五、算法的實現(xiàn)11.while(flag){ 12.count=0;flow=0;flag=FALSE;13.mcadfs(s,t,r,n,path,path1,count,count1,cap,flow,flag);14.if(flag){ /*存在最大容量的增廣路徑*/15.maxflow+=flow;16.for(k=0;k<count1;k++){17.f[path1[k]][path1[k+1]]+=flow; /*流量增廣*/18.r[path1[k]][path1[k+1]]-=flow/*更新剩余容量*/19.r[path1[k+1][path1[k]]+=flow;20.}21.}22.}23.returnmaxflow;24.}五、算法的實現(xiàn)1.voidmcadfs(intv,intt,floatr[][],intn,intpath[],intpath1[],intcount,int&count1,floatcap[],float&flow,BOOL&flag)2.{3.inti,j;4.floattemp;5.path[count++]=v; /*在搜索路徑中登記頂點v*/6.for(i=0;i<n;i++){ /*頂點v,i有剩余容量,i不構成回路*/7.if((r[v][i]>0)&&(!(loop(i,path,count))){8.cap[count-1]=r[v][i]; /*搜索路徑中登記剩余容量*/9.if(i!=t) /*頂點i不是收點,繼續(xù)搜索*/10.mcadfs(i,t,r,n,path,path1,count,count1,cap,flow,flag);五、算法的實現(xiàn)11.else{ 12.flag=TRUE; /*頂點i是收點,存在擴張路徑*/13.path[count]=t; 14.temp=cap[0]; /*計算擴張路徑的瓶頸容量*/15.for(j=1;j<count;j++)16.if(cap[j]<temp)17.temp=cap[j];18.if(temp>flow){ /*是最大的瓶頸容量?*/19.for(j=0;j<=count;j++)20.path1[j]=path[j]; /*更新最大瓶頸容量的擴張路徑*/21.count1=count+1;22.flow=temp;23.}24.}25.}26.}27.}五、算法的實現(xiàn)1.BOOLloop(intv,intpath[],intcount)2.{3.inti;4.for(i=0;i<count;i++)5.if(v==path[i])6.returnTRUE;7.returnFALSE;8.}六、復雜性分析10.2.3最短路徑增廣一、分級圖二、思想方法三、最短路徑增廣的步驟四、數(shù)據(jù)結構五、算法的實現(xiàn)六、復雜性分析一、分級圖圖10.7二、思想方法利用分級圖，用廣度優(yōu)先搜索方法搜索最短路徑，選擇邊數(shù)最少的擴張路徑進行擴張三、最短路徑擴張的步驟四、數(shù)據(jù)結構五、算法的實現(xiàn)

1.floatmin_path_aug(floatc[][],floatf[][],intn,ints,intt)2.{3.inti,j,w;4.intpath[n];5.floatcap,r[n][n],flow=0;6.for(i=0;i<n;i++) /*初始化網(wǎng)絡流量和剩余圖*/7.for(j=0;j<n;j++){8.f[i][j]=0;r[i][j]=c[i][j];9.}五、算法的實現(xiàn)

10.while(mpla_bfs(s,t,r,path,n)){ /*尋找最短路徑*/11.w=path[t]; /*收點t的前方頂點w*/12.cap=r[w][t];13.while(w!=s){ /*沿著path計算瓶頸容量*/14.i=w;w=path[i]; 15.if(r[w][i]<cap)cap=r[w][i];16.}17.w=t;18.while(w!=s){ /*更新剩余圖,增廣流量*/19.i=w;w=path[i]; /*從t沿著path回溯到s*/20.r[w][i]-=cap;21.r[i][w]+=cap;22.f[w][i]+=cap;23.}24.flow+=cap;25.}26.returnflow;27.}五、算法的實現(xiàn)

1.BOOLmpla_bfs(ints,intt,floatr[][],intpath[],intn)2.{3.intw;4.BOOLb[n]; /*頂點遍歷標志*/5.BOOLflag=FALSE;6.QUEUEqueue;7.NODE*p=newNODE; /*建立待搜索頂點的隊列元素*/8.initial_Q(queue); /*初始化廣度優(yōu)先搜索隊列*/9.for(i=0;i<n;i++) /*初始化頂點頂點遍歷標志*/10.b[i]=FALSE;11.path[s]=-1;12.p->v=s; /*賦予待搜索的隊列元素的頂點編號*/13.append_Q(queue,p);/*把該元素放到搜索隊列尾巴*/14.b[s]=TRUE;五、算法的實現(xiàn)15.while(!(empty(queue))&&!(flag)){ /*搜索隊列非空?*/16.p=delete_Q(queue); /*取下搜索隊列的隊首元素*/17.w=p->v; /*該元素的頂點編號保存于w*/18.deletep;i=0; /*頂點i初始化為0*/19.while(i<n){ /*尚未搜索到最短路徑p*/20.if((r[w][i])>0)&&!(b[i])) 21.b[i]=TRUE;22.path[i]=w; /*在路徑p上登記i的前一頂點*/23.if(i==t){ /*搜索到一條路徑,退出循環(huán)*/24.flag=TRUE;break;25.} 26.p=newNODE; /*建立一個待搜索的隊列元素*/27.p->v=i; /*賦予該元素的頂點編號*/28.append_Q(queue,p); /*把該元素放到搜索隊列尾巴*/29.}30.i++;31.}32.}33.returnflag;34.}六、復雜性分析六、復雜性分析10.3二分圖的最大匹配問題10.3.1預備知識10.3.2二分圖最大匹配的匈牙利樹方法10.3.1預備知識

一、基本概念二、最大匹配的求取一、基本概念圖10.8二、最大匹配的求取圖10.910.3.2二分圖最大匹配的匈牙利樹方法

一、二分圖二、在二分圖中尋找最大匹配的匈牙利樹方法三、匈牙利樹方法構造二分圖的最大匹配算法的步驟四、數(shù)據(jù)結構五、算法的實現(xiàn)六、復雜性分析一、二分圖例：圖10.9的無向圖，重新畫成圖10.12所表示的二分圖形式。圖10.10二、在二分圖中尋找最大匹配的匈牙利樹方法例圖10.13的二分圖中，匹配M={(a,f),(d,g),(e,h)}。以b為根的交替路徑樹以c為根的匈牙利樹三、匈牙利樹方法構造二分圖的最大匹配算法的步驟：四、數(shù)據(jù)結構NODEnode[n]; int match[n]; int path[n]; BOOLblock[n]; typedefstructq_node{ int v; int tag; structq_node*next; }QNODE;typedefstruct{ QNODE *head; QNODE *tair; }QUEUE;五、算法的實現(xiàn)

1.hung_bipartite_match(NODEnode[],intmatch[],intn1,intn)2.{3.intr,i,j,t,path[n];4.BOOLblock[n],flag=TRUE;5.for(i=0;i<n;i++) 6.match[i]=-1;7.while(flag){8.for(r=0;r<n1;r++) 9.if(match[r]==-1)break;10.if(r>=n1)break; 11.for(i=n1;i<n;i++) 12.if(match[i]==-1)break;13.if(i>=n)break; 14.if(!(hung_bfs(r,t,node,match,path,block,n))){15.for(i=0;i<n;i++){ 16.if(block[i]){17.v=i;node[v].next=NULL;18.while(path[v]!=-1){19.