計算機軟件基礎(chǔ)課件：圖

圖BasicsofComputerSoftware答辯人：XXX

目錄圖的基本概念1圖的存儲結(jié)構(gòu)2圖的遍歷3圖的應(yīng)用4圖的基本概念PART1基本概念連通性問題拓?fù)渑判驁D的存儲結(jié)構(gòu)圖的遍歷最小生成樹最短路徑關(guān)鍵路徑圖的基本概念圖的定義：圖是由頂點集合及頂點間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：

Graph＝(V,E)其中：V={x|x

某個數(shù)據(jù)對象}是頂點的有窮非空集合；E={(x,y)|x,y

V}是頂點之間關(guān)系的有窮集合，也叫做邊或弧的集合，此時的圖稱為無向圖（邊）或有向圖（弧）。無向圖：在無向圖中，頂點對(x,y)是無序的。有向圖：在有向圖中，頂點對<x,y>是有序的。無向完全圖：若有n個頂點的無向圖有n(n-1)/2條邊,則此圖為無向完全圖。即任何2頂點間均有一條邊存在。有向完全圖：有n個頂點的有向圖有n(n-1)條弧,則此圖為有向完全圖。即任何2頂點間均有一對方向相反的弧存在。12033456120012無向完全圖有向完全圖012圖的基本概念

鄰接頂點：如果(u,v)是E(G)中的一條邊，則稱u與v互為鄰接頂點。子圖：設(shè)有兩個圖G＝(V,E)和G’＝(V’,E’)。若V’

V且E’

E,則稱圖G’是圖G的子圖。1203子圖1030321320圖的基本概念權(quán)：某些圖的頂點或邊具有與它相關(guān)的數(shù),稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。如：交通網(wǎng)的公里數(shù)、工程造價圖中的造價頂點的度TD(v)：一個頂點v的度是與它相關(guān)聯(lián)的邊的條數(shù)。在有向圖中,頂點的度等于該頂點的入度與出度之和。入度ID(v):是以v為終點（弧頭）的弧的條數(shù)

出度OD(v):是以v為始點（弧尾）的弧的條數(shù)圖的基本概念A(yù)BECF有向圖頂點的度(TD)=出度(OD)+入度(ID)TD(B)=OD(B)+ID(B)=3圖的基本概念路徑：在圖G＝(V,E)中,若從頂點vi出發(fā),沿一些邊經(jīng)過一些頂點vp1,vp2,…,vpm，到達(dá)頂點vj。則稱頂點序列(vivp1vp2...vpmvj)為從頂點vi

到頂點vj

的路徑。它經(jīng)過的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應(yīng)是屬于E的邊。1203路徑：0,1,2,3ABECF路徑：A,E,C,F圖的基本概念路徑長度：非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和。簡單路徑：若路徑上各頂點v1,v2,...,vm均不互相重復(fù),則稱這樣的路徑為簡單路徑?；芈罚喝袈窂缴系谝粋€頂點v1與最后一個頂點vm重合,則稱這樣的路徑為回路或環(huán)。120312031203圖的基本概念A(yù)BECF路徑：A,B,C,F路徑長度：3同時它也是簡單路徑回路：A,E,C,F,A同時它也是簡單回路圖的基本概念圖的存儲結(jié)構(gòu)PART2圖的存儲結(jié)構(gòu)

A.Edge[i][j]=1，若<i,j>∈E或(i,j)∈E0，否則01鄰接矩陣（順序存儲）在圖的鄰接矩陣表示中，有一個記錄各個頂點信息的頂點表，還有一個表示各個頂點之間關(guān)系的鄰接矩陣。設(shè)圖A=(V,E)是一個有n個頂點的圖,圖的鄰接矩陣是一個二維數(shù)組A.edge[n][n]，定義：無向圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣可能是不對稱的。0123

鄰接矩陣120頂點表0123A.vexs=012B.vexs=圖的順序存儲圖的存儲結(jié)構(gòu)在無向圖的鄰接表中,

統(tǒng)計第i行(列)1的個數(shù)可得頂點I的度。在有向圖的鄰接表中,

統(tǒng)計第i行1的個數(shù)可得頂點i的出度，統(tǒng)計第j列1的個數(shù)可得頂點j的入度。

無向圖的鄰接矩陣有向圖的鄰接矩陣圖的存儲結(jié)構(gòu)182301632954網(wǎng)絡(luò)的鄰接矩陣

A.Edge[i][j]=W(i,j)，若i≠j且<i,j>∈E∞或0，若i≠j且<i,j>?E0，若i=j圖的存儲結(jié)構(gòu)#defineMaxVerNum100//最大結(jié)點數(shù)typedefintVertType;//結(jié)點類型typedefintEdgeType;

//邊的類型typedefstruct{intn;//頂點數(shù)VertTypevexs[MaxVerNum];//頂點結(jié)構(gòu)inte;//邊的個數(shù)EdgeTypeedges[MaxVerNum][MaxVerNum];//邊結(jié)構(gòu)}Mgraph;

鄰接矩陣表示法的存儲結(jié)構(gòu)定義建立有向圖G的鄰接矩陣存儲voidCreatGraph(MGraph*G)//建立有向圖G的鄰接矩陣存儲{inti，j，k，w；charch；

scanf(“%d，%d”，&(G->n)，&(G->e))；//輸入頂點數(shù)和邊數(shù)for(i=0；i<G->n；i++)scanf(“%d”，&(G->vexs[i]))；//輸入頂點信息，建立頂點表for(i=0；i<G->n；i++) for(j=0；j<G->n；j++)G->edges[i][j]=0；//初始化鄰接矩陣for(k=0；k<G->e；k++) {scanf(“%d，%d”，&i，&j)；//輸入e條邊，建立鄰接矩陣 G->edges[i][j]=1；//若加入G->edges[j][i]=1，則為無向圖的鄰接矩陣}}鄰接矩陣的特點無向圖的鄰接矩陣一定是一對稱矩陣無向圖的鄰接矩陣的第i行(或第i列)非零元素(或非∞元素)個數(shù)為第i個頂點的度D(vi)。有向圖的鄰接矩陣的第i行非零元素(或非∞元素)個數(shù)為第i個頂點的出度OD(vi)，第i列非零元素(或非∞元素)個數(shù)就是第i個頂點的入度ID(vi)。鄰接矩陣表示圖，很容易確定圖中任意兩個頂點之間是否有邊相連。由順序存儲的頂點表及n個鏈?zhǔn)酱鎯Φ倪呮湵韮刹糠纸M成鄰接表（圖的鏈?zhǔn)酱鎯Γ〢BCDABCD0123邊鏈表頂點表

13021002圖的存儲結(jié)構(gòu)頂點表：存放頂點本身的數(shù)據(jù)信息，表中每個表目對應(yīng)于圖的一個頂點，包括兩個字段：VerTex：頂點信息Firstedge：指向邊鏈表的第一個結(jié)點vertexFirstedge邊鏈表：存放邊的信息，鏈表中每個結(jié)點包括三個字段：Adjvex:存放與頂點vi相鄰接的頂點vj在頂點表中的位置Info:存放邊結(jié)點所代表的邊的權(quán)值（可選項）Next:指向邊鏈表的下一個邊結(jié)點adjvexinfonexttypedefstructnode//邊結(jié)點{intadjvex;//鄰接點域intinfo;//權(quán)值（可選）

structnode*next;//邊鏈表指針}EdgeNode;#defineMaxVertexNum100//最大頂點數(shù)typedefstructtnode{intvertex;

//頂點域

structnode*firstedge;//邊鏈表指針}VertexNode;//表結(jié)點typedefstruct{AdjListadjlist;//鄰接表intn,e;//頂點數(shù)和邊數(shù)}ALGraph;//鄰接表vertexFirstedge頂點表結(jié)點邊鏈表結(jié)點adjvexinfonextTypedefVertexNodeadjlist[MaxVertexNum];//頂點表無向圖的鄰接表的建立過程：BCADVertexfirstedgeABCD0123adjvexnext1

30

2

01.建立頂點信息（建頂點表）2.輸入邊信息，插入到邊鏈表中（建立邊鏈表）1

voidCreateALGraph(ALGraph*G)//建立有向圖的鄰接表存儲{inti，j，k；EdgeNode*p；

scanf(“%d，%d”，&(G->n)，&(G->e)；//讀入頂點數(shù)和邊數(shù)for(i=0；i<G->n；i++)//建立有n個頂點的頂點表{scanf(“%c”，&(G->adjlist[i].vertex))；//讀入頂點信息 G->adjlist[i].firstedge=nil；//頂點的邊表頭指針設(shè)為空}for(k=0；k<G->e；k++)/建立邊表 {scanf(“%d，%d”，&i，&j);//讀入邊<Vi，Vj>的頂點對應(yīng)序號 p=(EdgeNode*)malloc(sizeof(EdgeNode))；//生成新邊表結(jié)點p p->adjvex=j；//鄰接點序號為j p->next=G->adjlist[i].firstedge；//將邊結(jié)點插入到頂點Vi的鏈表頭部 G->adjlist[i].firstedge=p；

}}

建立有向圖的鄰接表算法：有向圖的鄰接表和逆鄰接表鄰接表(出邊表)ABCABC

1

02

逆鄰接表(入邊表)ABC1

0

1

鄰接表：對每個頂點vi將所有以頂點vi為弧尾（起始結(jié)點）的弧鏈接起來，形成出邊表，可以建立有向圖的鄰接表逆鄰接表：對每個頂點vi將所有以頂點vi為弧頭（終止結(jié)點）的弧鏈接起來，形成入邊表，可以建立有向圖的逆鄰接表網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表BACD69528(出邊鏈表)(頂點表)ABCD15012336

28

32

19

adjvexinfonext圖的遍歷PART3圖的遍歷02廣度優(yōu)先搜索BFS(BreadthFirstSearch)01深度優(yōu)先搜索DFS(DepthFirstSearch)兩種圖的遍歷方法深度優(yōu)先搜索DFS(DepthFirstSearch)1.從圖中某個頂點v出發(fā)，訪問v。2.找到剛訪問過的頂點的第一個未被訪問的鄰接點，訪問該頂點。以該頂點為新頂點，重復(fù)此步驟，直至剛訪問的頂點沒有未被訪問的鄰接點為止。3.返回前一個訪問過得且仍有未被訪問的鄰接點的頂點，找到該頂點的下一個未被訪問的鄰接點，訪問該頂點。4.重復(fù)步驟2，3，直至圖中所有頂點都被訪問過。深度優(yōu)先搜索可以用堆棧來實現(xiàn)深度優(yōu)先搜索過程可用堆棧來實現(xiàn)69AEDFCBGIH123457878前進(jìn)回退深度優(yōu)先訪問順序：69AEDFCBGIH12345A棧底DEGCFBHI圖的遍歷廣度優(yōu)先搜索BFS(BreadthFirstSearch)1.從圖中某個頂點v出發(fā)，訪問v。2.依次訪問v的各個未被訪問過得鄰接點。3.分別從這些鄰接點出發(fā)依次訪問他們的鄰接點4.重復(fù)步驟3，直至圖中所有的頂點都被訪問到。廣度優(yōu)先搜索可以用隊列來實現(xiàn)廣度優(yōu)先搜索BFS——類似于樹的按層遍歷AEDFCBGIH123456789AEDFCBGIH123456789ABCDEFGHIABCDEFGHI訪問順序：隊尾廣度優(yōu)先生成樹圖的應(yīng)用PART401020403拓?fù)渑判蚪鉀Q工程實踐中的活動步驟問題最小生成樹解決工程實踐中的最小代價問題最短路徑解決2點之間的最短距離問題關(guān)鍵路徑解決工程實踐中的最短工期問題圖的應(yīng)用最小生成樹的相關(guān)概念最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路徑生成樹連通圖的生成樹是一個極小連通子圖，它包含圖中所有頂點，但只有足以構(gòu)成一棵樹的n-1條邊最小生成樹問題該問題是構(gòu)造連通圖的最小代價生成樹問題連通圖無向圖中，如果任意兩個頂點之間都能夠連通，則稱此無向圖為連通圖代價一棵生成樹的代價就是樹上各邊（?。┑拇鷥r（權(quán)值）之和）最小生成樹是帶權(quán)圖例如，若要在n個城市間建立通信聯(lián)絡(luò)網(wǎng)，則只需n-1條線路。但在n個城市間，最多可能架設(shè)n（n-1）/2條線路，選擇哪n-1條線路，使費用最少。123456872135689最小生成樹12345687214357681110912連通圖普里姆算法克魯斯卡爾算法最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路徑普里姆（Prim）算法假設(shè)N=（V，E）是連通圖，TE是N上最小生成樹中邊的集合。從U={u0}（u0

V），TE=空開始；重復(fù)執(zhí)行：在所有uU，vV-U的邊(u,v)

E中找一條代價最小的邊(u0，v0)并入TE，同時u0并入U，直到U=V為止；此時TE中必有n-1條邊，則T=（V，TE）為N的最小生成樹。最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路徑普里姆（Prim）算法12345687214357681110912123456872135689(1)U={1,2},V-U={3,4,5,6,7,8}初始狀態(tài)：U={1},V-U={2,3,4,5,6,7,8}(4)U={1,2,4,7,5},V-U={3,6,8}(2)U={1,2,4},V-U={3,5,6,7,8}(3)U={1,2,4,7},V-U={3,5,6,8}(5)U={1,2,4,7,5,6},V-U={3,8}(6)U={1,2,4,7,5,6,3},V-U={8}(7)U={1,2,4,7,5,6,3,8},V-U={}最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路徑克魯斯卡爾（Kruskal）算法假設(shè)N=（V，E）是連通圖取圖中每個頂點自成一個連通分量在{E}中選擇代價最小的邊，若該邊所依附的頂點落在T中不同的連通分量上，則將此邊加入生成樹T中；否則，舍去此邊，再選擇下一條代價最小的邊。重復(fù)上述步，直到T中所有頂點都在同一連通分量上為止。最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路徑克魯斯卡爾（Kruskal）算法12345687214357681110912123456872135689(1){1},{2,4},{3},{5},{6},{7},{8}初始狀態(tài)：{1},{2},{3},{4},{5},{6},{7},{8}(4){1,2,4,5,7},{3},{6},{8}(2){1,2,4},{3},{5},{6},{7},{8}(3){1,2,4,7},{3},{5},{6},{8}(5){1,2,4,5,6,7},{3},{8}(6){1,2,3,4,5,6,7},{8}(7){1,2,3,4,5,6,7,8}最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路徑AOV網(wǎng)與拓?fù)渑判駻OV網(wǎng)：用頂點表示活動，用弧表示活動間優(yōu)先關(guān)系的有向圖稱為頂點表示活動的網(wǎng)。計劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個叫做“活動”的子工程。完成了這些活動，這個工程就可以完成了。在AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路,即有向環(huán)。因此，對給定的AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路徑最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路徑課程代碼課程名稱先修課程C1高等數(shù)學(xué)C2程序設(shè)計基礎(chǔ)C3離散數(shù)學(xué)C1，C2C4數(shù)據(jù)結(jié)構(gòu)C3，C2C5高級語言程序設(shè)計C2C6編譯方法C5，C4C7操作系統(tǒng)C4，C9C8普通物理C1C9計算機原理C8學(xué)生課程學(xué)習(xí)工程圖

檢測有向環(huán)的一種方法是對該AOV網(wǎng)絡(luò)的各個結(jié)點(活動)進(jìn)行拓?fù)渑判颉?/p>

拓?fù)渑判颍簩⒏鱾€頂點(代表各個活動)排列成一個線性有序的序列，使得AOV網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿足。如果通過拓?fù)渑判蚰軐OV網(wǎng)絡(luò)的所有頂點都排入一個拓?fù)溆行虻男蛄兄?則該網(wǎng)絡(luò)中必定不會出現(xiàn)有向環(huán)。如果AOV網(wǎng)絡(luò)中存在有向環(huán)，此AOV網(wǎng)絡(luò)所代表的工程是不可行的。最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路徑拓?fù)渑判蛩惴á僭贏OV網(wǎng)絡(luò)中選一個沒有直接前驅(qū)的頂點,并輸出之;②

從圖中刪去該頂點,同時刪去它發(fā)出的所有有向邊;③重復(fù)以上①、②步,直到全部頂點均已輸出，拓?fù)溆行蛐蛄行纬?，拓?fù)渑判蛲瓿桑换?圖中還有未輸出的頂點,但已跳出處理循環(huán)。說明圖中還剩下一些頂點,它們都有直接前驅(qū)。這時網(wǎng)絡(luò)中必存在有向環(huán)。最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路徑例如,對上述學(xué)生選課工程圖C8C3C5C4C9C6C7C1C2對其進(jìn)行拓?fù)渑判?還可得其它拓?fù)湫蛄腥纾?/p>

C2,C5,C1,C8,C9,C3,C4,C7,C6拓?fù)渑判颍篊8C3C5C4C9C6C7C1C2最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路徑C0C1C2C3C4C5拓?fù)渑判虻倪^程(a)有向無環(huán)圖C0C2C5C1C3(b)輸出頂點C4后C1C2C5C3(c)輸出頂點C0后C4C0C2C5C1C3(d)輸出頂點C3后拓?fù)湫蛄校篊2最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路徑C1C5(e)輸出頂點C2后C5C1(f)輸出頂點C1后C5(g)輸出頂點C5后本拓?fù)湫蛄谐怂鼭M足圖中給出的所有前驅(qū)和后繼關(guān)系，對于本來沒有這種關(guān)系的頂點，如C4和C2，也排出了先后次序關(guān)系。C4C0C3拓?fù)湫蛄校篊2拓?fù)渑判虻倪^程最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路徑AOE網(wǎng)絡(luò)：用邊表示活動的網(wǎng)絡(luò)如果在帶權(quán)有向無環(huán)圖中,用有向邊表示一個工程中的活動，用邊上權(quán)值表示活動持續(xù)時間，用頂點表示事件，則這樣的有向圖叫做用邊表示活動的網(wǎng)絡(luò),簡稱AOE網(wǎng)絡(luò)。最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路徑問：完成整個工程至少需要多少時間？為縮短完成工程所需的時間,應(yīng)當(dāng)加快哪些活動?<1,3><3,4>那些活動不能耽誤，必須按時完成？

<1,3><3,4>

AOE網(wǎng)絡(luò)在某些工程估算方面非常有用。例如：132481291022天源點→←匯點←關(guān)鍵路徑最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路徑從源點到匯點的有向路徑可能不止一條。這些路徑的長度也可能不同,但只有各條路徑上所有活動都完成了,整個工程才算完成。因此,完成整個工程所需的時間取決于從源點到匯點的最長路徑長度,這條路徑長度最長的路徑就叫做關(guān)鍵路徑(CriticalPath)。要找出關(guān)鍵路徑，必須找出關(guān)鍵活動,即不按期完成就會影響整個工程進(jìn)度的活動。最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路徑求關(guān)鍵路徑步驟求Ve(i):事件Vi的最早發(fā)生時間：從始點到vi的最長（加權(quán)）路徑長度求Vl(i):事件Vi的最遲發(fā)生時間：在不拖延整個工期的條件下，vi的可能的最晚發(fā)生時間。求e(i):活動ai的最早開始時間：活動的起點的最早發(fā)生時間求l(i):活動ai的最遲開始時間：在不拖延整個工期的條件下，活動起點的可能的最晚發(fā)生時間。l(i)-e(i):完成活動ai的時間余量最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路徑12346791058a1=8a3=7a4=3a6=9a8=13a9=4a11=8a7=9a12=6a13=14a2=6a5=10a10=19a14=1012345678910VeVl086167201620ai12345678910111213