福大真題數(shù)據(jù)結(jié)構(gòu)課件graph

1線性表、堆棧、隊(duì)1線性表、堆棧、隊(duì)圖本課件部分資源引自互聯(lián)?和相關(guān)書籍?2，不便??列出來(lái)源，在此?并圖本課件部分資源引自互聯(lián)?和相關(guān)書籍?2，不便??列出來(lái)源，在此?并圖的定義和表示7.1-7.6-圖的定義和表示7.1-7.6-344566定比層次結(jié)構(gòu)定比層次結(jié)構(gòu)更加復(fù)雜的非線性結(jié)層次關(guān)系中（樹），每個(gè)結(jié)點(diǎn)只有一個(gè)父本質(zhì)上是一種多對(duì)多的關(guān)頂點(diǎn)的非空有限集合V和邊（頂點(diǎn)對(duì)）的有限集(可為空)E所組成的二元組G，記為G=(V,7衍生概有衍生概有向(u,v)中u為起點(diǎn)，v為終點(diǎn)，(v,u)中v無(wú)向(u,v)和(v,u)是同一條8簡(jiǎn)單簡(jiǎn)單圖中的每條邊均帶有一個(gè)賦權(quán)有向圖和賦權(quán)無(wú)向圖統(tǒng)稱為網(wǎng)9完全完全無(wú)向圖：0<=e<=n(n-1)/2有向圖：0<=e<=n(n-完全無(wú)向完全有向其它術(shù)其它術(shù)關(guān)無(wú)向邊(u,v)中，頂點(diǎn)u和v互為鄰接點(diǎn)/相鄰接，(u,v)關(guān)聯(lián)于頂點(diǎn)u和有向邊(u,v)中，終點(diǎn)v是起點(diǎn)u的鄰接頂點(diǎn)(u,v)關(guān)聯(lián)于頂點(diǎn)u和頂點(diǎn)的無(wú)向圖中頂點(diǎn)v的度就是關(guān)聯(lián)于該頂點(diǎn)的邊的數(shù)有向圖以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目稱為v的入度以頂點(diǎn)v為起點(diǎn)的邊的數(shù)目稱為v的出度頂點(diǎn)數(shù)n，邊數(shù)e和度數(shù)之間的關(guān)系例 例 頂點(diǎn)2例 頂點(diǎn)4入度 出度子G=(V,E)，G’=(V’,E’)，V’是V子G=(V,E)，G’=(V’,E’)，V’是V路頂點(diǎn)序列u(1),u(2),…,u(m)，使有向圖中路徑也是有向簡(jiǎn)單路簡(jiǎn)單路除了起點(diǎn)和終點(diǎn)可能相同外，其余頂點(diǎn)均不相同起點(diǎn)和終點(diǎn)相同的簡(jiǎn)單路徑稱為簡(jiǎn)單回連通圖和連通分頂點(diǎn)u和v之間存在一條路徑，稱u和v是連通的?u和v，兩者都是連通的，則稱無(wú)向圖通圖無(wú)向圖G的極大連通子圖稱為G的連通分任何連通圖只有自身一個(gè)連通分非連通圖有多個(gè)連通分強(qiáng)連通圖強(qiáng)連通圖和強(qiáng)連通分有向圖中?u和v，存在著從u到v和任何強(qiáng)連通圖只有自身一個(gè)強(qiáng)連通分非強(qiáng)連通有向圖有多個(gè)強(qiáng)連通分有根頂點(diǎn)v即為該有根圖的ADTADTADT基本運(yùn)ADT基本運(yùn)GraphAdd(i,j,G)GraphDelete(i,j,G)Degree(i,G)OutDegree(i,G)InDegree(i,G)備以有向圖為基本無(wú)向圖中的一條邊(u,v)用兩條有向邊(u,v)和(v,u)代結(jié)點(diǎn)集合：一般可以用1...n來(lái)進(jìn)行編號(hào)結(jié)點(diǎn)集合：一般可以用1...n來(lái)進(jìn)行編號(hào)12例34例12^345^^^^^^12例34例12^345^^^^^^i,j,wi為兩條有向加權(quán)邊i－>j和j->i，權(quán)重均為w空間耗有向圖空間耗有向圖無(wú)向圖利用無(wú)向圖鄰接矩陣對(duì)稱性，僅保存上三角或下三角部分，從而節(jié)省一半時(shí)間耗費(fèi)：輸入和查看n思類似樹的思類似樹的兒子鏈表表示稀疏型圖用鄰接表表示比鄰接矩陣表示有 有向 有向 ?向typedefstructgraphstructtypedefstructgraphstructn;//WItem//??i,j??//?(i,j)???????????創(chuàng)建一個(gè)有n個(gè)孤創(chuàng)建一個(gè)有n個(gè)孤立頂點(diǎn)的賦權(quán)有向圖二維矩陣中每個(gè)元素初始化為無(wú)邊標(biāo)記GraphGraphinit(intn,WItemGraphG=malloc(sizeof*G);G->a=Make2DArray(G->n+1,G-//圖的頂點(diǎn)編號(hào)為1-n，因此開(kāi)辟二維數(shù)組return{}GraphVertices(G)???????GraphVertices(G)???????intGraphVertices(GraphG){returnG-GraphEdges(G)???????intGraphEdges(GraphG){returnG-GraphExist(i,j,G)????(i,j)??intGraphExist(inti,intj,Graph{if(i<1||j<1||i>G->n||j>G->n||G->a[i][j]==G->NoEdge)return0;} voidGraphAdd(inti,intj, voidGraphAdd(inti,intj,WItemw,Graph{if(i<1||j<1||i>G->n||j>G->n||G->a[i][j]!==G-rrr("dG-}voidGraphDelete(inti,intj,Graph{if(i<1||j<1||i>G->n||j>G->n||G->a[i][j]==G-/?,rrr("dG->a[i][j]=G-}? ? intOutDegree(inti,Graph{intif(i<1||i>G->n)Error("BadInput");for(j=1;j<G->n);j++)if(G->a[i][j]!=G->NoEdge)sum++;returnsum;}? intInDegree(inti,Graph{intif(i<1||i>G->n)Error("BadInput");for(j=1;j<G->n);j++)if(G->a[j][i]!=G->NoEdge)sum++;returnsum;}voidGraphOut(GraphG{intfor(i=1;i<=G->n;{for(j=1;j<=G->n;j++)WItemShow(G-printf("\n}擴(kuò)展將無(wú)向擴(kuò)展將無(wú)向圖視為有向圖來(lái)GraphAdd(i,j,w,G)在圖G中加入一條權(quán)重為w的GraphDelete(i,j,G)在圖中刪除邊(i,j)的同時(shí)還應(yīng)G->e--????????????0?????? ?????????????Graph{GraphG=malloc(sizeof*G);G-G->a=Make2DArray(G->n+1,G-return擴(kuò)展每條邊的權(quán)重?cái)U(kuò)展每條邊的權(quán)重為1,無(wú)邊時(shí)邊權(quán)為無(wú)向圖中的一條邊(u,v)用兩條有向邊(u,v)和(v,u)代替直觀體所有賦權(quán)無(wú)向圖實(shí)現(xiàn)中取消權(quán)重的概念w出現(xiàn)處均直接置為1NoEdge出現(xiàn)處均直接置為0GraphAdd(i,j,G)在圖G中加入邊(i,j)的同時(shí)還應(yīng)加入G-(i,j,G)在圖中刪除邊(i,j)的同時(shí)還應(yīng)刪除G->e--有向圖和無(wú)向圖鄰接表結(jié)點(diǎn)結(jié)構(gòu)有向圖和無(wú)向圖鄰接表結(jié)點(diǎn)結(jié)構(gòu)typedefstructlnodestruct//???}glinkNewLNode(intv,glink{glinkx=malloc(sizeofx->v=v;x->next=next;returnx;}鄰接表實(shí)鄰接表實(shí)現(xiàn)下有向圖和無(wú)向圖的結(jié)構(gòu)定typedefstructgraphgraph{int/?GraphintGraphG=malloc(sizeof*G);G-for(i=0;i<=n;i++)returnG;{}在結(jié)點(diǎn)在結(jié)點(diǎn)i的鄰接表中線性掃描是否包含intGraphExist(inti,intj,Graph{glinkif(i<1||j<1||i>G->n||j>G->n)return0;while(p&&p->v!=j)p=p->next;if(p)return1;elsereturn}在結(jié)點(diǎn)i的鄰在結(jié)點(diǎn)i的鄰接表中增加一個(gè)結(jié)點(diǎn)包含voidGraphAdd(inti,intj,Graph{if(i<1||j<1||i>G->n||j>G->n||i==j||GraphExist(i,j,G))Error("BadInput");//??????????????(i,j)G->adj[i]=NewLNode(j,G-}在結(jié)點(diǎn)i的鄰接表中在結(jié)點(diǎn)i的鄰接表中刪除包含j的結(jié)voidGraphDelete(inti,intj,Graph{if(i<1||j<1||i>G->n||j>G->n||!GraphExist(i,j,G))Error("BadInput");//???????????????(i,j)p=G->adj[i];//??(p-{G->adj[i]=p-{while(p&&p->next->v!=j)p=p-if(p){q=p->next;p->next=q->next;}}intOutDegree(inti,Graph{glinkp;intif(i<1i>G->n)Error("Badp=G-while(p){j++;p=p->next;}returnj;}對(duì)于j=1,…,n，計(jì)算邊(j,i)存在的條intInDegree(inti,Graph{intj,if(i<1i>G->n)Error("Badfor(j=1;j<=G->n;if(GraphExist(j,i,G))sum++;returnsum;}輸出有向圖G的鄰接void輸出有向圖G的鄰接voidGraphOut(Graph{glinkp;inti;for(i=1;i<=G->n;{while(p){printf("%d",p-printf("\np=p-}}?????? ?G->adj[i]=NewLNode(j,G- ?G->adj[j]=NewLNode(i,G-G->e++;if(p->v==i){G->adj[j]=p->next;free(p);}else{while(p&&p->net->v!=i)p=p->next;if(p){q=p->next;p->next=q->next;要求：每個(gè)頂點(diǎn)對(duì)應(yīng)的鄰接表要求：每個(gè)頂點(diǎn)對(duì)應(yīng)的鄰接表結(jié)點(diǎn)中除了存儲(chǔ)和該頂點(diǎn)相鄰接的頂點(diǎn)以方法:修訂鄰接表結(jié)點(diǎn)類型與賦權(quán)有向圖要求相適typedefstructlnode*glink;structlnode{intv;//邊的另一個(gè)頂WItemw;//邊next;//鄰接表指針，指向鄰接表的下一個(gè)}glinkNewLWNode(intv,WItemw,glink//創(chuàng)建一個(gè)新的鄰接表結(jié)點(diǎn)并插入至next{glinkx=malloc(sizeofx->v=v;x->w=w;x->next=next;returnx;}鄰接表下賦權(quán)有向圖的結(jié)構(gòu)定義和有向圖的結(jié)構(gòu)定義一致成員函成員函數(shù)的實(shí)GraphGraphinit(int{intGraphG=malloc(sizeo*G);G-for(i=0;i<=n;i++)G->adj[i]=0;returnG;}GraphAdd(i,j,w,G)在圖GraphAdd(i,j,w,G)在圖中加入一條權(quán)G->adj[i]=NewLWNode(j,w,G-if(p){q=p->next;p->next=q->next;if(p){q=p->next;p->next=q->next;}????????????????w?(i,j)??????w?? ???(i,j) ???(j,i) p=G->adj[j];//???(j,i)if(p->v==i){G->adj[j]=p->next;11掌握無(wú)圈有向圖DAG的拓?fù)渑判蚣捌鋺?yīng)用關(guān)鍵路掌握構(gòu)造最小支撐樹的Prim算法——貪心算法策例廣度例廣度遍歷V2?V3?V4?V5?V6?V7深度遍歷V2?V4?V8?V5?V3?V6基本基本在依次訪問(wèn)v的每一個(gè)未被訪問(wèn)過(guò)的鄰接頂點(diǎn)之后，分別從這些鄰接頂點(diǎn)出發(fā)，遞歸地以廣度優(yōu)先方式搜索圖以廣度優(yōu)先搜索策略遍歷圖的過(guò)程是以一個(gè)頂點(diǎn)v為起始頂點(diǎn)，由近及遠(yuǎn)，依次訪問(wèn)和v有路相通，且路徑長(zhǎng)度為1,2,…,的頂點(diǎn)——類似于樹的層序遍歷標(biāo)記頂點(diǎn)v//從頂點(diǎn)v開(kāi)始，廣度優(yōu)先遍歷圖的算法標(biāo)記頂點(diǎn)v//從頂點(diǎn)v開(kāi)始，廣度優(yōu)先遍歷圖的算法設(shè)u是wwhileQ}u=w}}具體實(shí)現(xiàn)的時(shí)候可以用一個(gè)數(shù)組pre來(lái)記錄頂點(diǎn)被訪問(wèn)的先后次序，同時(shí)防止頂點(diǎn)被重復(fù)訪問(wèn)初始化時(shí)所有頂點(diǎn)v有錄途中頂點(diǎn)的訪問(wèn)次序，每訪問(wèn)一個(gè)頂點(diǎn)，即pre[v]=cnt++，算法結(jié)鄰接矩陣下無(wú)向圖的廣度優(yōu)先搜索鄰接矩陣下無(wú)向圖的廣度優(yōu)先搜索算法bfsvoidbfs(GraphG,int{intQueueq=QueueInit();whileif{for(j=1;j<=G->n;if(G->a[i][j])if(pre[j]==0)}例}缺如何改進(jìn)voidbfs(GraphG,int{intj;Queueq=QueueInit();(!QueueEmpty(q)){i=Deletfor(j=1;j<=G->n;if((G->a[i][j])&&{EnterQueue(j,q);}時(shí)間復(fù)雜時(shí)間復(fù)雜nbfssBSO(s*n)O(∑OD())思考題：鄰接表下的BFS如何實(shí)現(xiàn)BFS下圖的遍BFS下圖的遍歷算調(diào)用一次BS可以訪問(wèn)圖中起始頂點(diǎn)所在連通分支中的所有頂點(diǎn)，但不能訪問(wèn)圖中和連通的其它頂點(diǎn)調(diào)用一次BFS只能遍歷圖G的一個(gè)連通分支圖為連通圖——一次BFS可以遍歷圖G的所有頂點(diǎn)圖G為非連通圖——包含多個(gè)連通分一次BS只能訪問(wèn)一個(gè)連通分支，剩余連通對(duì)每一個(gè)連通分支調(diào)用一次for(i=1;i<G->n;i++)for(i=1;i<=G->n;if(pre[i]==0)例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^廣度遍歷vexdata例adjvex1234567837^2^88^6^74^1234567^8^2^廣度遍歷vexdata例adjvex1234567837^2^88^6^74^1234567^8^2^?廣度遍歷例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^?廣度遍歷例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^?V2廣度遍歷例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^?V2廣度遍歷例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^?V2?V7廣度遍歷例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^?V2?V7廣度遍歷例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^?V2?V7?V6廣度遍歷例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^?V2?V7?V6廣度遍歷例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^?V2?V7?V6?V4廣度遍歷例vexdataadjvex1234567837^2^88^6^74^1234567^?V2?V7?V6?V4廣度遍歷例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^?V2?V7?V6?V4?V8廣度遍歷例vexdataadjvex1234567837^2^88^6^74^1234?V2?V7?V6?V4?V8廣度遍歷例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^?V2?V7?V6?V4?V8?廣度遍歷例vexdataadjvex1234567837^2^88^6^74^12?V2?V7?V6?V4?V8?廣度遍歷例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^圖的廣度圖的廣度優(yōu)先遍歷時(shí)間復(fù)雜鄰接表表示法下，廣度優(yōu)先遍歷所需時(shí)為基本思基本思將V中的每一個(gè)頂點(diǎn)都標(biāo)記為未被選取一個(gè)頂點(diǎn)v∈V，開(kāi)始搜索，標(biāo)記v為已訪遞歸調(diào)用深度優(yōu)先搜索方法，依次搜索v的每一個(gè)訪問(wèn)過(guò)的鄰接頂直至從v出發(fā)有路徑可達(dá)的頂點(diǎn)都已經(jīng)被訪問(wèn)過(guò)盡可能地先對(duì)縱深方向進(jìn)行搜當(dāng)前訪問(wèn)頂點(diǎn)為x，下一步選擇x的鄰接頂點(diǎn)y進(jìn)訪問(wèn)，緊接著由頂點(diǎn)y出發(fā)，選擇y的鄰接頂點(diǎn)z行訪問(wèn)，形成68點(diǎn)x出發(fā)的一個(gè)縱深搜索序 vexdata adjvex 32 456782834567^8^7^2^8^6^74^2 vexdata adjvex 32 456782834567^8^7^2^8^6^74^2^ 深度遍歷 vexdata adjvex 32 456782834567^8^7^2^ 深度遍歷 vexdata adjvex 32 456782834567^8^7^2^8^6^74^2^ 深度遍歷：V1?V3 vexdata adjvex 32 456782834567^8^7 深度遍歷：V1?V3 vexdata adjvex 32 456782834567^8^7^2^8^6^74^2^ 深度遍歷：V1?V3?V7 vexdata adjvex 32 456782834567 深度遍歷：V1?V3?V7 vexdata adjvex 32 456782834567^8^7^2^8^6^74^2^ 深度遍歷：V1?V3?V7?V6 vexdata adjvex 32 456782834 深度遍歷：V1?V3?V7?V6 vexdata adjvex 32 456782834567^8^7^2^8^6^74^2^ 深度遍歷：V1?V3?V7?V6?V2 vexdata adjvex 32 45678 深度遍歷：V1?V3?V7?V6?V2 vexdata adjvex 32 456782834567^8^7^2^8^6^74^2^ 深度遍歷：V1?V3?V7?V6?V2?V4 vexdata adjvex 32 4 深度遍歷：V1?V3?V7?V6?V2?V4 vexdata adjvex 32 456782834567^8^7^2^8^6^74^2^ 深度遍歷：V1?V3?V7?V6?V2?V4?V8 vexdata adjvex 32 深度遍歷：V1?V3?V7?V6?V2?V4?V8 vexdata adjvex 32 456782834567^8^7^2^8^6^74^2^ 深度遍歷：V1?V3?V7?V6?V2?V4?V8? vexdata adjvex 32 深度遍歷：V1?V3?V7?V6?V2?V4?V8? vexdata adjvex 32 456782834567^8^7^2^8^6^74^2^算法描遞歸實(shí)鄰接矩算法描遞歸實(shí)鄰接矩陣下無(wú)向圖G中深度優(yōu)先搜索算法voiddfs(GraphG,int{intj;for(j=1;j<=G->n;if(G-if(pre[j]==0)}鄰接表下有向圖G中深度優(yōu)先搜索算法voiddfs(GraphG,int{glinkp;for(p=G->adj[i];p;p=p-if(pre[p->v]==0)dfs(G,p-}一次遞歸搜索找到一個(gè)連通分支，時(shí)間復(fù)雜性同廣 先搜索時(shí)間復(fù)雜 深度優(yōu)先搜索方式下的圖的遍歷voidGraphSearch(Graph{intfor深度優(yōu)先搜索方式下的圖的遍歷voidGraphSearch(Graph{intfor(i=1;i<G->n;i++)for(i=1;i<=G->n;if(pre[i]==0)}Floyd問(wèn)題問(wèn)題給定V中的一個(gè)頂點(diǎn)，稱為常用Dijkstra荷蘭計(jì)算機(jī)科學(xué)家艾茲赫爾·戴克斯特（EdsgerWybeDijkstra）（1972年圖靈獎(jiǎng)獲得者）算法策略——貪心重點(diǎn)——貪心策略的應(yīng)用和邊的源點(diǎn)：1，最短路徑估計(jì)源點(diǎn)：1，最短路徑估計(jì)011-22有兩條出邊：2-3和2-123456頂點(diǎn)?01∞∞∞????014∞∞????0184????123456頂點(diǎn)?01∞∞∞????014∞∞????0184????0184???0184????0184Dijkstra算Dijkstra算頂點(diǎn)集合V-特殊路徑：設(shè)u是V-S中的某一個(gè)頂點(diǎn)，把從源頂點(diǎn)s到u且中間只經(jīng)過(guò)S中頂點(diǎn)的路徑稱為123456?01∞∞∞????014∞∞???0184算法前算法前設(shè)置一個(gè)頂點(diǎn)集合重點(diǎn)：一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源算法步驟：貪心選擇與邊的松弛交替使用初始時(shí)，中僅含有源頂點(diǎn)s,V-余的所有頂點(diǎn)初始化數(shù)組每次從V-S中取出具有最短特殊路徑長(zhǎng)度的頂點(diǎn)u（貪心策略的應(yīng)用），將u添加到S中，同時(shí)對(duì)數(shù)組dist做必要的修改(邊42422213164233542422213164233542422012136423354242201213642335224422012136423352244220121364233522442201213642334522442201213642334522∞442201213642334522∞442201213642334522∞442201213642334522∞4422012136423345∞22∞442201213∞642334522∞442201213∞6423345∞22∞442201213∞642334522∞442201213∞6423345∞∞4422201213∞642335∞∞4422201213∞642335∞∞4422201213∞642335∞∞4422201213∞642335∞22∞442201213∞642335∞22∞442201213∞642335∞22∞442201213∞642335∞22∞442201213∞642335∞22∞442201213∞642335∞22∞442201213∞642335∞22∞442201213∞6423345∞22∞442201213∞6423345∞22∞442201213∞6423345∞22∞442201213∞6423345∞22∞442201213∞6423345∞22∞442201213∞6423345∞22∞442201213∞6423345∞22∞442201213∞6423345∞???22∞442201213∞6423345∞貪?選22∞442201213∞6423345∞貪?選22∞442201213∞6423345∞貪?選22∞442201213∞6423345∞貪?選22∞442201213∞6423345∞貪?選??222∞442201213∞6423345∞貪?選??2?????22∞442201213∞6423345∞邊的松22∞442201213∞6423345∞邊的松22∞442201213∞6423345∞邊的松22∞442201213∞6423345∞邊的松22∞442201213∞6423345∞邊的松22∞442201213∞6423345∞邊的松22∞442201213∞6423345∞3邊的松22∞442201213∞6423345∞3邊的松22∞442201213∞6423345∞3邊的松22∞442201213∞6423345∞3邊的松22∞442201213∞6423345∞3邊的松22∞442201213∞6423345∞3邊的松22∞442201213∞6423345∞3邊的松22∞442201213∞6423345∞3邊的松6∞22442201213∞6423345∞3邊的松6∞22442201213∞6423345∞3邊的松6∞22442201213∞6423345∞3邊的松6∞22442201213∞6423345∞3邊的松6∞22442201213∞6423345∞3邊的松6∞22442201213∞6423345∞3邊的松6∞22442201213∞6423345∞43邊的松6∞22442201213∞6423345∞43邊的松6∞22442201213∞6423345∞43????3?4?56∞22442201213∞6423345∞43????3?4?5???4???5????????????邊的松??????????226442201213∞64233354貪?選226442201213∞64233354貪?選226442201213∞64233354貪?選226442201213∞64233354貪?選226442201213∞64233354邊的松226442201213∞64233354邊的松226442201213∞64233354邊的松226442201213∞64233354邊的松226442201213∞64233354 dist(5)沒(méi)有變 邊的226442201213∞64233354 dist(5)沒(méi)有變 邊的松226442201213∞64233354貪?選226442201213∞64233354貪?選226442201213∞64233354貪?選226442201213∞64233354貪?選226442201213∞64233354邊的松226442201213∞64233354邊的松226442201213∞64233354邊的松226442201213∞64233354邊的松226442201213∞64233354 dist(4)沒(méi)有變 邊的226442201213∞64233354 dist(4)沒(méi)有變 邊的松226442201213∞64233354 dist(4)沒(méi)有變 邊的226442201213∞64233354 dist(4)沒(méi)有變 邊的松226442201213∞64233354 dist(4)沒(méi)有變 邊的松226442201213∞64233354 dist(4)沒(méi)有變 邊的松2264422016∞21364233354 dist(4)沒(méi)有變 邊的2264422016∞21364233354 dist(4)沒(méi)有變 邊的松226442201213664233354貪?選226442201213664233354貪?選226442201213664233354貪?選226442201213664233354貪?選226442201213664233354邊的松226442201213664233354邊的松226442201213664233354邊的松226442201213664233354邊的松226442201213664233354 dist(6)沒(méi)有改 邊226442201213664233354 dist(6)沒(méi)有改 邊的松226442201213664233354貪?選226442201213664233354貪?選226442201213664233354貪?選226442201213664233354貪?選226442201213664233354226442201213664233354226442201213664233354 226442201213664233354 226442201213664233354 226442201213664233354 226442201213664233354226442201213664233354Dijkstra算法描??????Dijkstra算法描???????dist[v]??????s???v???????prev[v]????s???v????????v??????LS?????s???????????dist[v]=a[s][v],???????L?????prev[v]<>0???v//???? ?3Step2: ???for(i=1;i<=G->n;i++){dist[i]=a[s][i];if(dist[i]for(i=1;i<=G->n;i++){dist[i]=a[s][i];if(dist[i]==G->NoEdge)prev[i]={prev[i]=s;} ?st?re(!ListEmpty())??//???v??L???????dist??intiListDelMin(L,dist);//P.154for(intj=1;j<=G->n;j++)if(G->a[i][j]!=G-&&(!prev[j]||dist[j]>dist[i]+G-//dist[j]dist[j]=dist[i]+G-if(!prev[j]){//L???jL}}數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)說(shuō)dist數(shù)組的作prev數(shù)組的作實(shí)現(xiàn)最短路徑的回計(jì)算結(jié)束后可以根據(jù)數(shù)組prev找到從源s到v的最短路徑上的每個(gè)頂點(diǎn)的前一個(gè)頂點(diǎn)，從而找到從源s到v時(shí)間復(fù)雜性：鄰接矩陣實(shí)現(xiàn)下dist[x]<=d(s,x)d(x,u)>=0—dist[i新的特殊路徑先經(jīng)過(guò)老的S到達(dá)頂點(diǎn)u新的特殊路徑先經(jīng)過(guò)老的S到達(dá)頂點(diǎn)uu經(jīng)過(guò)一條邊直接到達(dá)頂點(diǎn)FORDFORDBellman-Ford算法——Dijkstrafor(k=1;k<=n-1k++)//進(jìn)?n-1輪松弛for(i=1;i<=e;i++)//枚舉每?條邊{時(shí)間復(fù)雜}}基本思基本思動(dòng)態(tài)規(guī)劃dist2[u],…distn-1[u]當(dāng)s到u存在一條邊(s,u)時(shí)當(dāng)k>1時(shí)，distk[u]如何求解當(dāng)前問(wèn)題：當(dāng)k>1時(shí)，需要求解tkik[]為從s到u的最多經(jīng)過(guò)G中k條邊的最短從s到u的最多經(jīng)過(guò)G中k條邊的路徑滿足三個(gè)條件最后一條邊一定是一條和頂點(diǎn)u關(guān)聯(lián)的邊從s到v最多經(jīng)過(guò)G中k-1條3.對(duì)于任何一條從s到u最多經(jīng)過(guò)G中k條邊的路徑而言，其長(zhǎng)度pahku=pthk-v+ev,)要求解ditk[u]，即要求解最小的path[k,u]=min{path[k-1,v]+e(v,u)|(v,u)∈=min{min(path[k-1,v])+e(v,u)|(v,u)∈=min{distk-1[v]+e(v,u)|(v,u)∈b5-3a0cd4Bellman-b5-3a0cd4Bellman-5b53ac40d4Bellman-15b53ac40d4Bellman-15b53ac30d74Bellman-25b53ac30d74Bellman-25 5 43Bellman- <dist1?5b53ac30d64Bellman-35b53ac30d64Bellman-35b53ac30d64Bellman-3?5b53ac30d64Bellman-3?5b530ac3d64Bellman-5b530ac3d64Bellman-2d:0d:∞AB-d:∞21-42d:0d:∞AB-d:∞21-4C51-DE4d:∞d:∞d:0d:∞-2AB-π:nilCd:∞221-4C51d:0d:∞-2AB-π:nilCd:∞221-4C51-DE4d:∞4d:∞d:0d:∞-2AB-π:nilCBd:∞2021-4C51-d:0d:∞-2AB-π:nilCBd:∞2021-4C51-DE4d:∞4π:nild:∞Cd:0d:∞-2AB-π:nilCBd:∞2021-4C51-DEd:0d:∞-2AB-π:nilCBd:∞2021-4C51-DE4d:∞4π:Cd:∞3d:0π:nilAEd:∞-1-2AB-π:nilCBBd:∞20-121-4C51-d:0π:nilAEd:∞-1-2AB-π:nilCBBd:∞20-121-4C51-DE4d:∞4π:Cd:∞3核心問(wèn)如何按照遞核心問(wèn)如何按照遞推公式計(jì)算任意一個(gè)頂點(diǎn)tk由遞推公式distk[u]=min{distk-∈E}分析，可以得知，只有某一個(gè)頂點(diǎn)vdistk-1[v]比distk-2[v]更短時(shí)，需要重新計(jì)算鄰接頂點(diǎn)u的記錄頂點(diǎn)的最短路徑更新次數(shù)，如存在一個(gè)從源可達(dá)的負(fù)權(quán)圈，相應(yīng)頂點(diǎn)的最短路徑將會(huì)不斷更新，否則因?yàn)閺脑吹饺魏我粋€(gè)頂點(diǎn)的最短路徑最多只有n-1條邊，因此，其更新算法依次從隊(duì)列qu中取出更新過(guò)最短路徑長(zhǎng)度的頂點(diǎn)j，對(duì)其鄰接頂點(diǎn)k按照計(jì)算i[]代碼實(shí)代碼實(shí)初始化工遞推計(jì)算while負(fù)權(quán)圈的判if(count[k]>n)printf("cycleofnegativeweightexists!\n");return0;}遞推計(jì)p=G-遞推計(jì)p=G-if(dist[j]>dist[k]+p-{(!ub[j]){ue(j,qu);}}}時(shí)間復(fù)雜性：最壞情況下問(wèn)題問(wèn)題解決方時(shí)間復(fù)雜性為O(3)解決方Floyd-Warshall算1962年，RobertW.Floyd(1978年圖靈獎(jiǎng)獲得同年，Setphen首先考慮路徑（i,1j）是否存在（（i,1）和(1,j)是否存在）。如果存在，則比較（i,j）和（i,1,j）的路徑長(zhǎng)度取長(zhǎng)度較短者為從ij1的最短是說(shuō)，如果（i,1,2）和（2,1,j）分于1的最短路徑，計(jì)算（i,1,2)+(2,1,j），將它和已經(jīng)得到的從i到j(luò)中間頂再增加一個(gè)頂點(diǎn)3，繼續(xù)進(jìn)行試依次類推,…直至增加頂點(diǎn)結(jié)在一結(jié)在一般情況下，若（i,…,k）（k,…,j）分別是從i到k和從k到j(luò)路徑，則將（i,…,k,…,j）和已經(jīng)經(jīng)過(guò)n-2次比較，最后求得的必是i到j(luò)的最短路特每一次的試探都是前一次試探結(jié)上的一次迭代求教材P.158邊權(quán)為負(fù)時(shí)，F(xiàn)loyd解決方解決方n*n的耗費(fèi)矩陣初始時(shí)，0j第k次迭代前，當(dāng)前k[ij]的值表大于k-1的頂點(diǎn)的最短路徑長(zhǎng)度，k[,]+k[kj]表示從頂點(diǎn)i到頂點(diǎn)k，再?gòu)膋到j(luò)，且中間不經(jīng)過(guò)編號(hào)大于k的頂點(diǎn)的最短路徑長(zhǎng)度k,jmk[,j],ck-經(jīng)過(guò)第k次迭代之后，k的值是點(diǎn)的最短路徑長(zhǎng)Floyd算法for(inti=1;i<=G->n;Floyd算法for(inti=1;i<=G->n;for(intj=1;j<=G->n;{}c[i][j]=path[i][j]=for(inti=1;i<=G->n;i++)for(intk=1;k<=n;k++)for(inti=1;i<=n;for(intj=1;j<=n;{t1=t2=t3=c[i][i]=if(t1!=G->NoEdge&&t2!=G-(t3==G-{c[i][j]=t1+?cij]?jt[i][j] }二維數(shù)組path的作用：幫助記錄(i,j)點(diǎn)對(duì)間最短路徑的走向3 時(shí)間復(fù)雜性：O(n 設(shè)G=(V,E)是一個(gè)無(wú)向連通賦權(quán)圖，E設(shè)G=(V,E)是一個(gè)無(wú)向連通賦權(quán)圖，E中每條邊棵包含G的所有頂點(diǎn)的樹，則稱G’為G的支撐在G最小生成樹并§最小生成樹的表示和存儲(chǔ)§最小生成樹的表示和存儲(chǔ)實(shí)?–最小生成樹是由邊???所構(gòu)成的如何合理而有效地表示和存儲(chǔ)，?樹？方法 ???表示和存儲(chǔ)最小生?借助邊結(jié)點(diǎn)結(jié)構(gòu)Edge實(shí)現(xiàn)邊的表示typedefstructedge{intu;intv;WItemw;}//邊的構(gòu)造函數(shù)EdgeEDGE（intu,intv,WItem{Edgee.u=u;e.v=v;e.w=w;returne;}借助于邊結(jié)點(diǎn)的數(shù)組存放最小生成樹邊的集合TEdget[maxE]–構(gòu)造常見(jiàn)的最小生成樹構(gòu)造算Prim算Kruskal算最小生成樹性質(zhì)（MST性質(zhì)反證法證PRIMPRIMPRIMS存放GT存放GPRIMS存放GT存放G初始條初始條方所有的頂點(diǎn)集合被分為兩個(gè)集合S（已被選入生成樹的頂點(diǎn)）和V-S（未被選入生成樹的頂MT性質(zhì)，從所有i∈∈-的邊中，選取具有最小權(quán)值的邊i，加入中，將邊（i）加入集合T中，如此不＝T中恰好包含了最小支撐樹的所有邊起點(diǎn)為頂點(diǎn)起點(diǎn)為頂點(diǎn)Prim算法描{whilePrim算法描{whileS=S∈V-S????j∈S????????(i,j)=//??????????????????}}結(jié)T中所有的邊構(gòu)成G的一棵最小支撐樹設(shè)置兩個(gè)數(shù)組closest和對(duì)于每一個(gè)設(shè)置兩個(gè)數(shù)組closest和對(duì)于每一個(gè)j∈V-S，lowcost[j]用來(lái)保存頂點(diǎn)jclosest[j]是依附于該邊的在集合S--12---11-----12---11---Prim算法實(shí)Prim算法實(shí)for(i=1;i<G->n;i++){min=G->NoEdge;j=1;for(k=2;k<=G->n;if{j=k;}//找到符合條件的t[kk].weight=t[kk].u=t[kk++].v=closest[j];//邊加入到最小生成樹存放的數(shù)組t中for(k=2;k<=n;if((G- }//修正V-S集合中頂點(diǎn)對(duì)應(yīng)的lowcost和closest數(shù)組單}時(shí)間復(fù)雜性：KRUSKALKRUSKALKRUSKALKRUSKAL當(dāng)查看到第k當(dāng)查看到第k條邊(v,w)時(shí)，如果端點(diǎn)v和w分別是當(dāng)前兩個(gè)不同的連通分支T1和T2中的頂連通分支組成一個(gè)集合，借助并查集的基本運(yùn)算連通分支組成一個(gè)集合，借助并查集的基本運(yùn)算順序查看操作即為pop實(shí)inte,i,k,s,t;Edge實(shí)inte,i,k,s,t;Edgea[maxE];UFsetU;for(i=0,k=0;i<e&&k<G->n-i++){s=UFfind(a[i].u,U);//查找頂點(diǎn)u包含在哪個(gè)連通分支中t=UFfind(a[i].v,u);//查找頂點(diǎn)v包含在哪個(gè)連通分支中if(s!=t){//u和v分屬于兩個(gè)不同的連通分支}}預(yù)處理（P.167-168）邊結(jié)構(gòu)edge的定義加權(quán)邊數(shù)組的抽Kruskal算法時(shí)Kruskal算法時(shí)間復(fù)雜性——當(dāng)e=Ω(n2)時(shí)，Kruskal算法比Prim算當(dāng)e=O(n2)時(shí)，Kruskal算法比Prim法好（稀疏型圖二分設(shè)G=(V,E)是一二分設(shè)G=(V,E)是一個(gè)無(wú)向圖，如果頂點(diǎn)集合可以分割為兩個(gè)互不相交的子集，并且圖中每條邊(i,j)所關(guān)匹最大匹配——G的邊數(shù)最多的匹完全匹配一定是一個(gè)最大匹所得到的邊集合記為M⊕所得到的邊集合記為M⊕P，則M⊕P是一個(gè)解決樹的構(gòu)適用范圍：圖G為二方取G的一個(gè)方取G的一個(gè)未匹配頂點(diǎn)作為樹根結(jié)點(diǎn)，位于樹的第層點(diǎn)而且不屬于M的邊，連同這條邊關(guān)聯(lián)的另外點(diǎn)而且屬于M的邊，連同這條邊關(guān)聯(lián)的另外一偏序關(guān)滿足以偏序關(guān)滿足以下兩個(gè)條件的二元關(guān)系反自反性：對(duì)于所有的a∈S,aRa不成應(yīng)用實(shí)例——學(xué)生選課問(wèn)課程與課程之間存在著偏序關(guān)例課程代課程名先修程序設(shè)計(jì)基無(wú)離散數(shù)數(shù)據(jù)結(jié)匯編語(yǔ)語(yǔ)言的設(shè)計(jì)和分例課程代課程名先修程序設(shè)計(jì)基無(wú)離散數(shù)數(shù)據(jù)結(jié)匯編語(yǔ)語(yǔ)言的設(shè)計(jì)和分計(jì)算機(jī)原編譯原操作系高等數(shù)無(wú)線性代普通物數(shù)值分思思課程之間存在偏序關(guān)系，所有課程形成的偏合可以用一個(gè)DAG加以表示(將偏序集合圖的頂點(diǎn)，元素間的偏序關(guān)系作為頂點(diǎn)間的有邊，即可用DAG表示該偏序集)，要順序?qū)W習(xí)這對(duì)于一個(gè)DAG中所有的頂點(diǎn)確定ord:V->{0,1,2,…,n-????????(u,v)∈E??—??????或或反拓?fù)渑欧赐負(fù)渑臘AG的鄰接表實(shí)現(xiàn)下反拓DAG的鄰接表實(shí)現(xiàn)下反拓?fù)渑判蛩鉽oidRevTopSort(GraphD,int{intv;for(v=0;v<=D->n;v++)for(v=1;v<=D->n;v++)if(pre[v])TSdfs(D,v,}voidTSdfs(GraphD,intv,int{glinkt;for(t=D->adj[v];t;t=t-if(pre[t->v])TSdfs(Dt->vts);//深度優(yōu)先遍歷遞歸實(shí)現(xiàn)}時(shí)間復(fù)雜DAG的鄰接矩陣實(shí)現(xiàn)下反拓DAG的鄰接矩陣實(shí)現(xiàn)下反拓?fù)渑判蛩鉽oidRevTopSort(GraphD,int{intv;for(v=0;v<=D->n;v++)for(v=1;v<=D->n;v++)if(pre[v])TSdfs(D,v,}voidTSdfs(GraphD,intv,int{intw;for(w=0;w<d->n;if(D->a[w][v]&&pre[w])TSdfs(Dt->v,ts);//數(shù)組ts給出所有頂點(diǎn)的反拓?fù)湫騷時(shí)間復(fù)雜當(dāng)DG頂點(diǎn)數(shù)n1時(shí)，顯然有拓?fù)渑判蚣僭O(shè)對(duì)于所有頂點(diǎn)數(shù)小于nDG拓?fù)渑判騽h除一個(gè)入度為0的頂點(diǎn)v，以及所有該頂點(diǎn)為起點(diǎn)的邊，得到一個(gè)包含n-1根據(jù)歸納假設(shè)，G'可以進(jìn)行拓?fù)渑判騰的入度為0，因此將v至于G'拓?fù)湫蛄械淖钋懊?，即可合成圖G的拓?fù)湫蛄?DA拓?fù)湫蛄型負(fù)湫蛄型負(fù)湫蛄型負(fù)湫蛄型負(fù)湫蛄校篊1--拓?fù)湫蛄型負(fù)湫蛄校篊1--拓?fù)湫蛄型負(fù)湫蛄校篊1--拓?fù)湫蛄型負(fù)湫蛄校篊1--拓?fù)湫蛄型負(fù)湫蛄校篊1--C2--拓?fù)湫蛄校篊1--C2--拓?fù)湫蛄校篊1--C2--拓?fù)湫蛄校篊1--C2--拓?fù)湫蛄校篊1--C2--C3--拓?fù)湫蛄校篊1--C2--拓?fù)湫蛄校篊1--C2--C3--拓?fù)湫蛄校篊1--C2--拓?fù)湫蛄校篊1--C2--C3--拓?fù)湫蛄校篊1--C2--拓?fù)湫蛄校篊1--C2--C3--拓?fù)湫蛄校篊1--C2--拓?fù)湫蛄校篊1--C2--C3--C4--拓?fù)湫蛄校篊1--C2--C3--C4--拓?fù)湫蛄校篊1--C2--C3--C4--C5--拓?fù)湫蛄校篊1--C2--C3--C4--拓?fù)湫蛄校篊1--C2--C3--C4--C5--拓?fù)湫蛄校篊1--C2--C3--C4--拓?fù)湫蛄校篊1--C2--C3--C4--C5--拓?fù)湫蛄校篊1--C2--C3--C4--拓?fù)湫蛄校篊1--C2--C3--C4--C5--拓?fù)湫蛄校篊1--C2--C3--C4--拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7---10拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7---10拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7---10拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7---10拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7----C10--拓?fù)湫蛄校篊1--C2--C3--C4--