軟件技術基礎13-14圖

圖

軟件技術基礎（六）西安電子科技大學

電子工程學院

林杰1本章要求1.基本要求（1）熟練掌握圖的定義，無向圖、有向圖、子圖、頂點的度、帶權圖、連通圖、強連通圖等的概念，邊（或?。┡c頂點之間的關系。掌握圖的兩種存儲方法，以及存儲結構的定義，了解建立圖的算法。（2）熟練掌握深度優(yōu)先和廣度優(yōu)先搜索遍歷圖的方法，了解相應的算法，寫出給定圖的遍歷序列。掌握生成樹的概念，了解相應的算法，根據(jù)兩種搜索遍歷的方法畫出生成樹；掌握最小生成樹的概念，用Prim（普里姆）和Kruskal（克魯斯卡爾）算法畫出最小生成樹。2.重點、難點重點：圖的定義及圖的概念，圖的遍歷方法和生成樹及最小生成樹。難點：圖的建立和遍歷算法，最小生成樹算法2本章內容7.1圖的基本概念7.2圖的存儲方法7.3圖的遍歷7.4生成樹和最小生成樹7.5最短路徑7.6拓撲排序7.7關鍵路徑3哥尼斯堡七橋問題（1736年）4能否從某個地方出發(fā)，穿過所有的橋僅一次后再回到出發(fā)點？5圖的實例：我的畢業(yè)旅行十三城市之間火車費用表十三城市之間火車行駛時間表方案1：最省錢方案2：最省時67.1圖的基本概念圖G是由一個頂點集V(G)和一個邊集E(G)構成的數(shù)據(jù)結構。記為二元組形式：G=(V,E)。其中:

V是由頂點構成的非空有限集合，記為：V＝{V0,V1,V2,…Vn-1}

E是由V中頂點的對偶構成的有限集合，記為：E={(V0,V2),(V3,V4),…}，若E為空，則圖中只有頂點而沒有邊。在線性表中，元素個數(shù)可以為零，稱為空表；在樹中，結點個數(shù)可以為零，稱為空樹；在圖中，頂點個數(shù)不能為零，但可以沒有邊。7其中頂點的對偶可以表示成：

(Vi,Vj)—無序的對偶稱為邊（edge），

即(Vi,Vj)=(Vj,Vi)，其圖稱為無向圖。<Vi,Vj>—有序的對偶稱為?。╝rc），

即<Vi,Vj>≠<Vj,Vi>，稱Vi為弧尾（tail）或起始點，稱Vj為弧頭（head）或終端點，該圖稱為有向圖。8無向圖：邊用(x,y)表示，且頂點x與y是無序的。V(G2)={A,B,C}E(G2)={(A,B),(B,C),(C,A)}

={(B,A),(C,B),(A,C)}ABC無向圖G2有向圖：邊用<x,y>表示，且x與y是有序的。a)有向圖中的邊又稱為“弧”

b)x:弧尾或弧的起始頂點；y:弧頭或弧的終止頂點V(G1)={A,B,C}E(G1)={<A,B>,<B,A>,<B,C>,<A,C>}ABC有向圖G19

（1）一條邊中涉及的兩個頂點必須不相同，即：若（vi，vj）或<vi，vj>是E(G)中的一條邊，則要求vi≠vj；（2）一對頂點間不能有相同方向的兩條有向邊；（3）一對頂點間不能有兩條無向邊。圖的說明V0V1V2V3V4V0V1V2V3V4V0V1V2V3數(shù)據(jù)結構中討論的都是簡單圖10

1）頂點的數(shù)目n與弧或邊的數(shù)目e的關系：無向圖：0≤e≤n(n-1)/2e=0：任意兩頂點之間都沒有邊

e=n(n-1)/2：任意兩頂點之間都有邊，稱為無向完全圖。有向圖：0≤e≤n(n-1)e=0：任意兩頂點之間都沒有弧

e=n(n-1)：任意兩頂點之間都有弧，稱為有向完全圖。V0V1V2V3V0V1V2112）稀疏圖：有很少條邊的圖（e<nlogn）稠密圖：e>=nlogn的圖3）子圖：設有兩個圖G＝(V,E)和G’＝(V’,E’)。若V’V且E’

E,則稱圖G’是圖G的子圖。ABC有向圖G1ABC有向圖G1的子圖G1’ABC無向圖G2ABC無向圖G2的子圖G2’12v1v2v3v4（a）無向完全圖G3子圖示例v1v2v4v2v3v4v1v2v3v4無向圖G3的部分子圖13v1v2v3v4（b）有向完全圖G4v1v4v2v3v4v1v1v3v2v4完全有向圖G4的部分子圖子圖示例144）鄰接點無向圖：若邊（Ｖi，Ｖj）∈E(G)則稱Ｖi和Ｖj相互鄰接，兩個頂點互為鄰接點，并稱邊（Ｖi，Ｖj

）關聯(lián)于頂點Ｖi和Ｖj或稱邊（Ｖi，Ｖj

）與頂點相關聯(lián)。有向圖：邊<Ｖi，Ｖj>∈E(G)則稱Ｖi鄰接到Ｖj

，或稱Ｖj鄰接于Ｖi，并稱邊<Ｖi，Ｖj>關聯(lián)于頂點Ｖi和Ｖj

，或稱邊<Ｖi，Ｖj>與頂點Ｖi和Ｖj相關聯(lián)。ABC無向圖G1ABC有向圖G215不同結構中邏輯關系的對比FECBAD線性結構ABCDEF樹結構V0V1V2V3V4圖結構在線性結構中，數(shù)據(jù)元素之間僅具有線性關系；在樹結構中，結點之間具有層次關系；在圖結構中，任意兩個頂點之間都可能有關系。16FECBAD線性結構ABCDEF樹結構V0V1V2V3V4圖結構在線性結構中，元素之間的關系為前驅和后繼；在樹結構中，結點之間的關系為雙親和孩子；在圖結構中，頂點之間的關系為鄰接。不同結構中邏輯關系的對比17

5）度，出度和入度有向圖

頂點v的入度ID(v)：以該頂點為終點的弧的數(shù)目；

頂點v的出度OD(v)：以該頂點為起點的弧的數(shù)目；

頂點v的度D(v)：D(v)=ID(v)+OD(v)；無向圖

頂點v的度D(v)：與該頂點相關聯(lián)的邊的數(shù)目；ABC有向圖G1ABC無向圖G2ID(A)=1OD(A)=2D(A)=3D(A)=2D(B)=2D(C)=218頂點的度與弧的關系對于一個有向圖或無向圖，如果具有n個頂點，e條邊（?。颐總€頂點的度為D(Vi)(1=<i<=n)，則存在以下關系：注：圖中的每條邊均關聯(lián)于兩個頂點ABC有向圖G1ABC無向圖G2196）權與網(wǎng)如果圖的邊或弧具有一個與它相關的數(shù)時，這個數(shù)就稱為該邊或弧的權。這個數(shù)常常用來表示距離或耗費。若將圖的每條邊都賦上一個權，則稱這種帶權圖為網(wǎng)絡，簡稱為網(wǎng)。V0V1V3V234567825V0V2V1455064（a）無向網(wǎng)絡G1

（b）有向網(wǎng)絡G220哈夫曼樹中的權與網(wǎng)圖的權有何區(qū)別？V0V1V2V327857423217）路徑與回路在圖G＝(V,E)中，若從頂點vi

出發(fā)，沿一些邊經過一些頂點vp1,vp2,…,vpm，到達頂點vj。則稱頂點序列(vi，vp1，vp2，...vpm，vj)為從頂點vi到頂點vj的路徑。它經過的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應是屬于E的邊。V0到V3的路徑：V0V3

V0

V1V2V3

V0

V1V4V2V3V0V1V2V3V4一般情況下，圖中的路徑不唯一22路徑長度:非帶權圖的路徑長度是指此路徑上邊/弧的條數(shù)。帶權圖的路徑長度是指路徑上各邊/弧的權之和。V0V1V2V3V4V0V3：路徑長度為1V0V1V2V3：路徑長度為3V0V1V4V2V3：路徑長度為4V0V3：路徑長度為8V0V1V2V3：路徑長度為7V0V1V4V2V3：路徑長度為15V0V1V2V3V425632823

簡單路徑：若路徑上各頂點v1,v2,...,vm均不互相重復,則稱這樣的路徑為簡單路徑?；芈罚喝袈窂缴系谝粋€頂點v1與最后一個頂點vm重合（路徑長度≥2）,則稱這樣的路徑為簡單回路或簡單環(huán)。

例如：

a:（0，1，3，2）是簡單路徑；

b:（0，1，3，0，1，2）是非簡單路徑；

c:（0，1，3，0）是簡單回路。0132a簡單路徑0132b非簡單路徑0132c回路24

有根圖：在一個有向圖中，若存在一個頂點v，從該頂點有路徑可到達圖中其它的所有頂點，則稱這個有向圖為有根圖，v稱為該圖的根。V0V1V2V3278525

8）連通圖連通：在無向圖中,若從頂點v1到頂點v2有路徑,則稱頂點v1與v2是連通的。連通圖：如果圖中任意一對頂點都是連通的,則稱此圖是連通圖。連通分量：非連通圖的極大連通子圖叫做連通分量。1.含有極大頂點數(shù)；2.依附于這些頂點的所有邊。V0V1V2V3V426

例：非連通圖及其連通分量示例V1V2V4V5V3（a）非連通圖V1V2V4V5V3（b）G5的兩個連通分量H1和H227強連通圖：在有向圖中,若對于每一對頂點vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強連通圖。強連通分量：非強連通圖的極大強連通子圖叫做強連通分量。ABCa：強連通圖ABCDEb：非強連通圖ABCDEc：（b）圖的兩個強連通分量28根據(jù)強連通圖的定義，可知強連通圖的唯一強連通分量是其自身，而非強連通的有向圖有多個強連通分量。例如，右圖所示的有向圖G4是一個具有4個頂點的強連通圖。v1v2v3v4有向完全圖G4

v1v2v3v4（a）非強連通圖G6下圖（a）所示的有向圖G6不是強連通圖（v2、v3、v4沒有到達v1的路徑），它的兩個強連通分量H3與H4如圖下圖（b）所示。v1v2v3v4（b）G6的兩個強連通分量H3和H4

299）生成樹，生成深林生成樹：n個頂點的連通圖G的生成樹是包含G中全部頂點的一個極小連通子圖。生成森林：在非連通圖中，由每個連通分量都可以得到一棵生成樹，這些連通分量的生成樹就組成了一個非連通圖的生成森林。多——構成回路少——不連通含有n-1條邊30V0V1V3V4V2V6V5V0V1V3V4V2V6V5V0V1V2V3V4V0V1V2V3V4生成樹生成森林317.2圖的存儲結構圖的存儲結構至少要保存兩類信息：

1)頂點的數(shù)據(jù)

2)頂點間的關系約定:G=<V,E>是圖,V={v0,v1,v2,…vn-1},設頂點的下標為它的編號。如何表示頂點間的關系？V0V1V2V3V4V0V1V2V37.2圖的存儲結構32由于圖結構中任意兩個頂點之間都可能存在“關系”，因此無法以簡單的順序存儲映象表示這種關系。常用的圖的存儲方法鄰接矩陣鄰接鏈表十字鏈表多重鏈表337.2.1鄰接矩陣圖的鄰接矩陣表示法，也稱為數(shù)組表示法。它采用兩個數(shù)組來表示圖。頂點表:一個存儲各個頂點信息的一維數(shù)組。鄰接矩陣：一個存儲各個頂點之間的關系（邊或?。┑亩S數(shù)組。設圖G=(V,E)是一個有n個頂點的圖，則圖的鄰接矩陣A[n][n]定義為：A[i][j]＝1若(vi,vj)∈E（或<vi,vj>∈E）0其它34無向圖的鄰接矩陣的特點？無向圖的鄰接矩陣V0V2V3V1V0V1V2V3vertex=0101101101001100A=V0V1V2V3V0V1V2V3主對角線為0且一定是對稱矩陣。頂點表

鄰接矩陣35無向圖的鄰接矩陣V0V2V3V1如何求頂點i的度？鄰接矩陣的第i行（或第i列）非零元素的個數(shù)。V0V1V2V3vertex=0101101101001100A=V0V1V2V3V0V1V2V3頂點表

鄰接矩陣0101101101001100A=V0V1V2V3V0V1V2V336無向圖的鄰接矩陣V0V2V3V1如何判斷頂點Vi

和Vj

之間是否存在邊？測試鄰接矩陣中相應位置的元素A[i][j]是否為1。V0V1V2V3vertex=頂點表

鄰接矩陣0101101101001100A=V0V1V2V3V0V1V2V337無向圖的鄰接矩陣V0V2V3V1如何求頂點i的所有鄰接點？將數(shù)組中第i行元素掃描一遍，若A[i][j]為1，則頂點j為頂點i的鄰接點。V0V1V2V3vertex=頂點表

鄰接矩陣38有向圖的鄰接矩陣V0V1V2V3V0V1V2V3vertex=0110000000011000A=V0V1V2V3V0V1V2V3有向圖的鄰接矩陣一定不對稱嗎？不一定，例如有向完全圖。39有向圖的鄰接矩陣V0V1V2V3V0V1V2V3vertex=0110000000011000A=V0V1V2V3V0V1V2V3如何求頂點i的出度？鄰接矩陣的第i行元素之和。40有向圖的鄰接矩陣V0V1V2V3V0V1V2V3vertex=0110000000011000A=V0V1V2V3V0V1V2V3如何求頂點i的入度？鄰接矩陣的第i列元素之和。41有向圖的鄰接矩陣V0V1V2V3V0V1V2V3vertex=0110000000011000A=V0V1V2V3V0V1V2V3如何判斷頂點i和j之間是否存在邊？測試鄰接矩陣中相應位置的元素A[i][j]是否為1。42

約定：頂點的“第一個”鄰接點：該頂點所對應的行中值為非零元素的最小列號所代表的頂點，其“下一個”鄰接點就是同行中離它次最近的值為非零元素的列號所代表的頂點。例如有向圖G1中頂點V0的第一個鄰接點為"頂點V1"，下一個鄰接點是"頂點V2"。V0V1V2V3V0V1V2V3vertex=0110000000011000A=V0V1V2V3V0V1V2V343網(wǎng)絡，鄰接矩陣元素A[i,j]可按以下規(guī)則取值：網(wǎng)絡的鄰接矩陣表示A[i][j]＝

wij

若(vi,vj)∈E（或<vi,vj>∈E）0若i=j∞其他V0V1V2V32785025∞∞0∞

∞

∞

∞087∞∞0A=V0V1V2V3V0V1V2V344當一個圖用鄰接矩陣表示時，可用以下數(shù)據(jù)類型來定義：#define n圖的頂點數(shù)

#define e圖的邊數(shù)

typedefcharvextype;//頂點的數(shù)據(jù)類型

typedeffloatadjtype;//頂點權值的數(shù)據(jù)類型

typedefstruct

{

vextypevexs[n];//頂點數(shù)組

adjtypearcs[n][n];//鄰接矩陣

}graph;頂點表和鄰接矩陣中結點的數(shù)據(jù)類型45無向網(wǎng)絡鄰接矩陣建立算法:voidCreatGraph(graphg)//建立無向網(wǎng)絡{inti,j,k;floatw;

for(i=0;i<n;i++)

g->vexs[i]=getchar();//讀入頂點信息，建立頂點表

for(i=0;i<n;i++)

for(j=0;j<n;j++)g->arcs[i][j]=0;//鄰接矩陣初始化

for(k=0;k<e;k++)

{scanf(“%d,%d,%f”,&i,&j,&w);//讀入邊(vi,vj)上的權wg->arcs[i][j]=w;//寫入鄰接矩陣

g->arcs[j][i]=w;

}}//CreatGraph時間復雜度O(n2+e），由于e<<n2,所以時間復雜度是O(n2)建立無向圖，可以在算法中直接對鄰接矩陣的元素賦1建立有向網(wǎng)絡，只須將寫入矩陣的兩個語句中的后一個語句g->arcs[j][i]=w去掉即可467.2.2鄰接表鄰接表存儲的基本思想對于圖的每個頂點vi，將所有鄰接于vi的頂點鏈成一個單鏈表，稱為頂點vi的邊表（對于有向圖則稱為出邊表）。所有邊表的頭指針和存儲頂點信息的一維數(shù)組構成了頂點表。圖的鄰接矩陣存儲結構的空間復雜度？如果為稀疏圖，會出現(xiàn)什么現(xiàn)象？

假設圖G有n個頂點e條邊，則存儲該圖需要O(n2)477.2.2鄰接表鄰接表包括：（1）頂點表；（2）鄰接鏈表鄰接表存儲方法是一種順序存儲（頂點表）與鏈式存儲（鄰接鏈表）相結合的存儲方法。

頂點表：頂點信息和單鏈表的頭指針一起存儲在一個一維數(shù)組中。一維數(shù)組要想表示兩類數(shù)據(jù)類型(頂點信息和頭指針)，則必須定義成結構體的數(shù)組。

鄰接鏈表：將和同一頂點“相鄰接”的所有鄰接點鏈接在一個單鏈表中。48頂點表和鄰接鏈表中結點的數(shù)據(jù)類型typedefcharvextype;//定義頂點數(shù)據(jù)信息類型；typedefstructnode//鄰接鏈表結點，也叫弧結點的結構；{

int

adjvex;//鄰接點域，該弧所指向的頂點的位置/下標；

structnode*next;//鏈域，指向下一條弧的指針；

}edgenode;

typedefstruct//頂點的結構

{

vextype

vertex;//頂點域，放置頂點信息；

edgenode

*link;//指針域，指向第一條依附于該頂點的弧

}vexnode;vexnodega[n];//頂點表49頂點表和鄰接鏈表中結點的數(shù)據(jù)類型鄰接表有兩種結點結構：頂點表結點和鄰接鏈表結點vertexlink

adjvex

next

頂點表鄰接鏈表vertex：數(shù)據(jù)域，存放頂點信息。link：指針域，指向邊表中第一個結點。adjvex：鄰接點域，邊的終點在頂點表中的下標。next：指針域，指向邊表中的下一個結點。50邊表，出邊表，入邊表邊表：對于無向圖，Vi的鄰接鏈表中每個結點都對應與Vi相關聯(lián)的一條邊，所以將此鄰接鏈表稱為邊表。出邊表：對于有向圖，Vi的鄰接鏈表中每個結點都對應于以Vi為起始點射出的一條邊（?。?，所以有向圖的鄰接鏈表也稱為出邊表。入邊表：有向圖還有另外一種表示法，叫入邊表。即Vi鄰接鏈表中的每個結點對應于以Vi為終點的一條邊。51103∧23∧1∧01∧V0V1

V2V30123vertexlinkV0V2V3V1無向圖的鄰接表邊表中的結點表示什么？每個結點對應圖中的一條邊，鄰接表的空間復雜度為O(n+e)。頂點表邊表52103∧23∧1∧01∧V0V1

V2V30123vertexlinkV0V2V3V1無向圖的鄰接表如何求頂點i的度？頂點i的邊表中結點的個數(shù)。頂點表邊表頂點v的度D(v)：與該頂點相關聯(lián)的邊的數(shù)目53103∧23∧1∧01∧V0V1

V2V30123vertexlinkV0V2V3V1無向圖的鄰接表如何判斷頂點i和頂點j之間是否存在邊?測試頂點i的邊表中是否存在終點為j的結點。(或測試頂點j的邊表中是否存在終點為i的結點。)頂點表邊表54有向圖的鄰接表V0V1V2V312∧3∧0∧V0V1

V2V30123vertexlink∧如何求頂點i的出度？頂點i的出邊表中結點的個數(shù)。頂點表出邊表55有向圖的鄰接表V0V1V2V312∧3∧0∧V0V1

V2V30123vertexlink∧如何求頂點i的入度？各頂點的出邊表中以頂點i為終點的結點個數(shù)之和。頂點表出邊表56有向圖的鄰接表V0V1V2V312∧3∧0∧V0V1

V2V30123vertexlink∧如何判斷頂點i和頂點j之間是否存在邊?搜索兩個結點對應的單鏈表頂點表出邊表57網(wǎng)圖的鄰接表V0V1V2V3278521V0V1

V2V30123vertexlink∧52∧83∧70∧邊表中，添加一個“權值域”58無向圖鄰接表的建立算法1.確定圖的頂點個數(shù)和邊的個數(shù)；2.輸入頂點信息，初始化該頂點的邊表；3.依次輸入邊的信息并存儲在邊表中；

3.1輸入邊所依附的兩個頂點的序號i和j；

3.2生成鄰接點序號為j的邊表結點s；

3.3將結點s插入到第i個邊表的頭部；

3.4生成鄰接點序號為i的邊表結點s；

3.5將結點s插入到第j個邊表的頭部；59建立鄰接表的主要操作是在鏈表中插入一個結點，以下是輸入圖的頂點和邊建立鄰接表的算法。

voidCreatgraphlist(vexnodega[])//建立無向圖的鄰接表{inti,j,k;

edgenode

*s;

for(i=0;i<n;i++)

{ga[i].vertex=getchar();

//讀入頂點信息

ga[i].link=NULL;

//對邊表的頭指針初始化

}//頂點表初始化頂點表數(shù)組的基地址無向圖鄰接表的建立算法60for(k=0;k<e;k++)//采用頭插法建立邊表{scanf(“%d%d”,&i,&j);//讀入邊(vi,vj)的頂點序號（數(shù)組下標）

s=(edgenode*)malloc(sizeof(edgenode));//生成鄰接點序號為j的邊表結點s

s->adjvex=j;

s->next=ga[i].link;//①將s插入頂點vi的邊表頭部

ga[i].link=s;//②

s=(edgenode*)malloc(sizeof(edgenode));//生成鄰接點序號為i的邊表結點s

s->adjvex=i;

s->next=ga[j].link;

//①將s插入頂點vj的邊表頭部

ga[j].link=s;//②

}}//Creatgraphlist時間復雜度O(n+e)12V0V1

V2V30123∧∧∧∧①②s鄰接表的建立算法說明對于無向圖，每輸入一條邊需要生成兩個結點，分別插入在這條邊的兩個頂點的鏈表中。即無向圖的鄰接表中邊結點的個數(shù)為圖中邊的數(shù)目的兩倍。對于有向圖，鄰接表中弧結點的個數(shù)與圖中邊的數(shù)目相等。61圖的存儲結構的比較:鄰接矩陣和鄰接表62O(n2)O(n+e)O(n2)O(n+e)空間性能時間性能適用范圍唯一性鄰接矩陣鄰接表稠密圖稀疏圖唯一不唯一7.3圖的遍歷圖的遍歷是指從圖中某一頂點出發(fā)，沿著某條搜索路徑使圖中每個頂點僅被訪問一次。圖的遍歷操作要解決的關鍵問題

①在圖中，如何選取遍歷的起始頂點？解決方案：從編號小的頂點開始。在圖中，任何兩個頂點之間都可能存在邊，頂點是沒有確定的先后次序的，所以，頂點的編號不唯一。為了定義操作的方便，將圖中的頂點按任意順序排列起來，比如，按頂點的存儲順序。6364②從某個起點始可能到達不了所有其它頂點，怎么辦？

解決方案：多次調用從某頂點出發(fā)遍歷圖的算法。僅討論從某頂點出發(fā)遍歷圖的算法。③因圖中可能存在回路，某些頂點可能會被重復訪問，那么如何避免遍歷不會因回路而陷入死循環(huán)?解決方案：附設訪問標志數(shù)組visited[n]。④在圖中，一個頂點可以和其它多個頂點相連，當這樣的頂點訪問過后，如何選取下一個要訪問的頂點？解決方案：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。7.3.1深度優(yōu)先搜索遍歷基本思想

：⑴訪問頂點v；⑵從v的未被訪問的鄰接點中選取一個頂點w，從w出發(fā)進行深度優(yōu)先遍歷；⑶重復上述兩步，直至圖中所有和v有路徑相通的頂點都被訪問到。65深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?深度優(yōu)先搜索遍歷V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5

V5棧深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5V8

V8深度優(yōu)先搜索遍歷棧深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5V8深度優(yōu)先搜索遍歷棧深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8

V1遍歷序列：V1

V7V2V4V5V8V3

V3V6

V6V7深度優(yōu)先搜索遍歷棧7.3.1深度優(yōu)先搜索遍歷對于一個圖，按深度優(yōu)先搜索遍歷先后順序得到的頂點序列稱為圖的深度優(yōu)先搜索遍歷序列（簡稱DFS序列,depth-firstsearch）。一個圖的DFS序列并不唯一，它與遍歷算法（選擇Vj的原則）、圖的存儲結構和初始出發(fā)點有關。707.3.1深度優(yōu)先搜索遍歷從頂點V0出發(fā)的深度遍歷序列：

A、B、C、E、D從頂點V1出發(fā)的深度遍歷序列：

B、A、D、E、C從頂點V2出發(fā)的深度遍歷序列：

C、B、A、D、E717.3.1深度優(yōu)先搜索遍歷當確定了按照鄰接點的序號從小到大進行選擇鄰接點時，確定了初始出發(fā)點，同時鄰接矩陣或者鄰接表也確定后，DFS就唯一了。對于鄰接表存儲，也就是要確定鄰接表中結點的鏈接次序。727.3.1深度優(yōu)先搜索遍歷DFS:ABCED7373頂點表邊表/鄰接鏈表

A

B

C

D

1

3

1

0

4

0

E

0

2

4

1

∧

∧

∧

∧

∧

74鄰接矩陣作為圖的存儲結構，深度優(yōu)先遍歷算法：intvisited[n];//定義visited為全局變量，n為頂點數(shù)graphg;//g為全局變量voidDFSA(inti)//從vi出發(fā)深度優(yōu)先搜索圖g，g用鄰接矩陣表示{intj;printf(“node:%c\n”,g.vexs[i]);//訪問出發(fā)點vi

visited[i]=1;//標記vi已被訪問

for(j=0;j<n;j++)//按頂點序號從小到大依次搜索vi的某個鄰接點

if((g.arcs[i][j]==1)&&(visited[j]==0))

DFSA(j);//若vi的鄰接點vj未被訪問過，則從vj出發(fā)進行深度優(yōu)先搜索遍歷}//DFSA時間復雜度O(n2)75鄰接表作為圖的存儲結構，深度優(yōu)先搜索遍歷算法：voidDFSL(inti)//從vi出發(fā)深度優(yōu)先搜索遍歷圖ga，用鄰接表表示{edgenodep;

printf(“node:%c\n”,ga[i].vertex);//訪問頂點vi

visited[i]=1;//標記vi已被訪問

p=ga[i].link;//取vi的邊表頭指針

while(p!=NULL)//依次搜索vi的鄰接點

{if(visited[p->adjvex]==0)

DFSL(p->adjvex);//從vi的未曾訪問過的鄰接點出發(fā)進行深度優(yōu)先遍歷

p=p->next;

}}//DFSL

時間復雜度O(n+e)注：由于圖的鄰接表表示不唯一，所以DFSL算法得到的DFS序列也不唯一。7.3.2廣度優(yōu)先搜索遍歷基本思想：⑴訪問頂點v；⑵依次訪問v的各個未被訪問的鄰接點v1,v2,…,vk；⑶分別從v1，v2，…，vk出發(fā)依次訪問它們未被訪問的鄰接點，并使“先被訪問頂點的鄰接點”先于“后被訪問頂點的鄰接點”被訪問。(4)直至圖中所有與頂點v有路徑相通的頂點都被訪問到。767.3.2廣度優(yōu)先搜索遍歷注：廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點，不像深度優(yōu)先搜索那樣有往回退的情況。因此，廣度優(yōu)先搜索不是一個遞歸的過程，其算法也不是遞歸的。和樹的廣度優(yōu)先搜索一樣，用隊列實現(xiàn)。7778廣度優(yōu)先搜索遍歷的順序和結束條件:根據(jù)廣度遍歷思想，先遍歷的結點，其相鄰結點一定首先被遍歷。

故采用隊列來構造遍歷順序。對于連通圖，結束條件是隊列為空；對于非連通圖，結束條件是隊列為空并且圖的所有結點都被遍歷。7.3.2廣度優(yōu)先搜索遍歷廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V1廣度優(yōu)先搜索遍歷廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V2V3V3廣度優(yōu)先搜索遍歷廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V3V4V4V5V5廣度優(yōu)先搜索遍歷廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V4V5V5V6V6V7V7廣度優(yōu)先搜索遍歷廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V5V5V6V6V7V7V8V8廣度優(yōu)先搜索遍歷84BFSA：以鄰接矩陣為存儲結構時的廣度優(yōu)先搜索遍歷算法。BFSL：以鄰接表為存儲結構時的廣度優(yōu)先搜索遍歷算法。一個圖的BFSA和BFSL序列都不唯一，它與算法、存儲結構和初始出發(fā)點有關。當確定了按照序號（下標）從小到大的方式進行選擇鄰接點，確定了初始出發(fā)點后，以鄰接矩陣作為存儲結構得到的BFSA就唯一了。當采用鄰接表存儲時還必須確定邊表結點的鏈接次序，BFSL才唯一。85鄰接矩陣作為圖的存儲結構，廣度優(yōu)先搜索遍歷算法如下：voidBFSA(intk)//從vk出發(fā)廣度優(yōu)先搜索遍歷圖g，g用鄰接矩陣表示{ int i,j;

SETNULL(*sq);//sq置為空隊

printf(“%c\n”,g.vexs[k]);//訪問出發(fā)點vk

visited[k]=1;//標記vk已被訪問

ENQUEUE(*sq);//訪問過的頂點序號入隊,為訪問它的鄰接點作準備

while(!EMPTY(*sq))//隊非空時執(zhí)行下列操作

{i=DEQUEUE(*sq);//隊頭元素序號出隊

for(j=0;j<n;j++)//

if((g.arcs[i][j]==1)&&(visited[j]!=1))

{printf(“%c\n”,g.vexs[j]);visited[j]=1;

ENQUEUE(sq,j);//訪問過的頂點入隊

}//按頂點序號從小到大的順序，訪問未曾訪問的vi的鄰接點vj

}}//BFSA86鄰接表作為圖的存儲結構，廣度優(yōu)先搜索遍歷算法如下：voidBFSL(intk)//從vk出發(fā)廣度優(yōu)先搜索遍歷鄰接表圖ga{ inti;edgenodep;

SETNULL(sq);//置空隊

printf(“%c\n”,ga[k].vertex);//訪問出發(fā)點vk

visited[k]=1;//標記vk已被訪問

ENQUEUE(sq,k);//訪問過的頂點序號入隊,為訪問它的鄰接點作準備

while(!EMPTY(sq))

{i=DEQUEUE(sq);//隊頭元素序號出隊

p=ga[i].link;//取vi的邊表頭指針

while(p!=NULL)//依次搜索vi的鄰接點

{if(visited[p->adjvex]!=1)//vi的鄰接點未曾訪問

{printf(“%c\n”,ga[p->adjvex].vertex);

visited[p->adjvex]=1;

ENQUEUE(sequeue*sq,p->adjvex);//訪問過的頂點入隊

}p=p->next;

}

}}//BFSL87圖的廣度優(yōu)先遍歷實例:以下圖為例說明，從結點A開始ADBCEFG01324560123456visited[]queue初始狀態(tài)frADBCEFG01324560123456visited[]queuefr訪問開始結點A，并將A的序號入隊10r880123456visited[]1queue0fr0123456visited[]1queue0frfADBCEFG0132456ADBCEFG0132456A的序號出隊，同時訪問其所有的鄰接點：B,C并將B,C的下標按照次序依次入隊1rr2111211序號為1的B出隊，同時訪問其所有的鄰接點：D,E并將D,E的下標按照次序依次入隊f11rr34890123456visited[]1queue0ADBCEFG01324561211序號為2的C出隊，同時訪問其未被訪問的鄰接點：F并將F的下標按照次序依次入隊f11r34f1r50123456visited[]1queue0ADBCEFG01324561211序號為3的D出隊，D鄰接點B已訪問過，不執(zhí)行入隊操作1134f1r5f900123456visited[]1queue0ADBCEFG01324561211序號為4的E出隊同時訪問其未被訪問的鄰接點：G并將G的下標按照次序依次入隊11341r5ff1r60123456visited[]1queue0ADBCEFG01324561211序號為5的F出隊F鄰接點C，G已訪問過，不執(zhí)行入隊操作113415f1r6f910123456visited[]1queue0ADBCEFG01324561211序號為6的G出隊G的鄰接點E,F已訪問過，不執(zhí)行入隊操作1134151r6ff此時，隊列已空。搜索過程結束。根據(jù)訪問的順序，得到的BFS序列為A，B，C，D，E，F(xiàn)，G7.4生成樹和最小生成樹樹：圖論中的樹是指一個沒有回路的連通圖。生成樹：一個連通圖G的生成樹指的是一個包含了G的所有頂點的樹，是一個具有n個頂點n-1條邊的極小連通子圖.92多——構成回路少——不連通含有n-1條邊V0V1V2V3V4V0V1V2V3V4生成樹7.4生成樹和最小生成樹構造無向圖的生成樹的方法：

給定一個無向連通圖G，從G的任意頂點Vi出發(fā)，作一次深度優(yōu)先或廣度優(yōu)先搜索遍歷，遍歷過程中所經歷過的n-1條邊就構成了G的生成樹，頂點Vi是生成樹的根。937.4生成樹和最小生成樹94

深度優(yōu)先搜索生成樹（DFS生成樹）

廣度優(yōu)先搜索生成樹（BFS生成樹）生成樹連通圖的生成樹不是唯一的，它取決于遍歷算法和遍歷的起始頂點。在遍歷算法確定之后，從不同頂點出發(fā)進行遍歷得到的生成樹可能不同。對于非連通圖，生成的是包含若干棵樹的森林。95鄰接矩陣作為圖的存儲結構，構造DFS生成樹的算法intvisited[n];//定義visited為全局變量，n為頂點數(shù)

graph*g=(graph*)malloc((sizeof(graph));//產生圖的存儲空間voidDFSA(inti)//從vi出發(fā)，構造*g的DFS生成樹{intj;printf(“node:%c\n”,g->vexs[i]);//訪問出發(fā)點vi

visited[i]=1;//標記vi已被訪問

for(j=0;j<n;j++)//按頂點序號從小到大依次搜索vi的某個鄰接點

if((g->arcs[i][j]==1)&&(visited[j]==0)){printf(“(v%d,v%d)\n”,i,j);//輸出邊（vi，vj）

DFSA(j);}//若vi的鄰接點vj未被訪問過，則從vj出發(fā)進行深度優(yōu)先搜索遍歷}//DFSA96鄰接矩陣作為圖的存儲結構，構造BFS生成樹的算法voidBFSA(intk)//從vk出發(fā)廣度優(yōu)先搜索遍歷圖g，g用鄰接矩陣表示{ int i,j;

SETNULL(*sq);//sq置為空隊

printf(“%c\n”,g.vexs[k]);//訪問出發(fā)點vk

visited[k]=1;//標記vk已被訪問

ENQUEUE(*sq);//訪問過的頂點序號入隊,為訪問它的鄰接點作準備

while(!EMPTY(*sq))//隊非空時執(zhí)行下列操作

{i=DEQUEUE(*sq);//隊頭元素序號出隊

for(j=0;j<n;j++)//if((g.arcs[i][j]==1)&&(visited[j]!=1))

{printf(“(v%d,v%d)\n”,i,j);//輸出邊（vi，vj）

printf(“%c\n”,g.vexs[j]);visited[j]=1;

ENQUEUE(sq,j);//訪問過的頂點入隊

}//按頂點序號從小到大的順序，訪問未曾訪問的vi的鄰接點vj

}}//BFSA例：從頂點A出發(fā)的DFS生成樹和BFS生成樹。977.4生成樹和最小生成樹ABDCEABDCEDFS生成樹ABDCEBFS生成樹98最小生成樹的應用背景：例1：由于在n個居民點間構建通訊網(wǎng)只需架設n-1條線路，則工程隊面臨的問題是架設哪幾條線路能使總的工程費用最低？

例2：n個城市之間鋪設煤氣管道問題等。類似此類的問題很多。這些問題均等價于，在含有n個頂點的連通網(wǎng)中選擇n-1條邊，構成一棵極小連通子圖，并使該連通子圖中n-1條邊上權值之和達到最小的問題。7.4生成樹和最小生成樹最小生成樹（MST）：對一個連通網(wǎng)絡構造生成樹，可以得到一棵帶權的生成樹。我們把生成樹各邊的權值總和作為生成樹的權值，而具有最小權值的生成樹就是連通網(wǎng)絡的最小生成樹。構造準則:盡可能用網(wǎng)絡中權值最小的邊；必須使用且僅使用n-1條邊來連接網(wǎng)絡中的n個頂點；不能使用產生回路的邊。997.4生成樹和最小生成樹構造最小生成樹的兩種算法1.prim（普里姆）算法2.Kruskal(克魯斯卡爾)算法1007.4生成樹和最小生成樹1017.4.2prim（普里姆）算法設G(V,E)是有n個頂點的連通網(wǎng)絡，T=(U,TE)是要構造的生成樹。初始時U={φ}，TE={φ}。首先從V中取出一個頂點u0放入生成樹的頂點集U中作為第一個頂點(根結點），此時T=({u0},{φ})；然后從uU，vV-U的邊(u,v)中找一條代價最小的邊(u*,v*)放入TE中，且將v*放入U中，此時T=({u0,v*},{(u0,v*)})；重復（2），直到U=V為止。這時T的TE中必有n-1條邊，構成所要構造的最小生成樹。關鍵:是如何找到連接U和V-U的最短邊。102在生成樹的構造過程中，圖中n個頂點分屬兩個集合：已落在生成樹上的頂點集U和尚未落在生成樹上的頂點集V-U，則應在所有連通U中頂點和V-U中頂點的邊中選取權值最小的邊。

一般情況下所添加的頂點應滿足下列條件:UV-U103Prim算法構造最小生成樹實例以下圖為例說明構造過程，從頂點0開始801234510321117657V012345UV-U012345TE801234510321117657V012345U0V-U12345TE0,220104801234510321117657V012345U02V-U1345TE0,2801234510321117657V012345U024V-U135TE0,22,42,42,141105801234510321117657V012345U0241V-U35TE0,22,42,14,3801234510321117657V012345U02413V-U5TE0,22,42,14,33,535106801234510321117657V012345U024135V-UTE0,22,42,14,33,5012345321157107顯然，prim算法的關鍵是如何找到連接U和V-U的最短邊來擴充T。設當前生成樹T中已有K個頂點，則U和V-U中可能存在的邊數(shù)最多為K（n-K）條，在如此多的邊總尋找一條代價最小的邊是困難的。由于尋找過程具有可重復性，所以可通過將前一次所尋找得到的最小邊存儲起來，然后與新找到的邊進行比較，如果新邊短，則替換，否則不替換。7.4.2prim（普里姆）算法1087.4.2prim（普里姆）算法邊的存儲結構：typedefstruct{intfromvex,endvex;//邊的起點和終點

floatlength;//邊的權值}edge;edge

T[n-1];//最小生成樹，有n-1條邊圖的存儲結構：由于在算法執(zhí)行過程中，需要不斷讀取任意兩個頂點之間邊的權值，所以，圖采用鄰接矩陣存儲。float

dist[n][n];//連通網(wǎng)絡的帶權鄰接矩陣109算法7.7最小生成樹的Prim算法。voidPrim(inti) //i表示最小生成樹所選取的第一個頂點下標{intj,k,m,v,min,max=100000;

floatd;

edgee;v=i; //將選定頂點送入中間變量vfor(j=0;j<=n-2;j++) //構造第一個頂點

{T[j].fromvex=v;if(j>=v)

{T[j].endvex=j+1;T[j].length=dist[v][j+1];}else

{T[j].endvex=j;T[j].length=dist[v][j];}}7.4.2prim（普里姆）算法11001234500103∞∞∞1100586∞2350∞2∞3∞8∞07114∞6270175∞∞∞11170鄰接矩陣dist[6][6];fromvexendvexlength01234T[5],n=60000012435103∞∞∞V=0;801234510321117657111for(k=0;k<n-1;k++)//求第k條邊{

min=max;for(j=k;j<n-1;j++)//找出最短的邊，并將最短邊的下標記錄在m中

{if(T[j].length<min)

{min=T[j].length;m=j;}}e=T[m];T[m]=T[k];T[k]=e;//將最短的邊交換到T[k]單元中v=T[k].endvex;//存放新找到的最短邊在V-U中的頂點

for(j=K+1;j<n-1;j++)//修改所存儲的最小邊集

{d=dist[v][T[j].endvex];

if(d<T[j].length)

{T[j].length=d;T[j].fromvex=v;}}}}fromvexendvexlength01234112T[5],n=60000012435103∞∞∞max=10000;min=max;min=T[j].length<min?T[j].length:min;k=0;m=j;V=T[k].endvex=2V=0;113fromvexendvexlength012340000021435310∞∞∞k=0;d=dist[v][T[j].endvex]j=K+1,K+2,…,n-2V=2if(d<T[j].length)

{T[j].length=d;T[j].fromvex=v;}25d[2][1]=5新起點可能的終點d[2][3]=∞d[2][4]=222d[2][5]=∞修改存儲的最小邊集T[5],n=6114fromvexendvexlength01234000214353∞∞k=1;2522T[5],n=6時間復雜度O(n2)，與網(wǎng)的邊數(shù)無關。適合邊稠密網(wǎng)絡的最小生成樹1157.4.3Kruskal(克魯斯卡爾)算法克魯斯卡爾算法的基本思想：為使生成樹上總的權值之和達到最小，則應使每一條邊上的權值盡可能地小。自然應從權值最小的邊選起，直至選出n-1條互不構成回路的權值最小邊為止。1167.4.3Kruskal(克魯斯卡爾)算法具體作法如下：首先構造一個只含n個頂點的森林V；然后依權值從小到大從連通網(wǎng)中選擇不使森林中產生回路的邊加入到森林中去直至該森林變成一棵樹為止這棵樹便是連通網(wǎng)的最小生成樹。

117

問題：由于生成樹上不允許有回路，因此并非每一條當前權值最小的邊都可選。那么在算法中如何判別當前權值最小邊的兩個頂點之間是否已經連通？從生成樹的構造過程可見，初始態(tài)為n個頂點分屬n棵樹，互不連通，每加入一條邊，就將兩棵樹合并為一棵樹，在同一棵樹上的兩個頂點之間自然相連通。由此判別當前權值最小邊是否可取只要判別它的兩個頂點是否在同一棵樹（連通分量）上即可。

7.4.3Kruskal(克魯斯卡爾)算法118V012345TE21041321856101961451133041325初始連通分量T=（V,TE）0413255V012345TE加入（1,2）后的連通分量21041321856101961451133（1,2）119由于(2,3)和(1,3)的權值都是6，因此可以加入(2,3)或者(1,3)V012345TE（1,2）加入（2,3）后的連通分量2104132185610196145113304132556(2,3)V012345TE（1,2）（2,3）加入（0,5）后的連通分量210413218561019614511330413255610(0,5)120V012345TE（1,2）（2,3）（0,5）加入（1,5）后的連通分量21041321856101961451133041325561011V01234