數(shù)據(jù)結構與算法設計（第二版）課件 第7章 圖

第七章圖西安科技大學計算機學院張小艷數(shù)據(jù)結構與算法設計

七橋問題7.1圖--基本概念圖論。歐拉把每一塊陸地看成一個點，連接兩塊陸地的橋用聯(lián)線表示。把它轉化成一個幾何問題。七橋問題就轉化成了是否能用一筆不重復地畫出過此七條線的圖形？142351234圖--基本概念頂點邊弧

圖是一種網(wǎng)狀數(shù)據(jù)結構，是由一個頂點的有窮非空集V(G)和一個弧或邊的集合E(G)組成。通常記作二元組G

=

(V，E)其中G表示一個圖，V是圖G中頂點的集合，E是圖G中的弧的集合。線性表可以沒有元素，稱之為空表；樹中可以沒有結點，稱之為空樹；圖中不能沒有頂點。圖--圖的定義圖分為無向圖和有向圖。(a)無向圖對于無向圖G

=

(V，E)，如果(vi，vj)是一條邊，則稱頂點vi，vj互為鄰接點。邊(vi，vj)依附于頂點(vi，vj)。注意：(vi，vj)和(vj，vi)是一條邊。無向邊用于表示“對稱關系”，城市中的雙行道可以用無向邊表示。

圖(a)圖可以表示為二元組

(V1，E)

V1={1,2,3,4,5}

E=

{（1,2）,(1,4),(2,3),(2,5),(3,5),(3,4)}圖—圖的分類14235(b)有向圖

對于有向圖G

=

(V，E)，如果

<vi，vj>

是一條弧，

vi稱為弧尾或起始點，vj稱為弧頭(head)或終端點。

弧<vi，vj>

和

弧<vj，vi>

是兩條不同的弧。有向邊用于表示“非對稱關系”。城市中的單行道用有向邊表示。圖(b)可以表示為G2

=(V2，A)

V2={1,2,3,4}

A={<1,2>,<1,3>,<3,4>,<4,1>,<4,2>}表示邊的序偶用圓括號，表示弧的序偶用尖括號。圖—圖的分類1234

在一個無向圖中，如果任意兩個頂點都有一條直接邊相鄰接，則稱該圖為無向完全圖。可以證明，在一個含有n個頂點的無向完全圖中，有n(n-1)/2條邊。

在一個有向圖中，如果任意兩個頂點之間都有方向互為相反的兩條弧相鄰接，則稱該圖為有向完全圖。在一個含有n個頂點的有向完全圖中，有n(n-1)條邊。

若一個圖接近完全圖，稱為稠密圖；反之稱為稀疏圖。(a)無向完全圖(b)有向完全圖圖—完全圖加權邊或加權弧。帶權的圖稱為網(wǎng)或網(wǎng)絡(network)。(a)無向網(wǎng)(b)有向網(wǎng)圖—權值和網(wǎng)圖--頂點的度頂點的度(degree)是指依附于某頂點v的邊數(shù)，通常記為TD(v)。在有向圖中，要區(qū)別頂點的入度與出度的概念。頂點v的入度是指以頂點v為終點的弧的數(shù)目，記為ID(v)；

頂點v的出度是指以頂點v為始點的弧的數(shù)目，記為OD(v)。TD(v)?=?ID(v)?+?OD(v)。頂點1的度是2，頂點2的度為3，頂點3的度為3，頂點4的度是2，頂點5的度為2，所有頂點的度加起來等12，圖中有6條邊。15432（a）無向圖G1對于具有n個頂點、e條邊的無向圖：

頂點1的入度為?1，出度為?2；頂點2的入度為2，出度為0；頂點3的入度為1，出度為1；頂點4的入度為1，出度為2；所有頂點的入度之和與出度之和相等，就是邊數(shù)。1432（b）有向圖G2圖--頂點的度圖--路徑和回路無向圖G?=?(V，E)中：從頂點v到頂點v'?之間的路徑(path)是一個頂點序列(v?=?vi1，vi2，…，vim?=?v')，其中，(vij，vij+1)是E中的一條邊，1≤j＜m。路徑上邊或弧的數(shù)目稱為路徑長度。序列中頂點不重復出現(xiàn)的路徑稱為簡單路徑。V1V6V5V4V3V2132161189235712（a）無向網(wǎng)v1→v2→v3→v4v1→v6→v4路徑長度分別為3和2，這兩條路徑都是簡單路徑。v1→v2→v6→v5→v4是從頂點v1到頂點v4的一條路徑，路徑長度為4。v5→v1是從頂點v5到頂點v1的一條路徑，路徑長度為1。這兩條路徑都是簡單路徑。V3V1V6V5V4V289613215712（b）有向網(wǎng)圖--路徑和回路無向網(wǎng)(a)中，v1→v2→v6→v5→v1是一條簡單回路。有向網(wǎng)(b)中，v1→v2→v6→v5→v1也是一條簡單回路。無向網(wǎng)(a)中的v1→v2→v6→v4→v2→v1路徑中v2是重復的，就不是簡單環(huán)了。V1V6V5V4V3V2132161189235712V3V1V6V5V4V289613215712（a）無向網(wǎng)（b）有向網(wǎng)路徑中第一個頂點和最后一個頂點相同時稱該路徑為回路或者環(huán)(cycle)。除第一個頂點與最后一個頂點之外，其他頂點不重復出現(xiàn)的回路稱為簡單回路，或者簡單環(huán)。圖--路徑和回路圖--子圖對于圖G?=?(V，E)，存在G'?=?(V'，E')，若存在V'?是V的子集，E'?是E的子集，則稱圖G'?是G的一個子圖。153214154321542無向圖G1G1的子圖圖--無向圖的連通性在無向圖中，如果從頂點vi到頂點vj(i?≠?j)有路徑，則稱頂點vi和vj是連通的。如果圖中任意兩個頂點都是連通的，則稱該圖是連通圖。15432無向圖G1來看這里的無向圖連通嗎？MLADKJIHGFECB(a)無向圖G3顯然是不連通的，但是他包含三個部分，這三部分各自是聯(lián)通的。這三部分可以稱之為原圖的連通分量。MLAJFCBDEKIHG(b)無向圖G3的三個連通分量圖--無向圖的連通性無向圖的連通分量要滿足三個條件：

第一：是子圖；

第二：要聯(lián)通；

第三：含有極大頂點數(shù)及依附于這些頂點的所有的邊。所以無向圖的連通分量也稱之為無向圖的極大連通子圖圖--無向圖的連通性圖--有向圖的連通性在有向圖中，若圖中任意一對頂點vi,vj，從vi到vj有路徑，從vj到vi也有路徑，則稱該有向圖是強連通圖。有向圖的極大強連通子圖稱為強連通分量。圖(a)的有向圖有兩個強連通分量，分別是{v1,v3,v4}和{v2}。14322143(a)有向圖(b)連通分量圖--生成樹和生成森林一個連通圖的生成樹是一個極小的連通子圖，它包含圖中全部的頂點n，但只有足以讓n個頂點連通的n-1條邊，就是讓N個頂點連通而無回路。MLAJFCBMLAJFCB所以，一個連通圖的生成樹不止一棵。圖a不連通，有三個連通分量，就有三棵生成樹。MLADKJIHGFECBMLAJFCBDEKIHG(a)無向圖G3(c)無向圖G3的三個生成樹在非連通圖中，由每個連通分量都可得到一個極小連通子圖，即一棵生成樹。這些連通分量的生成樹就組成了一個非連通圖的生成森林。圖--生成樹和生成森林如果一個有向圖恰有一個頂點的入度為0，其余頂點的入度均為1，則是一棵有向樹。圖中v0的入度為0，v1,v2,v3,v4,v5的入度均為1，所以是一棵有向樹。V3V0V1V5V4V2入度為0的頂點其實就相當于樹的根結點，其余頂點入度為1就是說樹的非根結點的雙親只有一個。一個有向圖的生成森林由若干棵有向樹組成，含有圖中全部頂點，但只有足以構成若干棵互不相交的有向樹的弧。圖--生成樹和生成森林圖--基本操作在圖中任何一個頂點都可以被看成是第一個頂點；任意一個頂點的鄰接點之間也不存在次序關系，所以無法將圖中的頂點排列成一個唯一的線性序列。為了操作方便，需要將圖中頂點按任意的順序排列起來(這個序列是人為規(guī)定的)。所以需明確一個“頂點在圖中位置”的概念。15432所謂頂點在圖中位置，指的是該頂點在人為規(guī)定的排列中的位置(或序號)。同理，可對某個頂點的所有鄰接點進行排序，在這個序列中，自然形成了第一個鄰接點和第k個鄰接點。若某個頂點的鄰接點的個數(shù)大于k，則稱第k+1個鄰接點是第k個鄰接點的下一個鄰接點，最后一個鄰接點的下一個鄰接點為“空”。圖--基本操作假設頂點的序號就是存儲位置，按照序號從小到大排列某個頂點的鄰接點。頂點1有兩個鄰接點，4是頂點1相對于2的下一個鄰接點；頂點1相對于4的下一個鄰接點為空。15432無向圖G1可以稱2是1的第一個鄰接點；圖--基本操作的基本操作：(1)頂點定位操作LocateVex(G，v)：在圖G中找到頂點v，返回該頂點在圖中的位置。(2)取頂點操作GetVextex(G，v)：在圖G中找到頂點v，并返回頂點v的相關信息。(3)求第一個鄰接點操作FirstAdjVex(G，v)：在圖G中，返回v的第一個鄰接點。若頂點v在G中沒有鄰接頂點，則返回“空”。15432無向圖G1圖--基本操作的基本操作：(1)頂點定位操作LocateVex(G，v)：在圖G中找到頂點v，返回該頂點在圖中的位置。(2)取頂點操作GetVextex(G，v)：在圖G中找到頂點v，并返回頂點v的相關信息。(3)求第一個鄰接點操作FirstAdjVex(G，v)：在圖G中，返回v的第一個鄰接點。若頂點v在G中沒有鄰接頂點，則返回“空”。(4)求下一個鄰接點操作NextAdjVex(G，v，w)：在圖G中，返回v的(相對于w的)下一個鄰接頂點。若w是v的最后一個鄰接點，則返回“空”。15432無向圖G1圖--基本操作(5)插入頂點操作InsertVex(G，v)：在圖G中增添新頂點v。(6)刪除頂點操作DeleteVex(G，v)：在圖G中，刪除頂點v以及所有和頂點v相關聯(lián)的邊或弧。(7)插入弧操作InsertArc(G，v，w)：在圖G中增添一條從頂點v到頂點w的邊或弧。(8)刪除弧操作DeleteArc(G，v，w)：在圖G中刪除一條從頂點v到頂點w的邊或弧。(9)深度優(yōu)先遍歷圖DFSTraverse(G，v)：在圖G中，從頂點v出發(fā)按深度優(yōu)先對圖中每個結點訪問一遍且僅一遍。(10)廣度優(yōu)先遍歷圖BFSTraverse(G，v)：在圖G中，從頂點v出發(fā)按廣度優(yōu)先對圖中每個結點訪問一遍且僅一遍。圖的這10個基本操作中，5-8操作涉及圖的修改，一般情況下不常用到。7.2圖的存儲結構圖是一種結構復雜的數(shù)據(jù)結構，任意兩個頂點之間都有可能存在聯(lián)系。MLADKJIHGFECB同學們，用順序存儲結構可以圖嗎？

鏈式存儲結構可以嗎？7.2圖的存儲結構

--鄰接矩陣圖是一種結構復雜的數(shù)據(jù)結構，任意兩個頂點之間都有可能存在聯(lián)系。一個圖的信息包括兩部分：即圖中頂點的信息描述頂點之間的關系—邊或者弧的信息。MLADKJIHGFECB圖的信息包括兩部分：頂點的信息、頂點之間的關系(邊或者弧的信息)。分兩部分存儲：

用一維數(shù)組來存儲頂點信息;

頂點與頂點之間的關系用二維數(shù)組存儲--鄰接矩陣。V0V2V3V4V1圖的存儲結構

--鄰接矩陣假設圖G?=?(V，E)，有n個頂點，即V?=?{v0，v1，…，vn-1}，則表示G中各頂點相鄰關系為一個n?×?n的矩陣，將矩陣arcs稱為鄰接矩陣。圖的存儲結構

--鄰接矩陣V0V2V3V4V1(c)鄰接矩陣存儲結構(b)頂點數(shù)組(a)無向圖圖的存儲結構

--鄰接矩陣在無向圖中判斷頂點vi到vj是否有邊，只要判斷arcs[i][j]?是否等于1；頂點vi的度就是第i行的元素之和；如果要找頂點vi的所有鄰接點，查找第i行值為1的矩陣元，其所在列的序號即為其鄰接點的序號。圖的存儲結構

--鄰接矩陣判斷頂點vi到vj是否有弧，只要判斷arcs[i][j]?是否等于1。每個頂點的度分出度和入度，如果要找頂點vi的所有鄰接點，查找第i行值為1的矩陣元，其所在列的序號即為其鄰接點的序號。V0V2V3V1(c)鄰接矩陣存儲結構(b)頂點數(shù)組(a)無向圖圖的存儲結構

--鄰接矩陣若G是網(wǎng)，則鄰接矩陣可定義為：若(vi，vj)或<vi，vj>是G的邊或弧若i?=?j反之圖的存儲結構

--鄰接矩陣圖或網(wǎng)的鄰接矩陣存儲結構的C語言描述形式如下：1#defineINFINITY<整數(shù)中允許的最大值>2#defineMAXNODE<圖中頂點的最大個數(shù)>3typedefcharVertexType;4typedefstruct5{intadj;

6……7}ArcType;/*定義表示無窮大整數(shù)*//*定義圖中頂點的最大個數(shù)*//*假設頂點數(shù)據(jù)為字符型*//*圖：兩頂點相鄰則adj=1，否則adj=0；網(wǎng)：兩頂點相鄰則adj=wij，i=j則adj=0；否則adj=∞*//*其他信息*/8typedefstruct9{VertexTypevertexes[MAXNODE];10ArcTypearcs[MAXNODE][MAXNODE];11intvexnum,arcnum;12}GraphType;/*頂點數(shù)組*//*鄰接矩陣*//*圖的頂點數(shù)和弧數(shù)*/圖的存儲結構

--鄰接矩陣intadj[MAXNODE][MAXNODE]。在實際應用中，如果人們所關心的只是兩頂點之間是否有邊(或者弧)相連，而不考慮頂點本身的信息，在這種情況下，可以用編號作為圖中各個頂點信息，圖或網(wǎng)的鄰接矩陣存儲結構可以簡單地表示為：圖的存儲結構

--鄰接矩陣圖的鄰接矩陣存儲具有4個特點：①用鄰接矩陣存儲圖簡單明了，極易在圖中查找、插入、刪除一條邊或頂點，但要占用O(n2)個存儲空間(n是頂點數(shù))，無論圖中實際含有多少條邊。因此，對于稀疏圖而言，不適于用鄰接矩陣來存儲，因為這樣會造成存儲空間的浪費。②無向圖的鄰接矩陣一定是一個對稱矩陣。因此，在具體存放鄰接矩陣時只需存放上(或下)三角矩陣的元素即可。③對于無向圖或網(wǎng)，鄰接矩陣的第i行(或第i列)非零元素(或非∞元素)的個數(shù)正好是第i個頂點的度TD(vi)。④對于有向圖或網(wǎng)，鄰接矩陣的第i行(或第i列)非零元素(或非∞元素)的個數(shù)正好是第i個頂點的出度OD(vi)(或入度ID(vi))。圖的存儲結構

--鄰接矩陣1intCreateDN(GraphType*G) /*創(chuàng)建一個有向網(wǎng)*/2{3inti,j,k,weight;4VertexTypev1,v2;5scanf(″%d,%d″,&G->vexnum,&G->arcnum);/*輸入圖的頂點數(shù)和弧數(shù)*/6for(i=0;i<G->vexnum;i++)7for(j=0;j<G->vexnum;j++)8G->arcs[i][j].adj=INFINITY;/*初始化鄰接矩陣*/9for(i=0;i<G->vexnum;i++)10scanf(″%c″,&G->vertexes[i]); /*輸入圖的頂點*/11for(k=0;k<G->arcnum;k++)12{13scanf(″%c,%c,%d″,&v1,&v2,&weight);/*輸入弧的兩個頂點及權值*/14i=LocateVex(G,v1);/*定位函數(shù)，時間復雜度為O(n)，*/15j=LocateVex(G,v2);/*定位函數(shù)，時間復雜度為O(n)，*/16G->arcs[i][j].adj=weight; /*弧上賦權值*/17}18return(OK);19}基本操作執(zhí)行n2次循環(huán)次數(shù)為e次時間復雜度為：O(e?×?n)所以，此算法的時間復雜度為：O(n2?+?e?×?n)。圖的存儲結構

--鄰接矩陣v0v1v2v3v401234頂點數(shù)組：（a）無向圖邊矩陣：（c）鄰接矩陣存儲結構（b）頂點數(shù)組0123401234V0V1V2V3V4圖的存儲結構

--鄰接表V50501005010000012345678∧∧∧12345689序號datafirstchild對圖中的每一個結點的鄰接點用一個單鏈表存儲，所有頂點用一個數(shù)組存放。把這種順序存儲與鏈式存儲相結合的存儲方法稱為鄰接表。ABCDEFGHIBCDEFGHIA∧∧∧∧∧∧圖的存儲結構

--鄰接表012345678∧∧∧12345689序號datafirstchild圖的鄰接表存儲結構是順序存儲結構和鏈式存儲結構完美結合。順序存儲結構和鏈式存儲結構各有優(yōu)缺點，在這里充分發(fā)揮了各自的優(yōu)勢，所以大家要博學多識，積累知識，掌握各種理論與方法，在具體應用中才能夠將所學知識融會貫通。要善于運用事物或人本身所具有的長處。ABCDEFGHIBCDEFGHIA∧∧∧∧∧∧圖的存儲結構

--鄰接表adjvexnext①圖中的頂點用一個一維數(shù)組存儲，每個數(shù)組元素包含兩部分：

一部分用于存儲頂點信息data，一部分用于存放指向該頂點的第一個鄰接點的指針firstarc。②圖中每個頂點vi的所有鄰接點構成一個單鏈表。

若是無向圖，該鏈表稱為頂點vi的邊表；

若是有向圖，該鏈表稱為頂點vi作為弧尾的出邊表。firstarc如果邊上有其他信息需要保存，可以增加域，比如是網(wǎng)，可以增加權值weght。adjvexweightnextdata圖的存儲結構

--鄰接表01234^^^1302413datafirstarc02^^413adjvexnextv0v1v2v3v4對于有n個頂點、e條邊的無向圖而言，若采用鄰接表作為存儲結構，則需要n個表頭結點和2e個表結點。v0v1v2v3v4圖的存儲結構

--鄰接表在無向圖的鄰接表存儲結構中，若要獲得某結點的度，只需要查找這個頂點的邊表結點的個數(shù)即可。若要判斷頂點vi和vj是否存在邊，需要在vi(或vj)的鄰接點單鏈表中查找鄰接點域adjvex是否存在結點vj(或vi)的下標j(或i)。若求頂點的所有鄰接點，就是對此頂點的鄰接點單鏈表進行遍歷，得到的鄰接點域adjvex域對應的頂點。圖的存儲結構

--鄰接表有向圖0123^123datafirstarc01adjvexnext^^^v0v1v2v3有向圖采用鄰接表存儲結構類似無向圖，但是要注意有向圖中的弧是有方向的，以頂點為弧尾來存儲弧。有向圖鄰接表v3v0v1v2圖的存儲結構

--鄰接表有向圖逆鄰接表逆鄰接表中，圖中第i個頂點的入度等于第i條鏈表中邊結點的個數(shù)。0123300datafirstarc2adjvexnext^^v0v1v2v33^^v3v0v1v2圖的存儲結構

--鄰接表對于網(wǎng)，在邊表結點上增加一個權值weight域，用于存放與邊或弧相關的信息。當然如果邊上有其他的信息需要保存，也可以增加域。adjvexweightnextv0v1v2v3v401234datafirstarcv0v1v2v3v4adjvexweightnext^^^^^1233022645116384032847152137通過無向網(wǎng)鄰接表存儲實例，我們可以看到邊結點增加的存儲權值域。圖的存儲結構

--鄰接表#defineMAXNODE＜圖中頂點的最大個數(shù)＞typedefstructarc {

intadjvex; intweight; structarc*next;}ArcType;typedefstruct{ElemTypedata; ArcType*firstarc; }VertexType; typedefstruct{VertexTypevertexes[MAXNODE];intvexnum,arcnum; }AdjList;/*邊表結點*//*鄰接點域，存儲鄰接點在表頭結點表中的位置*//*權值域，用于存儲邊或弧相關的信息，非網(wǎng)圖可以不需要*//*鏈域，指向下一鄰接點*//*頂點信息*//*指向第一條依附該頂點的邊或弧的指針*//*頂點表結點*//*圖中頂點數(shù)和弧數(shù)*/圖的存儲結構

--鄰接表

1#defineMAXNODE302intCreateUDN(AdjList*G)3{4inti,j,k;5intv1,v2;6intn,e;7ArcType*p,*q;8printf(″\n輸入圖中頂點的個數(shù)n和邊數(shù)e：\n″);9scanf(″%d,%d″,&n,&e,);10G->vexnum=n;11G->arcnum=e;12printf(″\n輸入頂點的信息：\n″);13for(k=0;k<n;k++)14{15scanf(″%d″,&(G->vertexes[k].data));16G->vertexes[k].firstarc=NULL;17}

/*創(chuàng)建一個無向圖G*//*輸入圖中的頂點數(shù)和邊數(shù)*/

/*輸入n個頂點信息*/循環(huán)次數(shù)為n圖的存儲結構

--鄰接表18printf(″\n輸入圖中各邊:\n″)19for(k=0;k<e;k++)20{21scanf(″%d,%d″,&v1,&v2);22i=LocateVex(*G,v1);23j=LocateVex(*G,v2);24q=(ArcType*)malloc(sizeof(ArcType));25q->adjvex=j;26q->next=G->vertexes[i].firstarc;27G->vertexes[i].firstarc=q;28p=(ArcType*)malloc(sizeof(ArcType));29p->adjvex=i;30p->next=G->vertexes[j].firstarc;31G->vertexes[j].firstarc=p;32}33return(1);34}

/*依次讀入e條邊信息，建立邊表*//*讀入邊（v1，v2）*//*查找v1的位置i*//*查找v2的位置i*//*申請結點q指向*//*鄰接點賦值為j*//*在頂點數(shù)組的第i個頂點的邊表中插入邊結點*//*申請結點p指向*//*鄰接點賦值為i*//*在頂點數(shù)組的第j個頂點的邊表中插入邊結點*/該算法時間復雜度為O(e?×?n)采用頭插法建立單鏈表鄰接矩陣和鄰接表是兩種最常用的圖的存儲結構，前者適合于圖的靜態(tài)存儲，后者適合于圖的動態(tài)存儲。循環(huán)次數(shù)為e時間復雜度O(n)時間復雜度O(n)圖的存儲結構

--鄰接表7-3圖的深度優(yōu)先遍歷圖的遍歷，是指從圖中的任一頂點出發(fā)，對圖中的所有頂點訪問一次且只訪問一次，圖的遍歷有兩種：圖的深度優(yōu)先遍歷、廣度優(yōu)先遍歷。圖的遍歷進行圖的遍歷時，需要為圖設置一個訪問標識數(shù)組:visited[n]，用于表示圖中每個頂點是否被訪問過。visited[1~n]=0(“假”)，表示頂點均未被訪問；visited[i]=1(“真”)，表示頂點已被訪問。V0V2V3V4V12376815設置訪問標識數(shù)組記錄結點是否被訪問過。這種處理方式是為了讓我們記住來時路?！坝浀脕頃r路，繼續(xù)向遠方”不忘初心砥礪前行。深度優(yōu)先遍歷(depthfirstsearch)類似于樹的先根遍歷，是樹先根遍歷的推廣。生成的樹稱為深度優(yōu)先生成樹。圖的遍歷

--深度優(yōu)先遍歷ABCGDHEFABDHECFG深度優(yōu)先遍歷的序列為：深度優(yōu)先遍歷圖的算法：(1)訪問結點v；(2)找到v的第一個鄰接點w；(3)如果鄰接點w存在且未被訪問，則從w出發(fā)深度優(yōu)先遍歷圖；否則，結束；(4)找頂點v關于w的下一個鄰接點，轉(3)。圖的遍歷

--深度優(yōu)先遍歷9voidDepthFirstSearch(GraphG,intv)10{intw;11visit(v); 12visited[v]=1; 13w=FirstAdjVertex(G,v); 14while(w!=-1) 15{16if(!visited[w])17DepthFirstSearch(G,w); 18w=NextAdjVertex(G,v,w); 19}20}/*深度遍歷v所在的連通子圖*//*訪問頂點v*//*置訪問標識數(shù)組相應分量值*//*找第一個鄰接點*//*鄰接點存在*//*遞歸調(diào)用DepthFirstSearch*//*找下一個鄰接點*/圖的遍歷

--深度優(yōu)先遍歷深度優(yōu)先遍歷的序列在存儲結構給定的情況下是唯一的，因為存儲結構給定之后，頂點的存儲位置及鄰接點的排列順序也給定了。對于非連通圖，只要對圖中所有的連通分量進行深度優(yōu)先遍歷。從一個頂點開始深度優(yōu)先遍歷結束之后，如果圖中還有未被訪問的頂點，就另選一個沒有訪問過的頂點作為起點，重復上述過程，直到圖中所有頂點都被訪問過。所以圖的遍歷算法在從某一個頂點出發(fā)深度訪問之前需要做一些預處理：1、訪問標志數(shù)組初始化；2、找沒有遍歷的頂點。圖的遍歷

--深度優(yōu)先遍歷intvisited[MAXNUM];1voidTraveGraph(CraphG)2{

3intv;4for(v=0;v<G.vexnum;v++) 5visited[v]=0;6for(v=0;v<G.vexnum;v++)7if(!visited[v])DepthFirstSearch(G,v); 8}/*初始化訪問標識數(shù)組*//*找沒有被訪問過的頂點，找到后進入深度優(yōu)先*//*調(diào)用深度遍歷算法*//*對圖G進行深度優(yōu)先搜索，Craph是圖的一種存儲結構，如鄰接矩陣表示法或鄰接表*//*訪問標識數(shù)組*/圖的遍歷

--深度優(yōu)先遍歷一個連通圖的生成樹不唯一。（1）（2）（3）連通圖圖的遍歷

--深度優(yōu)先遍歷對于非連通圖，每個連通分量中的頂點集和深度優(yōu)先遍歷時走過的邊一起構成若干棵深度優(yōu)先遍歷生成樹，這些連通分量的生成樹組成非連通圖的深度優(yōu)先遍歷生成森林。第一次從頂點1出發(fā)，深度優(yōu)先遍歷的序列為:1-2-4-3-9；第二次從5出發(fā)，深度優(yōu)先遍歷的序列為:5-6-7；第三次從8出發(fā)，深度優(yōu)先遍歷的序列為:8-10。（1）（2）（3）圖的遍歷

--深度優(yōu)先遍歷7-3-2圖的廣度優(yōu)先遍歷圖的遍歷--廣度優(yōu)先遍歷ACBEFGDHI

廣度優(yōu)先遍歷實質(zhì)上是從指定頂點出發(fā)，按照到該頂點的路徑長度由短到長的順序訪問圖中的所有頂點。遍歷時需要設立訪問標識數(shù)組visited[n]：

visited[i]=0，節(jié)點未被訪問；

visited[i]=1，節(jié)點已被訪問。在廣度優(yōu)先遍歷中需要設置一個隊列Queue來記錄訪問次序。廣度優(yōu)先遍歷是對圖進行遍歷的另一種常用方法，它類似于樹的層次遍歷，是樹的按層次遍歷的推廣，在遍歷過程中需要用隊列記錄遍歷過程中的頂點。圖的遍歷--廣度優(yōu)先遍歷ACBEFGDHI出隊列入隊列ABCEFGHDIAABCDEFGHBCDEFGHII廣度優(yōu)先遍歷過程：在對連通圖進行廣度優(yōu)先遍歷過程中，連通圖的所有的頂點及廣度優(yōu)先遍歷走過的邊構成了一棵生成樹，稱為廣度優(yōu)先生成樹。對于非連通圖，每個連通分量中的頂點集和廣度優(yōu)先遍歷時走過的邊一起構成若干棵廣度優(yōu)先遍歷生成樹，這些連通分量的生成樹組成非連通圖的廣度優(yōu)先遍歷生成森林。圖的遍歷--廣度優(yōu)先遍歷ABCDEFGHIABCDEFGHI非連通圖（1）（2）廣度優(yōu)先遍歷算法描述如下：(1)設圖G的初態(tài)是所有頂點均未訪問，設置輔助隊列Q，隊列Q置空；(2)任選圖中一個未被訪問過的頂點v作為遍歷起點；(3)訪問v(將其訪問標識置為已被訪問，即visited[v]?=?1)，并且將v入隊列；(4)若隊列Q不空，從隊頭取出一個頂點v；(5)查找v的所有未訪問的鄰接點vi并對其訪問(將其訪問標識置為已被訪問，即visited[i]?=?1)，并入隊列，轉(4)，直到隊列Q為空；(6)若此時圖中還有未被訪問過的頂點，則轉(2)；否則，遍歷結束。圖的遍歷--廣度優(yōu)先遍歷1intvisited[MAXNUM];

2voidBFSTraveGraph(GraphTypeG)3{4intv;5QQTypeQ;

6InitQueue(&Q);

7for(v=0;v<G.vexnum;v++)

8visited[v]=0;9for(v=0;v<G.vexnum;v++)10if(!visited[v])BreadthFirstSearch(G,v);

11}圖的遍歷--廣度優(yōu)先遍歷/*訪問標識數(shù)組*//*QQType為隊列類型標識符*//*初始化隊列*//*初始化訪問標識數(shù)組*//*找沒有被訪問過的頂點，進行廣度優(yōu)先調(diào)用深度遍歷算法*/12voidBreadthFirstSearch(GraphTypeg,intv0)13{intv,vj,w;14visit(v0);15visited[v0]=1;16EnterQueue(&Q,v0); 17while(!QueueEmpty(Q))

18{v=DeleteQueue(&Q); 19for(vj=0;vj<n;vj++)20if(!visited[vj]&&g.arcs[v][vj].adj==1)

21{visit(vj);22visited[vj]=1;23EnterQueue(&Q,vj)24}25}26}/*訪問v0*//*訪問標志修改為訪問過*//*v0入隊列*/圖的遍歷--廣度優(yōu)先遍歷/*循環(huán)判斷隊列是否為空*//*隊頭元素出隊*//*找V的所有鄰接點*//*vj入隊列*//*若鄰接點存在且沒有被訪問過*/7-4-1普里姆算法一個帶權網(wǎng)，這個網(wǎng)中v1～v6代表6個村鎮(zhèn)，聯(lián)線上的數(shù)字就是兩個村鎮(zhèn)架設通訊設施的耗費。v1v4v2v3v5v65615366425最小生成樹

所謂最小成本，就是在這6個村鎮(zhèn)之間找到5條邊把6個村鎮(zhèn)連起來，同時達到5條邊上的權值之和最小。你找到的會是下面的一個無回路的聯(lián)通網(wǎng)，這就是最小生成樹.v1v4v2v3v5v615342最小生成樹最小生成樹:

一個無向連通網(wǎng)，它所有的生成樹中必有一棵邊的權值之和最小的生成樹，我們稱這棵樹為最小代價生成樹，簡稱最小生成樹。求最小生成樹的經(jīng)典算法有兩種：普里姆算法和克魯斯卡爾算法。普里姆(Prim)算法構造最小生成樹：

假定有連通網(wǎng)N?=?(V,E)，其中V為網(wǎng)中所有頂點的集合，E為網(wǎng)中所有帶權邊的集合。

①設TE為最小生成樹中邊的集合，初始化TE為?Φ，引入U集合，初始化U?集合只包含V中的一個頂點u0。

②在U集合到V-U集合的所有的邊中選一條代價最小的邊(u0,v0)。將邊(u0,v0)并入集合TE，同時將頂點v0并入U集合。

③重復②，直到U?=?V為止。 此時TE中必含有n-1條邊。 頂點集V、邊集為TE的生成樹T?=?(V,TE)，就是N的最小生成樹。

普里姆(Prim)算法也可稱為“加點法”。最小生成樹

--普里姆(Prim)算法v1v4v2v3v5v6142533425561665v1v2v3v4v5v6v4U={v1}

，V-U集合=?{v2,v3,v4,v5,v6}。U={v1,v3}

，V-U集合=?{v2,v4,v5,v6}。U={v1,v3,v6}

，V-U集合=?{v2,v4,v5}。U={v1,v3,v6,v4}

，V-U集合=?{v2,v5}。U={v1,v3,v6,v4,v2}

，V-U集合=?{v5}。U={v1,v3,v6,v4,v2,v5}

，V-U集合=?{}。U?=?V，找到最小生成樹最小生成樹

--普里姆(Prim)算法普里姆(Prim)算法實現(xiàn)需要設置一個輔助數(shù)組closedge[]，定義為一個結構體：typedefcharVertexType;struct{VertexTypevex;/*U中的頂點*/intlowcost;/*min({cost(vex,v)|vex∈U})*/}closedge[MAXNUM];/*求最小生成樹時的輔助數(shù)組*/closedge[]用來記錄從U集合到V-U集合具有最小代價的邊。對每個V-U集合中的頂點在輔助數(shù)組中存在一個分量closedge[v]，它包括兩個域：U中的頂點域vex和邊(u,v)上的耗費lowcost，（v,u）是當前權值最小的邊。

closedge[v].lowcost

=

min({cost(u,v)|u∈U}）最小生成樹

--普里姆(Prim)算法

以鄰接矩陣作為圖的存儲方式來展示普里姆(Prim)算法的實現(xiàn)。從頂點u出發(fā)，按普里姆算法構造連通網(wǎng)G的最小生成樹，并輸出生成樹的每條邊。1MiniTreePrim(GraphTypeG,VertexTypeu)2{intk,i,j,e,k0,mincost;3charu0,v0;4k=LocateVex(G，u); 5closedge[k].lowcost=0;6for(i=0;i<G.vexnum;i++)7if(i!=k)8{closedge[i].vex=u;9closedge[i].lowcost=G.arcs[k][i].adj;10}11for(e=1;e<=G.vexnum-1;e++)

12{mincost=32767;

13k0=0;/*確定u在圖G中的位置*//*初始化U?=?{u}*//*對V-U中的頂點i，初始化closedge[i]*//*依次找到n-1條邊*/循環(huán)次數(shù)為n/*mincost為一個比任何邊的權都要大的數(shù)*/最小生成樹

--普里姆(Prim)算法14for(j=0;j<G.vexnum;j++) 15if(closedge[j].lowcost!=0&&closedge[j].lowcost<mincost)16{17k0=j; 18mincost=closedge[j].lowcost;19}20u0=closedge[k0].vex;21v0=G.vertexes[k0];22printf(″(%c,%c)\n″,u0,v0);23closedge[k0].lowcost=0; 24for(i=0;i<G.vexnum;i++)25if(G.arcs[k0][i].adj<closedge[i].lowcost)26{closedge[i].lowcost=G.arcs[k0][i].adj;27closedge[i].vex=v0;28}29}30}算法的時間復雜度為O(n2)，與網(wǎng)中的邊數(shù)無關，適合于求邊稠密的網(wǎng)的最小生成樹。/*選擇當前代價最小的邊*/循環(huán)次數(shù)為n/*輸出生成樹的當前最小邊*//*將頂點v0并入U集合*//*在頂點v0并入U后，更新closedge[i]*//*closedge[k0]中存有當前代價最小的邊*/最小生成樹

--普里姆(Prim)算法7-4-2克魯斯卡爾算法克魯斯卡爾算法的基本思想是：(1)初始化最小生成樹的初始狀態(tài)為：

只有n個頂點而無邊的非連通圖T=(V,Φ)；

圖中每個頂點自成一個連通分量。(2)在邊集E中選擇代價最小的邊，如果這個邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中；否則舍去此邊而選擇下一條代價最小的邊。(3)重復(2)，直到T中所有的頂點都在同一連通分量上為止。最小生成樹

--克魯斯卡爾算法克魯斯卡爾算法逐步增加生成樹的邊，與普里姆算法相比，可稱為“加邊法”。

對于圖中的連通網(wǎng)，設N?=?{V,{E}}，最小生成樹T的初態(tài)中邊集為空，TE=NULL，每個頂點自成一個聯(lián)通網(wǎng)。1236541236543151561816361114362011616最小生成樹

--克魯斯卡爾算法克魯斯卡爾算法是不斷地掃描邊集合，至多對e條邊各掃描一次，如果用堆來存放邊，則每次選擇最小邊僅需O(lb?e)的時間代價。可以證明，克魯斯卡爾算法的時間復雜度為O(elb?e)，它適合于求邊稀疏的網(wǎng)的最小生成樹。最小生成樹

--克魯斯卡爾算法在解決問題時不斷刻苦鉆研，獲取最優(yōu)的解決方案，不能滿足于在找到答案。7-5-1迪杰斯特拉算法最短路徑

在實際生活中經(jīng)常遇到這樣的問題，從A城市到B城市有若干條路,需要選擇一條距離最短的路。假如要用計算機解決這一問題，可以采用網(wǎng)描述交通網(wǎng)絡。

在圖中頂點表示城市，邊代表城市之間的通路，邊上的權代表通路的距離。這樣，上述問題就變成了在圖中尋找一條從頂點A到頂點B所經(jīng)過的路徑上權值累加和最小的路徑。我們把這樣一類問題稱為最短路徑問題。v0v1v2v3v4v5v620301051291081518最短路徑有兩種最短路徑問題：①求某一源點到其余各頂點的最短路徑；②求任意兩頂點間的最短路徑。從源點到終點的路徑可能存在三種情況：①沒有路徑；②只有一條路徑，則該路徑即為最短路徑；③存在多條路徑，則其中必存在一條最短路徑。v0v1v2v3v4v5v6

有向網(wǎng)G?=?(V，E),求源點v0到其他各頂點的最短路徑。從源點v0到v5沒有路徑從源點v0到v1只有一條路徑(v0，v1)從源點v0到v4有兩條路徑，其中以長度為15的路徑(v0，v2，v4)為最短路徑20301051291081518最短路徑--迪杰斯特拉最短路徑--迪杰斯特拉

迪杰斯特拉(Dijkstra)提出了一種按路徑長度遞增的次序求從源點到各終點的最短路徑的算法。這個算法就稱為迪杰斯特拉算法

有向網(wǎng)G?=?(V，E)，用鄰接矩陣存儲02030

1009

05

0

01215

010018

v0v1v2v3v4v5v620301051291081518

終點v1v2v3v4v6v5從v0到各終點的最短路徑及最短路徑長度求解過程i-1i-2i-3i-4i-5i-6(v0，v1)20(v0，v2)10(v0，v3)30

(v0，v1)20(v0，v3)30(v0,v2

,

v4)15

(v0，v1)20(v0,v2,v4,v3)27(v0,v2,v4,v6)30

(v0,v2,v4,v3)27(v0,v1,v6)29

(v0,v1,v6)29

v0v1v2v3v4v5v602030

1009

05

0

01215

010018

20301051291081518最短路徑--迪杰斯特拉算法實現(xiàn)過程中需要記錄依次找到的最短路徑建立一個集合S，初始時該集合只有源點v0，然后逐步將已求得最短路徑的頂點加入到集合中。

為了實現(xiàn)算法，需要引進輔助向量dist[]，它的每個分量dist[i]表示已經(jīng)找到的從開始點v0到終點vi的當前最短路徑的長度。它的初態(tài)為：如果從v0到vi有弧，則dist[i]為弧的權值；否則dist[i]

為∞。最短路徑--迪杰斯特拉v0v1v2v3v4v5v62030105129108151802030

1009

05

0

01215

010018

從dist[]向量中選擇一個長度最小的路徑dist[j]此路徑為(v0，vj)。設下一條最短路徑的終點是vk，這條路徑可能是弧(v0，vk)；可能是：v0到vj，vj到vk，路徑長度是從v0到vk的弧上的權值之和。最短路徑--迪杰斯特拉v0v1v2v3v4v5v62030105129108151802030

1009

05

0

01215

010018

dist[i](v0，v2)就是從v0到v2的最短路徑，dist[2]記錄最短路徑長度10這里我們選擇了(v0，v2)比如：從v0到v4初始值為無窮大，但是v0經(jīng)過v2再到v4有路徑，而且路徑長度是最短的，從v0到v4的路徑為：v0到v2，v2到v4，路徑長度為15。設置集合S：用于存放已經(jīng)找到的從v0出發(fā)的最短路徑的終點集合。用鄰接矩陣g表示網(wǎng)(1)S集合初態(tài)只包含一個頂點{v0}；輔助向量dist[i]

=

g.arcs[0][i]。(2)在向量dist中選擇路徑長度最短的一條路徑，v0到vk的路徑，將vk并入S集合。(3)更新向量dist，使得向量dist中始終記錄從v0出發(fā)到集合V-S上任意一個頂點vi的最短路徑。判斷V0是否可借助S中的頂點到達集合V-S上任一頂點vi？如果可達，且路徑長度比原來的短，就修改v0到vi的路徑，修改dist[i]，否則保持原來的路徑及原來的dist[i].(4)重復(2)、(3)步n-1次，逐個求出v0到圖其他每個頂點的最短路徑最短路徑--迪杰斯特拉n個頂點，自然要有循環(huán)做n次循環(huán)n次總的時間復雜度是O(n2)。循環(huán)n-1次循環(huán)n次

引入向量P、D、final;

P[v]記錄有向網(wǎng)G的v0頂點到其余頂點v的最短路徑;若P[v][w]?為1，則w是從v0到v當前求得最短路徑上的頂點；D[v]?記錄有向網(wǎng)G的v0頂點到其余頂點v的最短路徑長度；final[v]?為1，當且僅當v∈S，即已經(jīng)求得從v0到v的最短路徑。1voidDijkstra(GraphTypeG,intv0,PathMatrix*P,ShortPathTable*D)2{/*常量INFINITY為邊上權值可能的最大值*/3for(v=0;v<G.vexnum;++v) /*初始化*/4{5fianl[v]=0; /*v頂點屬于V-S集*/6D[v]=G.arcs[v0][v];/*初始化源點到其他頂點的最短路徑*/7P[v]=0; /*設空路徑*/8if(D[v]<INFINITY) /*初始化最短路徑上的點*/9P[v]=1;10}11D[v0]=0;final[v0]=1;/*初始化，v0頂點屬于S集*/引入向量P、D、final;

P[v]記錄有向網(wǎng)G的v0頂點到其余頂點v的最短路徑若P[v][w]?為1，則w是從v0到v當前求得最短路徑上的頂點；D[v]?記錄有向網(wǎng)G的v0頂點到其余頂點v的最短路徑長度；final[v]?為1，當且僅當v∈S，即已經(jīng)求得從v0到v的最短路徑。12for(i=1;i<G.vexnum;++i)/*其余G.vexnum-1個頂點*/13{/*開始主循環(huán)，每次求得v0到某個v頂點的最短路徑，并加v到S集*/14min=INFINITY;/*min為當前所知離v0頂點的最近距離*/15for(w=0;w<G.vexnum;++w)/*在v0到其他頂點vi中查找最短路徑*/16if(!final[w]) /*w頂點在V-S中*/17if(D[w]<min)18{v=w;19min=D[w];20}21final[v]=1 /*離v0頂點最近的v加入S集合*/22for(w=0;w>G.vexnum;++w)/*更新當前最短路徑*/if(!final[w]&&(min+G.arcs[v][w]<D[w]))/*修改D[w]和P[w]*24{D[w]=min+G.arcs[v][w];25P[w]=P[v];P[w][v]=1;/*P[w]=P[v]+P[w]*/26}}}/*Dijkstra*/算法的運行時間分析：設圖中有n個頂點，e條邊。語句3～語句10：for循環(huán)的次數(shù)為n，時間復雜度是O(n)。語句12～語句27：for循環(huán)共進行n-1次，其中包含兩個并列的循環(huán)，

語句15～語句20是查找最短路徑，循環(huán)n次；

語句22～語句26是更新當前最短路徑，循環(huán)n次。所以總的時間復雜度是O(n2)。7-5-2弗洛伊德算法

對于一個有向網(wǎng)，求每對頂點之間的最短路徑，顯然可調(diào)用Dijkstra算法。

具體方法是：每次以不同的頂點為源點，用Dijkstra算法求出從該頂點到其余頂點的最短路徑，反復執(zhí)行n次這樣的操作，就可得到從每個頂點到其余頂點的最短路徑。

最短路徑--弗洛伊德算法02030

1009

05

0

01215

010018

v0v1v2v3v4v5v620301051291081518這種方法的時間復雜度為O(n3)。574設用鄰接矩陣表示圖g最短路徑--弗洛伊德算法(1)求圖g中任意一對頂點vi、vj間的最短路徑。將vi到vj的最短路徑長度初始化為g.arcs[i][j]，這個不一定是vi到vj的最短的路徑，需要做n次試探。02030

1009

05

0

01215

010018

v0v1v2v3v4v5v6203010512910815185274(2)在vi、vj間加入頂點v0，判別(vi,v0,vj)是否存在(即判別弧(vi,v0)和(v0,vj)是否存在)。如果存在，比較(vi,v0,vj)和(vi,vj)的路徑長度，取其中較短的路徑作為vi到vj的且中間頂點號不大于0的最短路徑。設用鄰接矩陣表示圖g最短路徑--弗洛伊德算法02030

1009

05

0

01215

010018

v0v1v2v3v4v5v6203010512910815185274(3)再將頂點v1加入vi、vj間，若(vi,…,v1)和(v1,…,vj)分別是中間頂點序號不大于0的最短路徑，這兩條路徑在上一步中已求出。將(vi,…,v1,…,vj)與上一步已求出的且vi到vj中間頂點號不大于0的最短路徑比較，取其中較短的路徑作為vi到vj的且中間頂點號不大于1的最短路徑。(4)繼續(xù)在vi、vj間加入頂點v2、v3v4…..，依次類推，……經(jīng)過n次比較和修正，在第n步，將求得vi到vj的且中間頂點號不大于n的最短路徑，這必是從vi到vj的最短路徑。弗羅伊德算法

路徑可直接從鄰接矩陣獲得

vivjcost[i，j]v1中間頂點序號不大于1的最短路徑

v2中間頂點序號不大于2的最短路徑

…Vn中間頂點序號不大于n的最短路徑

圖g中所有頂點偶對<vi，vj>間的最短路徑長度對應一個n階方陣D。依次在<vi，vj>間增加v1,v2,v3……過程中，方陣D中的值不斷變化，對應一個n階方陣序列。定義一個n階方陣序列：

D(-1)，D(0)，D(1)，…，D(k)，…，D(n-1);其中：D(-1)用鄰接矩陣初始化，D(-1)[i][j]?=?G.arcs[i][j]D(k)[i][j]?=?Min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]}，0≤k≤n-1D(1)[i][j]?是從vi到vj的中間頂點的序號不大于1的最短路徑的長度；D(k)[i][j]?是從vi到vj的中間頂點的序號不大于k的最短路徑的長度；D(n-1)[i][j]?就是從vi到vj的最短路徑的長度。

最短路徑--弗洛伊德算法

為了能記錄路徑，我們定義一個方陣P，記錄所有頂點偶對<vi，vj>間的最短路徑，用它代表對應頂點的最短路徑的前驅矩陣。方陣P隨著D的變化而變化，所以，P也對應一個方陣序列：P(-1)，P(0)，P(1)，…，P(k)，…，P(n-1)。P(-1)是初始設置,P(-1)[i][j]?=?jP(1)[i][j]是從vi到vj的中間頂點的序號不大于1的最短路徑；P(k)[i][j]?是從vi到vj的中間頂點的個數(shù)不大于k的最短路徑；P(n-1)[i][j]?就是從vi到vj的最短路徑。

最短路徑--弗洛伊德算法

typedefintPathMatrix[MAXVEX][MAXVEX]typedefintDistancMatrix[MAXVEX][MAXVEX]1voidFloyd(GgraphG,PathMatrix*P[],DistancMatrix*D)2{3for(v=0;v<G.vexnum;++v)4for(w=0;w<G.vexnum;++w)5{6D[v][w]=G.arcs[v][w]; 7P[v][w]=w;8}9for(u=0;u<G.vexnum;++u)10for(v=0;v<G.vexnum;++v)11for(w=0;w<G.vexnum;++w)12if(D[v][u]+D[u][w]<D[v][w]) 13{14D[v][w]=D[v][u]+D[u][w];15P[v][w]=P[v][u];16}17}/*初始化DP;*//*先定義兩個矩陣DP*//*G：帶權有向圖，P[v][w]為v到w的當前最短路徑，D[v][w]記錄路徑長度*/最短路徑--弗洛伊德算法算法的時間復雜度為O(n3)Dijkstra、RobertFloyd這兩位科學家在計算機領域成果斐然，是我們學習的榜樣。

通過樹立榜樣，學習先進典型人物，鼓勵學生不懈努力、改革創(chuàng)新，思考計算機專業(yè)的新的方法和理論，助力科技強國，并注重新技術的應用轉化，提高生產(chǎn)生活效率。7.6有向無環(huán)圖及其應用一個無環(huán)的有向圖稱做有向無環(huán)圖(directedacyclinegraph)，簡稱DAG圖。DAG圖是一類較有向樹更一般的特殊有向圖。有向樹DAG有向示意圖對于無向圖來說，若深度優(yōu)先遍歷過程中遇到回邊(即指向已訪問過的頂點的邊)，則必定存在環(huán)；檢查一個有向圖是否存在環(huán)要比無向圖復雜，因為這條回邊有可能是指向深度優(yōu)先生成森林中另一棵生成樹上頂點的弧。但是，如果從有向圖上某個頂點v出發(fā)的遍歷，在深度優(yōu)先遍歷結束之前出現(xiàn)一條從頂點u到頂點v的回邊，由于u在生成樹上是v的子孫，則有向圖必定存在包含頂點v和u的環(huán)有向無環(huán)圖是描述一項工程或系統(tǒng)的進行過程的有效工具。除最簡單的情況之外，幾乎所有的工程(project)