本節(jié)內(nèi)容ABCFEF圖G由頂點集V和邊集E組成，記為G=(V,E)圖樹是N(N≥0)個結(jié)點的有限集合，N=0時，稱為空樹，這是一種特殊情況。在任意一棵非空樹中應(yīng)滿足1)有且僅有一個特定的稱為根的結(jié)點。2)當(dāng)N>1時，其余結(jié)點可分為m(m>0)個互不相交的有限集合T?,T?,…,Tm,其中每一個集合本身又是一棵樹，并且稱為根結(jié)點的子樹。圖中就算是一條邊都沒有，也就是邊集為空，但是頂點集一定不為空。V(G)表示圖G中頂點的有限非空集。用|V|表示圖G中頂點的個數(shù)，也稱為圖G的階。E(G)表示圖G中頂點之間的關(guān)系(邊)集合。用|E|表示圖G中邊的條數(shù)。圖的基本概念圖的基本概念v鄰接到w或w鄰接自v圖無向邊(邊)的有限集合有向邊(弧)的有限集合有向圖無向圖有向圖G1無向圖G2圖的基本概念A(yù)對于n個頂點頂點有一條邊，由于重復(fù)每個頂點都與其他n-1個頂點圖的基本概念若有滿足V(G’)=V(G)的子圖G’,則為G的生成子圖A并非V和E的任何子集都能構(gòu)成G的子圖，因為這樣的子集可能不是圖，也就是說，E的子集中的某些邊關(guān)聯(lián)的頂點可能不在這個V的子集中。圖的基本概念如果右圖看成一個圖EQ\*jc3\*hps31\o\al(\s\up13(G),V)則是不連通的子圖個頂點，并且有小于n-1條邊，則此圖必從選取一個頂點開始，以這個頂點作為一個子圖，然后逐個添加與這個子圖相連的頂點和邊直到所有相連的頂點都加入該子圖圖的基本概念EQ\*jc3\*hps43\o\al(\s\up8(,),B)不連通AD強連通分量：有向圖中的極大強連通子圖強連通強連通分量圖的基本概念C無向圖中頂點V的度是指依附于該頂點的邊的條數(shù)，記為TD(v)有向圖中頂點v的度分為出度和入度A無向圖A有向圖無向圖：有向樹：有一個頂點的入度為0,其余頂點的入度均為1的有向圖。A有向樹B和D的距離為2路徑長度為4圖的基本概念弧有向圖弧無向圖邊無向圖度生成樹完全圖EhrNHLL-+圖的存儲結(jié)構(gòu)相比線性表和樹顯得更復(fù)雜圖中頂點沒有次序之分圖中邊和頂點的數(shù)量任意頂點數(shù)組：頂點數(shù)組：頂點：用一維數(shù)組來存儲邊或?。河枚S數(shù)組來存儲ABCD無向圖的鄰接矩陣是一個對稱矩陣因此可以只存儲上半部分矩陣二維數(shù)組就是一維數(shù)組的拓展，相當(dāng)于一維數(shù)組中每個元素也是一個一維數(shù)組。二維數(shù)組也叫做鄰接矩陣3*3二維數(shù)組1.判定兩個頂點是否有邊2.求某個頂點的度3.找到某個頂點的所有鄰接點頂點數(shù)組：A邊或弧數(shù)組：對于帶權(quán)圖(網(wǎng))可以在矩陣中存儲邊的權(quán)值BABCD各各頂點的入度是頂點所在這一列的的各數(shù)之和。2.判定兩個頂點是否有邊3.找到某個頂點的所有鄰接點1、帶權(quán)邊存儲權(quán)值2、行和列相同結(jié)點權(quán)3、不存在的邊權(quán)值為無限大typedeftypedeftypedef//頂點數(shù)目的最大值//頂點的數(shù)據(jù)類型不同情況不一樣//整數(shù)表示權(quán)值或者連通性//鄰接矩陣(二維數(shù)組),邊表//圖的當(dāng)前頂點數(shù)和弧數(shù)VertexType//鄰接矩陣(二維數(shù)組),邊表//圖的當(dāng)前頂點數(shù)和弧數(shù)由于鄰接矩陣基于二維數(shù)組，所以利用二維數(shù)組創(chuàng)建圖的時間復(fù)雜度為O(n2),其中n為圖的頂點數(shù)。所以當(dāng)頂點數(shù)較多時，鄰接矩陣的復(fù)雜度也會比較大。ffeffeABCD01aabaabC01234八八13八八13524CbCA八A八AAe鄰接表頂點表下標頂點表下標0123AAABCDB22122212八A0A八A0A圖中的頂點用一個一維數(shù)組存儲。同時每個元素還要存儲指向第一個鄰接點的指針(鏈表的頭指針)。存儲頂點和頭指針的表叫頂點裴圖中每個頂點的所有鄰接點構(gòu)成一個單鏈表。對于無向圖，這個表稱為該結(jié)點的邊表，對于有向圖稱為該結(jié)點的出邊裹下標0123下標0123八12302A八八八八A注意是以頂注意是以頂點為弧尾D需要設(shè)計兩種結(jié)點結(jié)構(gòu)類型：一是頂點表的頂點，二是單鏈表的結(jié)點//頂點表結(jié)點data;//頂點信息//頂點表結(jié)點data;//頂點信息//單鏈表頭指針ArcNodexfirstedge;//單鏈表頭指針}VNode,AdjList[MaxVertexNum];//AdjList是結(jié)構(gòu)體數(shù)組類型#defineMaxVertexNum100//圖中頂點數(shù)目的最大值typedefstructArcNode{//邊表結(jié)點intadjvex;//該弧所指向的頂點的位置structArcNode*next;//指向下一條弧的指針typedefstruct{//鄰接表//圖的頂點數(shù)和弧數(shù)//ALGraph是以鄰接表存儲的圖類型十字鏈表12302八八A八注意是以頂點為弧尾有向圖的鄰接表關(guān)心了有向圖的出邊問題，我們通過有向圖很容易找到頂點的出邊比如從每個頂點表的firstedge指針找到第一條邊的頂點，再通過next指針依次找到下一條邊的頂點直到空指針。但是，如果要找到其他頂點到該頂點的邊，或者說考慮一個頂點的入度問題，則需要遍歷整個圖。這是鄰接表存儲有向圖的缺陷。十字鏈表是針對有向圖的存儲方式，對應(yīng)于有向圖中的每條弧有一個結(jié)點，對應(yīng)于每個頂點也有一個結(jié)點頂點結(jié)點圖中頂點圖中頂點表的頭指針表的頭指針邊表結(jié)點弧尾(起點)弧頭(終點)(終點)相同所在頂點所在頂點的下一條邊表下標表下標指向弧尾的下一條邊其實十字鏈表是在鄰接表的基礎(chǔ)上進行了優(yōu)化。在十字鏈表中不僅包含了鄰接表本身就包含的結(jié)點出度結(jié)點，而且還包含了入度結(jié)點的信息。相同相同弧頭相同弧尾B下標123ADC入邊表出邊表ABCD?！擁旤c的出邊→該頂點的入邊十字鏈表的存儲形式不唯十字鏈表的存儲形式不唯一頂點結(jié)點的數(shù)據(jù)該頂點的入邊表的頭指針表的頭指針邊表結(jié)點這條弧的這條弧的指向弧頭指向弧尾弧尾(起點)弧頭(終點)(終點)相同(起點)相同所在頂點所在頂點的下一條邊的下一條邊表下標表下標typedefstructArcNode{鄰接多重表頂點表邊表頂點表ABCD八221210ABCD八221210003A八3A0123鄰接表存儲的無向圖中查找頂點是比較容易的，但是如果要修改圖中的邊或者是查詢邊，則需要遍歷鏈表。這是鄰接表的缺陷。仿照十字鏈表，對鄰接表的邊表進行改造，得到專門針對存儲無向圖的鄰接多重表邊表邊表AABCD012310002212八A八Ajvexjlinkjvexjlink點的兩個頂點在頂點表的下標一條邊指向依附頂一條邊工這條邊依附的兩個頂點在頂點表的下標指向依附頂點ivex的下一條邊指向依附頂點jvex的下一條邊圖的遍歷：從圖中某一頂點出發(fā)訪遍圖中其余頂點，且使每一個頂點僅被訪問一次，這個過程就叫做圖的遍歷。樹的遍歷圖中頂點沒有特殊性，可能存在沿著某條路徑搜索后回到原起點，而有些頂點沒有訪問到。圖的遍歷第一層第二層第三層第四層visit(p->adjvex);//訪問p所指向的頂點visited[p->adjvex]=TRUE;//對這個頂點做已訪問標記EnQueue(Q,p->adjvex);//這個頂點入隊列}p=p->next;//p指向該頂點的下一條邊}}}for(i=0;i<G->vexnum;i++)visited[]=false;//將標志數(shù)組初始化(全局數(shù)組)for(i=0;i<G->vexnum為了避免非連通圖一些頂點訪問不到若是連通圖只會執(zhí)行一次}}}})}下標0123422212八ABCDE1000N八N343A1訪問標記數(shù)組頂點ABCDE是否訪問visit(p->adjvex);//訪問p所指向的頂點visited[p->adjvex]=TRUE;//對這個頂點做已訪問標記EnQueue(Q,p->adjvex);//這個頂點入隊列}}}}visit(p->adjvex);//訪問p所指向的頂點visited[p->adjvex]=TRUE;//對這個頂點做已訪問標記EnQueue(Q,p->adjvex);//這個頂點入隊列}p=p->next;//指向該頂點的下一條邊}}}時間復(fù)雜度：2)鄰接矩陣：每個頂點入隊一次，時間復(fù)雜度為O(IV|,對于每個頂點，搜索它的鄰接點，需要遍歷一遍矩陣的一行，所以時間復(fù)雜度為O(VI),所以總的時間復(fù)雜度為O(VI?)BFS解決單源非帶權(quán)圖最短路徑問題：按照距離由近到遠來遍歷圖中每個頂點ArcNode*p=G->adjLis//路徑長度加1}}}廣度優(yōu)先生成樹ADBDEAB如果圖是鄰接矩陣存儲的，廣度優(yōu)先生成樹唯一。如果圖是鄰接矩陣存儲的，廣度優(yōu)先生成樹則不唯一。深度優(yōu)先搜索(DFS:Depth-First-Search):深度優(yōu)先搜索類似于樹的先序遍歷算法首先訪問圖中某一起始頂點v,然后由v出發(fā)，訪問與v鄰接且未被訪問的任一頂點w1,再訪問與w1鄰接且未被訪問的任一頂點w2,……重復(fù)上述過程。當(dāng)不能再繼續(xù)向下訪問時，依次退回到最近被訪問的頂點，若它還有鄰接頂點未被訪問過，則從該點開始繼續(xù)上述搜索過程，直到圖中所有頂點均被訪問過為止voidDFS(GraphG,intv){ArcNode*p;“//工作指針pwhile(p!=NULL){//沒遍歷完頂點的所有鄰接頂點if(!visited[p->adjvex]}{//如果該頂點沒被訪問DFS(G,p->adjvex);//遞歸訪問該頂點}看還有沒有其他未訪問的頂點inti;//單獨定義是為了方便多個循環(huán)中使用for(i=0;i<G->vexnum;i++)visited[i]=false;//將標志數(shù)組初始化(全局數(shù)組)f(!visited[])DFS(G,i);//對所有頂點訪問序列：頂點訪問序列：ABCDE}下標4ABCDE100012212八343N訪問標記數(shù)組頂點ABCDE是否訪問ArcNode*p;//工作指針pvisit(v);//訪問頂點v(一般是遍歷，即printf)while(p!=NULL){//沒遍歷完頂點的所有鄰接頂點DFS(G,p->adjvex);//遞歸訪問該頂點p=p->nextarc;//看還有沒有其他未訪問的頂點空間復(fù)雜度：由于DFS是一個遞歸算法，遞歸是需要一個工作棧來輔助工作，最多需要圖中所有頂點進棧，所以時間復(fù)雜度為O(IVI)時間復(fù)雜度：1)鄰接表：遍歷過程的主要操作是對頂點遍歷它的鄰接點，由于通過訪問邊表來查找鄰接點，所以時間復(fù)雜度為O(IEI),訪問頂點時間為O(IVI),所以總的時間復(fù)雜度為O(IV|+|EI)2)鄰接矩陣：查找每個頂點的鄰接點時間復(fù)雜度為O(VI),對每個頂點都進行查找，所以總的時間復(fù)雜度為O(VI?)如果是一個非連通圖，則是深度優(yōu)先森林BE深度優(yōu)先生成樹A深度優(yōu)先森林圖的應(yīng)用(1)最小生成樹最小生成樹我們之前講過連通圖的生成樹，它是一個極小的連通子圖。它包含圖中全部的頂點，但只有足以構(gòu)成一棵樹的n-1條邊。生成樹不唯一選擇總權(quán)值最小的修路成本自然最小選擇總權(quán)值最小的修路成本自然最小5A鎮(zhèn)8282E鎮(zhèn)3最小生成樹①從圖中找第一個起始頂點v0,作為生成樹的第一個頂點，然后從這個頂點到其他頂點的所有邊中選一條權(quán)值最小的邊。然后把這條邊的另一個頂點v和這條邊加入到生成樹中。②對剩下的其他所有頂點，分別檢查這些頂點與頂點v的權(quán)值是否比這些頂點在lowcost數(shù)組中對應(yīng)的權(quán)值小，如果更小，則用較小的權(quán)值更新lowcost數(shù)組。③從更新后的lowcost數(shù)組中繼續(xù)挑選權(quán)值最小而且不在生成樹中的邊，然后加入到生成樹。④反復(fù)執(zhí)行②③直到所有所有頂點都加入到生成樹中。需要維護兩個數(shù)組：lowcost[n]adjvex[n](n是圖中的頂點數(shù))初始化初始化普利姆算法生成樹中intadjvex[MAXVEX];//保存鄰接頂點下標的數(shù)組//記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值//將0號頂點(以0號頂點作為第一個頂點)加入生成樹//記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值//將0號頂點(以0號頂點作為第一個頂點)加入生成樹//由于剛開始生成樹只有一個頂點不存在邊干脆都設(shè)為0for(i=1;i<G.vexnum;i++){//除下標為0以外的所有頂點lowcost[]=G.arc[0][]://將與下標為0的頂點有邊的權(quán)值存入Lowcost數(shù)組adjvex[j]=0;//這些頂點的adjvex數(shù)組全部初始化為0初始化05000000000找頂點找頂點更新數(shù)組普利姆(Prim)算法普利姆算法表生成樹中表生成樹中intadjvex[MAXVEX];//保存鄰接頂點下標的數(shù)組//記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值//將0號頂點(以0號頂點作為第一個頂點)加入生成樹//由于剛開始生成樹只有一個頂點不存在邊干脆都設(shè)為0adjvex[]=0;//這些頂點的adjvex數(shù)組全部初始化為0}//算法核心min=65535;//tip:因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min,下標給kwhile(j<G.vexnum)[//從1號頂點開始找if[lowcost[])=0&&lowcosti]<min){//不在生成樹中的頂點而且權(quán)值更小的min=lowcost[];//更新更小的值k=j;//找到了新的點下標給kEQ\*jc3\*hps5\o\al(\s\up10(),j)++;//再看下一個頂點L}lowcost[k]=0;//將這個頂點加入生成樹//生成樹加入了新的頂點從下標為1的頂點開始更新lowcost數(shù)組值lowcost[]=G.arc][];//更新更小的權(quán)值adjvex[]=k;//修改這條邊鄰接的頂點也就是表示這條邊是從選出的頂點k指過來的方便打印}}}05000000}找頂點找頂點更新數(shù)組普利姆(Prim)算法普利姆算法表生成樹中表生成樹中intadjvex[MAXVEX];//保存鄰接頂點下標的數(shù)組//記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值//將0號頂點(以0號頂點作為第一個頂點)加入生成樹//由于剛開始生成樹只有一個頂點不存在邊干脆都設(shè)為0adjvex[]=0;//這些頂點的adjvex數(shù)組全部初始化為0}//算法核心min=65535;//tip:因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min,下標給kwhile(j<G.vexnum)[//從1號頂點開始找if[lowcost[])=0&&lowcosti]<min){//不在生成樹中的頂點而且權(quán)值更小的min=lowcost[];//更新更小的值k=j;//找到了新的點下標給kEQ\*jc3\*hps5\o\al(\s\up10(),j)++;//再看下一個頂點L}lowcost[k]=0;//將這個頂點加入生成樹//生成樹加入了新的頂點從下標為1的頂點開始更新lowcost數(shù)組值lowcost[]=G.arc][];//更新更小的權(quán)值adjvex[]=k;//修改這條邊鄰接的頂點也就是表示這條邊是從選出的頂點k指過來的方便打印}}}0000O00000}找頂點找頂點更新數(shù)組普利姆(Prim)算法普利姆算法表生成樹中表生成樹中intadjvex[MAXVEX];//保存鄰接頂點下標的數(shù)組//記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值//將0號頂點(以0號頂點作為第一個頂點)加入生成樹//由于剛開始生成樹只有一個頂點不存在邊干脆都設(shè)為0adjvex[]=0;//這些頂點的adjvex數(shù)組全部初始化為0}//算法核心min=65535;//tip:因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min,下標給kwhile(j<G.vexnum)[//從1號頂點開始找if[lowcost[])=0&&lowcosti]<min){//不在生成樹中的頂點而且權(quán)值更小的min=lowcost[];//更新更小的值k=j;//找到了新的點下標給kEQ\*jc3\*hps5\o\al(\s\up10(),j)++;//再看下一個頂點L}lowcost[k]=0;//將這個頂點加入生成樹//生成樹加入了新的頂點從下標為1的頂點開始更新lowcost數(shù)組值lowcost[]=G.arc][];//更新更小的權(quán)值adjvex[]=k;//修改這條邊鄰接的頂點也就是表示這條邊是從選出的頂點k指過來的方便打印}}}0028O0001110}找頂點找頂點更新數(shù)組普利姆(Prim)算法普利姆算法表生成樹中表生成樹中intadjvex[MAXVEX];//保存鄰接頂點下標的數(shù)組//記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值//將0號頂點(以0號頂點作為第一個頂點)加入生成樹//由于剛開始生成樹只有一個頂點不存在邊干脆都設(shè)為0adjvex[]=0;//這些頂點的adjvex數(shù)組全部初始化為0}//算法核心min=65535;//tip:因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min,下標給kwhile(j<G.vexnum)[//從1號頂點開始找if[lowcost[])=0&&lowcosti]<min){//不在生成樹中的頂點而且權(quán)值更小的min=lowcost[];//更新更小的值k=j;//找到了新的點下標給kEQ\*jc3\*hps5\o\al(\s\up10(),j)++;//再看下一個頂點L}lowcost[k]=0;//將這個頂點加入生成樹//生成樹加入了新的頂點從下標為1的頂點開始更新lowcost數(shù)組值lowcost[]=G.arc][];//更新更小的權(quán)值adjvex[]=k;//修改這條邊鄰接的頂點也就是表示這條邊是從選出的頂點k指過來的方便打印}}}0028O0001110}找頂點找頂點更新數(shù)組普利姆(Prim)算法普利姆算法表生成樹中表生成樹中intadjvex[MAXVEX];//保存鄰接頂點下標的數(shù)組//記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值//將0號頂點(以0號頂點作為第一個頂點)加入生成樹//由于剛開始生成樹只有一個頂點不存在邊干脆都設(shè)為0adjvex[]=0;//這些頂點的adjvex數(shù)組全部初始化為0}//算法核心min=65535;//tip:因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min,下標給kwhile(j<G.vexnum)[//從1號頂點開始找if[lowcost[])=0&&lowcosti]<min){//不在生成樹中的頂點而且權(quán)值更小的min=lowcost[];//更新更小的值k=j;//找到了新的點下標給kEQ\*jc3\*hps5\o\al(\s\up10(),j)++;//再看下一個頂點L}lowcost[k]=0;//將這個頂點加入生成樹//生成樹加入了新的頂點從下標為1的頂點開始更新lowcost數(shù)組值lowcost[]=G.arc][];//更新更小的權(quán)值adjvex[]=k;//修改這條邊鄰接的頂點也就是表示這條邊是從選出的頂點k指過來的方便打印}}}0008O0001110}找頂點找頂點更新數(shù)組普利姆(Prim)算法普利姆算法表生成樹中表生成樹中intadjvex[MAXVEX];//保存鄰接頂點下標的數(shù)組//記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值//將0號頂點(以0號頂點作為第一個頂點)加入生成樹//由于剛開始生成樹只有一個頂點不存在邊干脆都設(shè)為0adjvex[]=0;//這些頂點的adjvex數(shù)組全部初始化為0}//算法核心min=65535;//tip:因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min,下標給kwhile(j<G.vexnum)[//從1號頂點開始找if[lowcost[])=0&&lowcosti]<min){//不在生成樹中的頂點而且權(quán)值更小的min=lowcost[];//更新更小的值k=j;//找到了新的點下標給kEQ\*jc3\*hps5\o\al(\s\up10(),j)++;//再看下一個頂點L}lowcost[k]=0;//將這個頂點加入生成樹//生成樹加入了新的頂點從下標為1的頂點開始更新lowcost數(shù)組值lowcost[]=G.arc][];//更新更小的權(quán)值adjvex[]=k;//修改這條邊鄰接的頂點也就是表示這條邊是從選出的頂點k指過來的方便打印}}}00040001144}找頂點找頂點更新數(shù)組普利姆(Prim)算法普利姆算法表生成樹中表生成樹中intadjvex[MAXVEX];//保存鄰接頂點下標的數(shù)組//記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值//將0號頂點(以0號頂點作為第一個頂點)加入生成樹//由于剛開始生成樹只有一個頂點不存在邊干脆都設(shè)為0adjvex[]=0;//這些頂點的adjvex數(shù)組全部初始化為0}//算法核心min=65535;//tip:因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min,下標給kwhile(j<G.vexnum)[//從1號頂點開始找if[lowcost[])=0&&lowcosti]<min){//不在生成樹中的頂點而且權(quán)值更小的min=lowcost[];//更新更小的值k=j;//找到了新的點下標給kEQ\*jc3\*hps5\o\al(\s\up10(),j)++;//再看下一個頂點L}lowcost[k]=0;//將這個頂點加入生成樹//生成樹加入了新的頂點從下標為1的頂點開始更新lowcost數(shù)組值lowcost[]=G.arc][];//更新更小的權(quán)值adjvex[]=k;//修改這條邊鄰接的頂點也就是表示這條邊是從選出的頂點k指過來的方便打印}}}00040001144}找頂點找頂點更新數(shù)組普利姆(Prim)算法普利姆算法表生成樹中表生成樹中intadjvex[MAXVEX];//保存鄰接頂點下標的數(shù)組//記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值//將0號頂點(以0號頂點作為第一個頂點)加入生成樹//由于剛開始生成樹只有一個頂點不存在邊干脆都設(shè)為0adjvex[]=0;//這些頂點的adjvex數(shù)組全部初始化為0}//算法核心min=65535;//tip:因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min,下標給kwhile(j<G.vexnum)[//從1號頂點開始找if[lowcost[])=0&&lowcosti]<min){//不在生成樹中的頂點而且權(quán)值更小的min=lowcost[];//更新更小的值k=j;//找到了新的點下標給kEQ\*jc3\*hps5\o\al(\s\up10(),j)++;//再看下一個頂點L}lowcost[k]=0;//將這個頂點加入生成樹//生成樹加入了新的頂點從下標為1的頂點開始更新lowcost數(shù)組值lowcost[]=G.arc][];//更新更小的權(quán)值adjvex[]=k;//修改這條邊鄰接的頂點也就是表示這條邊是從選出的頂點k指過來的方便打印}}}00000001144}找頂點找頂點更新數(shù)組普利姆(Prim)算法普利姆算法表生成樹中表生成樹中intadjvex[MAXVEX];//保存鄰接頂點下標的數(shù)組//記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值//將0號頂點(以0號頂點作為第一個頂點)加入生成樹//由于剛開始生成樹只有一個頂點不存在邊干脆都設(shè)為0adjvex[]=0;//這些頂點的adjvex數(shù)組全部初始化為0}//算法核心min=65535;//tip:因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min,下標給kwhile(j<G.vexnum)[//從1號頂點開始找if[lowcost[])=0&&lowcosti]<min){//不在生成樹中的頂點而且權(quán)值更小的min=lowcost[];//更新更小的值k=j;//找到了新的點下標給kEQ\*jc3\*hps5\o\al(\s\up10(),j)++;//再看下一個頂點L}lowcost[k]=0;//將這個頂點加入生成樹//生成樹加入了新的頂點從下標為1的頂點開始更新lowcost數(shù)組值lowcost[]=G.arc][];//更新更小的權(quán)值adjvex[]=k;//修改這條邊鄰接的頂點也就是表示這條邊是從選出的頂點k指過來的方便打印}}}000030001145}找頂點找頂點更新數(shù)組普利姆(Prim)算法普利姆算法表生成樹中表生成樹中intadjvex[MAXVEX];//保存鄰接頂點下標的數(shù)組//記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值//將0號頂點(以0號頂點作為第一個頂點)加入生成樹//由于剛開始生成樹只有一個頂點不存在邊干脆都設(shè)為0adjvex[]=0;//這些頂點的adjvex數(shù)組全部初始化為0}//算法核心min=65535;//tip:因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min,下標給kwhile(j<G.vexnum)[//從1號頂點開始找if[lowcost[])=0&&lowcosti]<min){//不在生成樹中的頂點而且權(quán)值更小的min=lowcost[];//更新更小的值k=j;//找到了新的點下標給kEQ\*jc3\*hps5\o\al(\s\up10(),j)++;//再看下一個頂點L}lowcost[k]=0;//將這個頂點加入生成樹//生成樹加入了新的頂點從下標為1的頂點開始更新lowcost數(shù)組值lowcost[]=G.arc][];//更新更小的權(quán)值adjvex[]=k;//修改這條邊鄰接的頂點也就是表示這條邊是從選出的頂點k指過來的方便打印}}}000030001145}找頂點找頂點更新數(shù)組普利姆(Prim)算法普利姆算法表生成樹中表生成樹中intadjvex[MAXVEX];//保存鄰接頂點下標的數(shù)組//記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值//將0號頂點(以0號頂點作為第一個頂點)加入生成樹//由于剛開始生成樹只有一個頂點不存在邊干脆都設(shè)為0adjvex[]=0;//這些頂點的adjvex數(shù)組全部初始化為0}//算法核心min=65535;//tip:因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min,下標給kwhile(j<G.vexnum)[//從1號頂點開始找if[lowcost[])=0&&lowcosti]<min){//不在生成樹中的頂點而且權(quán)值更小的min=lowcost[];//更新更小的值k=j;//找到了新的點下標給kEQ\*jc3\*hps5\o\al(\s\up10(),j)++;//再看下一個頂點L}lowcost[k]=0;//將這個頂點加入生成樹//生成樹加入了新的頂點從下標為1的頂點開始更新lowcost數(shù)組值lowcost[]=G.arc][];//更新更小的權(quán)值adjvex[]=k;//修改這條邊鄰接的頂點也就是表示這條邊是從選出的頂點k指過來的方便打印}}}000000001145}找頂點找頂點更新數(shù)組普利姆(Prim)算法普利姆算法表生成樹中表生成樹中intadjvex[MAXVEX];//保存鄰接頂點下標的數(shù)組//記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值//將0號頂點(以0號頂點作為第一個頂點)加入生成樹//由于剛開始生成樹只有一個頂點不存在邊干脆都設(shè)為0adjvex[]=0;//這些頂點的adjvex數(shù)組全部初始化為0}//算法核心min=65535;//tip:因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min,下標給kwhile(j<G.vexnum)[//從1號頂點開始找if[lowcost[])=0&&lowcosti]<min){//不在生成樹中的頂點而且權(quán)值更小的min=lowcost[];//更新更小的值k=j;//找到了新的點下標給kEQ\*jc3\*hps5\o\al(\s\up10(),j)++;//再看下一個頂點L}lowcost[k]=0;//將這個頂點加入生成樹//生成樹加入了新的頂點從下標為1的頂點開始更新lowcost數(shù)組值lowcost[]=G.arc][];//更新更小的權(quán)值adjvex[]=k;//修改這條邊鄰接的頂點也就是表示這條邊是從選出的頂點k指過來的方便打印}}}000000001145}找頂點找頂點更新數(shù)組普利姆算法表生成樹中表生成樹中intadjvex[MAXVEX];//保存鄰接頂點下標的數(shù)組//記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值//將0號頂點(以0號頂點作為第一個頂點)加入生成樹//由于剛開始生成樹只有一個頂點不存在邊干脆都設(shè)為0adjvex[]=0;//這些頂點的adjvex數(shù)組全部初始化為0}//算法核心min=65535;//tip:因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min,下標給kwhile(j<G.vexnum)[//從1號頂點開始找if[lowcost[])=0&&lowcosti]<min){//不在生成樹中的頂點而且權(quán)值更小的min=lowcost[];//更新更小的值k=j;//找到了新的點下標給kEQ\*jc3\*hps5\o\al(\s\up10(),j)++;//再看下一個頂點L}lowcost[k]=0;//將這個頂點加入生成樹//生成樹加入了新的頂點從下標為1的頂點開始更新lowcost數(shù)組值lowcost[]=G.arc][];//更新更小的權(quán)值adjvex[]=k;//修改這條邊鄰接的頂點也就是表示這條邊是從選出的頂點k指過來的方便打印}}}00000001145}找頂點找頂點更新數(shù)組普利姆算法表生成樹中表生成樹中intadjvex[MAXVEX];//保存鄰接頂點下標的數(shù)組//記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值//將0號頂點(以0號頂點作為第一個頂點)加入生成樹//由于剛開始生成樹只有一個頂點不存在邊干脆都設(shè)為0adjvex[]=0;//這些頂點的adjvex數(shù)組全部初始化為0}//算法核心min=65535;//tip:因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min,下標給kwhile(j<G.vexnum)[//從1號頂點開始找if[lowcost[])=0&&lowcosti]<min){//不在生成樹中的頂點而且權(quán)值更小的min=lowcost[];//更新更小的值k=j;//找到了新的點下標給kEQ\*jc3\*hps5\o\al(\s\up10(),j)++;//再看下一個頂點L}lowcost[k]=0;//將這個頂點加入生成樹//生成樹加入了新的頂點從下標為1的頂點開始更新lowcost數(shù)組值lowcost[]=G.arc][];//更新更小的權(quán)值adjvex[]=k;//修改這條邊鄰接的頂點也就是表示這條邊是從選出的頂點k指過來的方便打印}}}00000001145}找頂點找頂點更新數(shù)組普利姆算法表生成樹中表生成樹中intadjvex[MAXVEX];//保存鄰接頂點下標的數(shù)組//記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值//將0號頂點(以0號頂點作為第一個頂點)加入生成樹//由于剛開始生成樹只有一個頂點不存在邊干脆都設(shè)為0adjvex[]=0;//這些頂點的adjvex數(shù)組全部初始化為0}//算法核心min=65535;//tip:因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min,下標給kwhile(j<G.vexnum)[//從1號頂點開始找if[lowcost[])=0&&lowcosti]<min){//不在生成樹中的頂點而且權(quán)值更小的min=lowcost[];//更新更小的值k=j;//找到了新的點下標給kEQ\*jc3\*hps5\o\al(\s\up10(),j)++;//再看下一個頂點L}lowcost[k]=0;//將這個頂點加入生成樹//生成樹加入了新的頂點從下標為1的頂點開始更新lowcost數(shù)組值lowcost[]=G.arc][];//更新更小的權(quán)值adjvex[]=k;//修改這條邊鄰接的頂點也就是表示這條邊是從選出的頂點k指過來的方便打印}}}0000000001145}找頂點找頂點更新數(shù)組普利姆(Prim)算法普利姆算法表生成樹中表生成樹中intadjvex[MAXVEX];//保存鄰接頂點下標的數(shù)組//記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值//將0號頂點(以0號頂點作為第一個頂點)加入生成樹//由于剛開始生成樹只有一個頂點不存在邊干脆都設(shè)為0adjvex[]=0;//這些頂點的adjvex數(shù)組全部初始化為0}//算法核心min=65535;//tip:因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min,下標給kwhile(j<G.vexnum)[//從1號頂點開始找if[lowcost[])=0&&lowcosti]<min){//不在生成樹中的頂點而且權(quán)值更小的min=lowcost[];//更新更小的值k=j;//找到了新的點下標給kEQ\*jc3\*hps5\o\al(\s\up10(),j)++;//再看下一個頂點L}lowcost[k]=0;//將這個頂點加入生成樹//生成樹加入了新的頂點從下標為1的頂點開始更新lowcost數(shù)組值lowcost[]=G.arc][];//更新更小的權(quán)值adjvex[]=k;//修改這條邊鄰接的頂點也就是表示這條邊是從選出的頂點k指過來的方便打印}}}000000001145}找頂點找頂點更新數(shù)組普利姆(Prim)算法普利姆算法表生成樹中表生成樹中intadjvex[MAXVEX];//保存鄰接頂點下標的數(shù)組//記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值//將0號頂點(以0號頂點作為第一個頂點)加入生成樹//由于剛開始生成樹只有一個頂點不存在邊干脆都設(shè)為0adjvex[]=0;//這些頂點的adjvex數(shù)組全部初始化為0}//算法核心min=65535;//tip:因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min,下標給kwhile(j<G.vexnum)[//從1號頂點開始找if[lowcost[])=0&&lowcosti]<min){//不在生成樹中的頂點而且權(quán)值更小的min=lowcost[];//更新更小的值k=j;//找到了新的點下標給kEQ\*jc3\*hps5\o\al(\s\up10(),j)++;//再看下一個頂點L}lowcost[k]=0;//將這個頂點加入生成樹//生成樹加入了新的頂點從下標為1的頂點開始更新lowcost數(shù)組值lowcost[]=G.arc][];//更新更小的權(quán)值adjvex[]=k;//修改這條邊鄰接的頂點也就是表示這條邊是從選出的頂點k指過來的方便打印}}}0000000001145}找頂點找頂點更新數(shù)組生成樹中//由于剛開始生成樹只有一個頂點不存在邊干脆都設(shè)為0}min=65535;//tip:因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min,L}j++;//再看下一個頂點//生成樹加入了新的頂點從下標為1的頂點開始更新lowcost數(shù)組值從選出的頂點k指過來的方便打印}}}雙重循環(huán)，外層循環(huán)次數(shù)而且時間復(fù)雜度只和n有關(guān)，所以適合稠密圖}換一種思路，我們可以從網(wǎng)中的邊這個角度，找最小權(quán)值的邊，直到找到n-1條邊?？唆斔箍査惴ㄋ悸罚簩D中邊按照權(quán)值從小到大排列，然后從最小的邊開始掃描，設(shè)置一個邊的集合來記錄，如果該邊并入不構(gòu)成回路的話，則將該邊并入當(dāng)前生成樹。直到所有的邊都檢測完為止。并查集并查集0012345670123并查集4567444集合B011集合A集合A查找某個集合的根結(jié)點：//循環(huán)尋找x的//循環(huán)尋找x的根}合并兩個集合：}合并0110444A和B合并}}}}克魯斯卡爾算法inta,b;//邊的兩個頂點while(parent[x]>=0)x=parent[x];//循環(huán)向上尋找下標為x頂點的根returnx;//while循環(huán)結(jié)束時找到了根的下標Edgeedges|MaxEdge];//邊數(shù)組intparent[MaxVex];//父親頂點數(shù)組(并查集)inti,n,m;sort(edges);//按權(quán)值由小到大對邊排列n=Find(parent,edges[].a);//n是這條邊的第一個頂點的根頂點所在下標m=Find(parent,edges[].b);//m是這條邊第二個頂點的根頂點所在下標if(n!=m){//根頂點不相同這條邊不會構(gòu)成環(huán)parent[n]=m;//并操作//作為生成樹的一條邊打印出來printf(“(%d->%d)”,edge}起點46515236663權(quán)值23458}}}}typedefstruct{n=Find(parent,edges[].a);//n是這條邊的第一個頂點的根頂點所在下標if(n!=m){//根頂點不相同這條邊不會構(gòu)成環(huán)printf(“(%d->%d)”,edg}起點46515236663權(quán)值23458}}}}typedefstruct{n=Find(parent,edges[].a);//n是這條邊的第一個頂點的根頂點所在下標if(n!=m){//根頂點不相同這條邊不會構(gòu)成環(huán)printf(“(%d->%d)”,edg}起點46515236663權(quán)值23458}}}}typedefstruct{n=Find(parent,edges[].a);//n是這條邊的第一個頂點的根頂點所在下標if(n!=m){//根頂點不相同這條邊不會構(gòu)成環(huán)printf(“(%d->%d)”,edg}起點46515236663權(quán)值23458}}}}typedefstruct{n=Find(parent,edges[].a);//n是這條邊的第一個頂點的根頂點所在下標printf(“(%d->%d)”,edg}起點46515236663權(quán)值23458}}}}typedefstruct{6n=Find(parent,edges[].a);//n是這條邊的第一個頂點的根頂點所在下標printf(“(%d->%d)”,edg}起點46515236663權(quán)值23458}}}}typedefstruct{6n=Find(parent,edges[].a);//n是這條邊的第一個頂點的根頂點所在下標if(n!=m){//根頂點不相同這條邊不會構(gòu)成環(huán)printf(“(%d->%d)”,edg}起點46515236663權(quán)值23458}}}}typedefstruct{6n=Find(parent,edges[].a);//n是這條邊的第一個頂點的根頂點所在下標if(n!=m){//根頂點不相同這條邊不會構(gòu)成環(huán)printf(“(%d->%d)”,edg}起點46515236663權(quán)值23458}}}}typedefstruct{n=Find(parent,edges[].a);//n是這條邊的第一個頂點的根頂點所在下標if(n!=m){//根頂點不相同這條邊不會構(gòu)成環(huán)printf(“(%d->%d)”,edg}起點46515236663權(quán)值23458}}}}typedefstruct{6n=Find(parent,edges[].a);//n是這條邊的第一個頂點的根頂點所在下標if(n!=m){//根頂點不相同這條邊不會構(gòu)成環(huán)printf(“(%d->%d)”,edg}起點46515236663權(quán)值23458inta,b;//邊的兩個頂點}}克魯斯卡爾算法while(parent[x]>=0)x=parent[x];//循環(huán)向上尋找下標為x頂點的根returnx;//while循環(huán)結(jié)束時找到了根的下標Edgeedges|MaxEdge];//邊數(shù)組intparent[MaxVex];//父親頂點數(shù)組(并查集)inti,n,m;sort(edges);//按權(quán)值由小到大對邊排列n=Find(parent,edges[].a);//n是這條邊的第一個頂點的根頂點所在下標m=Find(parent,edges[].b);//m是這條邊第二個頂點的根頂點所在下標if(n!=m){//根頂點不相同這條邊不會構(gòu)成環(huán)parent[n]=m;//并操作//作為生成樹的一條邊打印出來printf(“(%d->%d)”,edge由于n=m說明加入1-5會產(chǎn)生環(huán)所以什么都不執(zhí)行}起點46515236663權(quán)值23458}}}}typedefstruct{n=Find(parent,edges[].a);//n是這條邊的第一個頂點的根頂點所在下標if(n!=m){//根頂點不相同這條邊不會構(gòu)成環(huán)printf(“(%d->%d)”,edg}起點46515236663權(quán)值23458}}typedefstruct{n=Find(parent,edges[].a);//n是這條邊的第一個頂點的根頂點所在下標if(n!=m){//根頂點不相同這條邊不會構(gòu)成環(huán)printf(“(%d->%d)”,edg}起點46515236663權(quán)值23458}}}}typedefstruct{n=Find(parent,edges[].a);//n是這條邊的第一個頂點的根頂點所在下標if(n!=m){//根頂點不相同這條邊不會構(gòu)成環(huán)printf(“(%d->%d)”,edg}起點46515236663權(quán)值23458}}}}typedefstruct{n=Find(parent,edges[].a);//n是這條邊的第一個頂點的根頂點所在下標if(n!=m){//根頂點不相同這條邊不會構(gòu)成環(huán)printf(“(%d->%d)”,edg}起點46515236663權(quán)值23458}}}}typedefstruct{n=Find(parent,edges[].a);//n是這條邊的第一個頂點的根頂點所在下標if(n!=m){//根頂點不相同這條邊不會構(gòu)成環(huán)printf(“(%d->%d)”,edg}起點46515236663權(quán)值23458typedefstruct{for(i=0;i<G.arcnum;i++){//掃描每條邊n=Find(parent,edges[].a);//n是這條邊的第一個頂點的根頂點所在下標if(n!=m){//根頂點不相同這條邊不會printf(“(%d->%d)”,edg}}}克魯斯卡爾算法操作分為對邊的權(quán)值排序部分和一時間大于單重循環(huán)，所以克魯斯卡爾算法的主要時間耗費在排序上。排序和圖中邊的數(shù)量有關(guān)系，所最小生成樹圖的應(yīng)用(2)最短路徑最短路徑我們經(jīng)常會面臨路徑?jīng)Q策問題C23G8最短路徑迪杰斯特拉該算法設(shè)置一個集合S記錄已求得的最短路徑的頂點，可用一個數(shù)組s□來實現(xiàn)，初始化為0,當(dāng)s[vi]=1時表示將頂點vi放入S中，初始時把源點v0放入S中。此外在構(gòu)造過程中還設(shè)置了兩個輔助數(shù)組：path[:path[]表示從源點到頂點i之間的最短路徑的前驅(qū)結(jié)點，在算法結(jié)束時，可根據(jù)其值追假設(shè)從頂點0出發(fā)，也就是頂點0為源點，集合S最初只包含頂點0,鄰接矩陣arcs表示帶權(quán)有向的步驟如下：1)初始化：集合S初始為{0},dist]的初始值dist[i]=arcs[0][i],i=1,2,…,n-3)修改從v0出發(fā)到集合V-S上任一頂點v可達的最短路徑長度：如果則令dist[k]=dist[]+arcs[][k]。另外更新path[k]=j(也得到頂點k路徑變短的話就將到頂點k的路徑長度修改成較短的)4)重復(fù)2)～3)操作共n-1次，直到所有的頂點都包含在S中。path[4]、path[5]、path[6]都設(shè)為-1(-1表示到該頂點的路徑前驅(qū)頂點不存在，從而表示路徑不存在)頂點數(shù)組s[1]=1其余數(shù)組元素值為0第一步：從除了頂點1外的頂點中選擇dist數(shù)組值最小的頂點2加入最短路徑，所以s[2]=1第二步：以頂點2檢測其他剩余頂點3456dist[j]+arcs[j][k]<dist[k]dist[4]修改為16,path[4]修改為2dist[5]和path[5]不變 下標數(shù)組12345607112S110000下標12345607第一步：從除了頂點123外的頂點中選擇dist數(shù)組值最小的頂點4加入最短路徑，所以s[4]=1第二步：以頂點4檢測其他剩余頂點56①dist[5]=18<dist[4]+arc[4][5]=帝dist[5]和path[5]不變更新后的數(shù)組下標數(shù)組1234560711233S111100迪杰斯特拉下標12345607更新后的數(shù)組 下標數(shù)組1234560711233S111110由于只剩下頂點6所以直接加入頂點6并修改s[6]=19下標數(shù)組1234560711233S111111至此所有頂點都已經(jīng)添加到集合S中。通過這個表可以得到頂點1到其他頂點的最短路徑。①頂點1到頂點2的最短路徑：1->2路徑長度為7②頂點1到頂點3的最短路徑：1->3路徑長度為11③頂點1到頂點4的最短路徑：1->2->4路徑長度為16④頂點1到頂點5的最短路徑：1->3->5路徑長度為18⑤頂點1到頂點6的最短路徑：1->3->6路徑長度為19inti,j,min,u;}//下面的循環(huán)中包含兩部分作用：①內(nèi)層第一個for循環(huán)是找到到剩余頂點中距離最小的頂點u并把它加入最短路徑u=j;//u用于保存當(dāng)前找到的距離最小的頂點下標當(dāng)循環(huán)結(jié)束u保存}}s[u]=1;//到u的距離是最小的，所以把頂點u加入最短路徑}時間復(fù)雜度：迪杰斯特拉算法的核心部分在于一個雙重循環(huán)，這個雙重循環(huán)的內(nèi)循環(huán)又是兩個并列的迪杰斯特拉算法的時間復(fù)雜度為O(n2)其中n為圖中的頂點數(shù)。迪杰斯特拉算法不能用于權(quán)值有負數(shù)的圖，不然結(jié)果會出錯!比如左圖，顯然頂點1到頂點2的最短路徑是1->2,路徑長度為4,但是經(jīng)過迪杰斯特拉算法得到的結(jié)果卻是從1->3->2,路徑長度為5-弗洛伊德弗洛伊德算法是求圖中任意一對頂點間的最短路徑的算法算法思想：驟。初始時，對于任意兩個頂點v,和v,若它們之間存在邊，則以此邊上的權(quán)值作為它們之間的最短路徑長度；若它們之間不存在有向邊，則以作為它們之間的最短路徑長度。以后逐步嘗試在原路徑中加入頂點k(k=0,1,…,n-1)作為中間頂點。如果增加中間頂點后，得到的路徑比原來的路徑長度減少了，弗洛伊德4弗洛伊德算法需要維護兩個矩陣A和Path,矩陣A用來記錄當(dāng)前任意兩個頂點的最短路徑長度矩陣Path用來記錄當(dāng)前兩頂點間最短路徑上要經(jīng)過的中間頂點上標里的數(shù)字表示每一步中所選中的中間頂點弗洛伊德4BCD01230053120520103640A[3][1]=o>A[3][0]+A[0][1]4A[0][2]=o>A[0][1]+A[1][2]A[0][3]=o>A[0][1]+A[1][3]A[3][2]=o>A[3][1]+A[1][4A[1][0]=o>A[1][2]+A[2][0]54012306531205231○637540A120752310637540到這里弗洛伊德算法就執(zhí)行完畢弗洛伊德算法的核所以時間復(fù)雜度為O(n3)其中n是圖中弗洛伊德算法的核所以時間復(fù)雜度為O(n3)其中n是圖中}離長，則更新從頂點到頂點j的距離為較小值，并且存儲k表示路徑經(jīng)過頂點k}}}}圖的應(yīng)用(3)拓撲排序錄取復(fù)試錄取初試現(xiàn)場確認考研報名初試現(xiàn)場確認調(diào)劑調(diào)劑拓撲排序拓撲序列是對圖中所有的頂點，如果存在一條從頂點A到頂點B的路徑，那么在排序中頂點A出現(xiàn)在頂點B的前面。拓撲排序就是對一個有向圖構(gòu)造拓撲序列的過程，構(gòu)造會有兩種結(jié)果：如果此圖全部頂點都被輸出了，說明它是不存在回路的AOV網(wǎng)；如果沒有輸出全部頂點，則說明這個圖存在回路，不是AOV網(wǎng)。拓撲排序算法：從AOV網(wǎng)中選擇一個入度為0的頂點輸出，然后刪去此頂點，并刪除以此頂點為弧尾的弧。重復(fù)這個步驟直到輸出圖中全部頂點，或者找不到入度為0的頂點為止。求右邊這個有向圖的拓撲序列第①輪第一步：選擇入度為0的頂點輸出，比如選1號第二步：刪除1號頂點第三步：刪除以1號頂點為弧尾的邊一個DAG一個DAG的拓撲排序不唯一第一步：選擇入度為0的頂點輸出，可以選擇2號也可以選擇4號以選2號為例第二步：刪除2號頂點第三步：刪除以2號頂點為弧尾