數(shù)據(jù)結(jié)構(gòu)第九章圖

數(shù)據(jù)結(jié)構(gòu)第九章圖第1頁，課件共43頁，創(chuàng)作于2023年2月圖的基本概念圖(Graph)

圖是由頂點(diǎn)集合(vertex)及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：

Graph＝(V,E)

其中:V={x|x某個(gè)數(shù)據(jù)對(duì)象}是頂點(diǎn)的有窮非空集合；

E={(x,y)|x,y

V}

或

E={<x,y>|x,y

V}是頂點(diǎn)之間關(guān)系的有窮集合。125634abcd無向圖有向圖V={1,2,3,4}E={(1,2),(1,5),(1,6),(2,3),(2,4),(3,4),(4,5),(4,6)}（邊）V={a,b,c,d}E={<a,b>,<a,d>,<b,d>,<c,a>,<d,a>,<d,b>,

<d,c>}（?。?lt;弧尾頂點(diǎn)，弧頭頂點(diǎn)>第2頁，課件共43頁，創(chuàng)作于2023年2月ADTGraph{數(shù)據(jù)對(duì)象:

D={ai|1in,n0,ai屬Elemtype類型

數(shù)據(jù)關(guān)系:R1={<ai,aj>|ai,aj

D,1in,1jn,

每個(gè)元素可以有多個(gè)直接前驅(qū)和可以有多個(gè)直接后繼}

基本運(yùn)算:InitGraph(t);ClearGraph(t);DSF(t);BSF(t);

}抽象數(shù)據(jù)類型數(shù)的定義第3頁，課件共43頁，創(chuàng)作于2023年2月完全圖

若有

n個(gè)頂點(diǎn)的無向圖有n(n-1)/2條邊,則此圖為完全無向圖。有

n個(gè)頂點(diǎn)的有向圖有n(n-1)條邊,則此圖為完全有向圖。abc1234鄰接頂點(diǎn)

如果(u,v)是E(G)中的一條邊，則稱u與v互為鄰接頂點(diǎn)。例：存在(1,2)，則頂點(diǎn)1與2互為鄰接點(diǎn)。存在<a,b>,則頂點(diǎn)a與b互為鄰接點(diǎn)。第4頁，課件共43頁，創(chuàng)作于2023年2月125634abcd頂點(diǎn)的度

一個(gè)頂點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(v)。在有向圖中,頂點(diǎn)的度=入度+出度。頂點(diǎn)v的入度

是以v為終點(diǎn)的有向邊的條數(shù),記作

ID(v);頂點(diǎn)v的出度

是以v為始點(diǎn)的有向邊的條數(shù),記作

OD(v)。TD(v)=ID(v)+OD(v)例：TD(1)=3TD(4)=4TD(5)=2例：TD(b)=ID(b)+OD(b)TD(d)=ID(d)+OD(d)=2+1=3=2+3=5第5頁，課件共43頁，創(chuàng)作于2023年2月子圖

設(shè)有兩個(gè)圖G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,則稱圖G’是圖G的子圖。0123子圖0130123023權(quán)

某些圖的邊具有與它相關(guān)的數(shù),稱為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)。任意圖都是其自身子圖abcd8

19341123第6頁，課件共43頁，創(chuàng)作于2023年2月路徑

在圖G＝(V,E)中,若從頂點(diǎn)vi出發(fā),沿一些邊經(jīng)過一些頂點(diǎn)

vp1,vp2,…,

vpm，到達(dá)頂點(diǎn)vj。則稱頂點(diǎn)序列

(vi

vp1vp2...vpm

vj)

為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。125634例：V1到V3的路徑：123、123423、16423、1544……..路徑長(zhǎng)度

非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和。簡(jiǎn)單路徑

若路徑上各頂點(diǎn)v1,v2,...,vm均不互相重復(fù),則稱這樣的路徑為簡(jiǎn)單路徑?；芈?/p>

若路徑上第一個(gè)頂點(diǎn)v1與最后一個(gè)頂點(diǎn)vm重合,則稱這樣的路徑為回路或環(huán)。

路徑長(zhǎng)度：

2、5、4、3……..第7頁，課件共43頁，創(chuàng)作于2023年2月連通圖與連通分量

在無向圖中,若從頂點(diǎn)v1到頂點(diǎn)v2有路徑,

則稱頂點(diǎn)v1與v2是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的,

則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。生成樹一個(gè)連通圖的生成樹是其極小連通子圖。n個(gè)頂點(diǎn)、n-1條邊、連通子圖。12563441532連通圖非連通圖兩個(gè)連通分量125634125634第8頁，課件共43頁，創(chuàng)作于2023年2月強(qiáng)連通圖與強(qiáng)連通分量

在有向圖中,

若對(duì)于每一對(duì)頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。abcd

abcd

強(qiáng)連通圖非強(qiáng)連通圖cabd

兩個(gè)強(qiáng)連通分量第9頁，課件共43頁，創(chuàng)作于2023年2月圖的存儲(chǔ)表示鄰接矩陣(AdjacencyMatrix)aij=abefcdvexs123456abcdefA=010011101100010100011011100100100100利用數(shù)組vertex[]存儲(chǔ)頂點(diǎn)基本思想：利用矩陣A表示頂點(diǎn)之間的關(guān)系無向圖的鄰接矩陣是對(duì)稱矩陣第10頁，課件共43頁，創(chuàng)作于2023年2月aij=A=abcd8

19341123vexs1234A=abcd1111111000000000A=abefcdvexs123456abcdef482196

731084931112341984198262633107107A=010011101100010100011011100100100100鄰接矩陣所占存儲(chǔ)空間與頂點(diǎn)數(shù)成正比但圖中有無關(guān)系都分配存儲(chǔ)空間邊的插入和刪除不影響存儲(chǔ)空間大小0100？求頂點(diǎn)的度第11頁，課件共43頁，創(chuàng)作于2023年2月鄰接矩陣的數(shù)據(jù)類型A=vexs1234Typedefenum{DG,DN,UDG,UDN}Graphkind;typedefstructArcCell{VRTypeadj;/*各頂點(diǎn)之間的關(guān)系或權(quán)值*/InfoType*info;}ArcCell,AdjMatrix[MAXV][MAXV];typedefstruct{VertexTypevexs[MAXV];/*存儲(chǔ)頂點(diǎn)元素*/AdjMatrixarcs;intvexnum,arcnum;/*頂點(diǎn)數(shù)，弧數(shù)*/Graphkindkind;}Mgraph;第12頁，課件共43頁，創(chuàng)作于2023年2月建立鄰接矩陣*鄰接矩陣初始化（置0或）*輸入頂點(diǎn)數(shù)，弧數(shù)ga->vexnumga->arcnum*輸入各頂點(diǎn)信息存入ga->vexs[]*輸入各邊信息（或權(quán)值）存入ga->arcsarcsvexs1234第13頁，課件共43頁，創(chuàng)作于2023年2月鄰接表(AdjacencyList)基本思想：在無向圖中，將依附于某個(gè)頂點(diǎn)的所有邊（邊結(jié)點(diǎn)）以單鏈表形式鏈接，每個(gè)鏈表設(shè)立一個(gè)表頭結(jié)點(diǎn)。abefcd123456abcdef(a,b)(a,e)(a,f)256(b,a)(b,c)(b,d)134(c,b)(c,d)24(d,b)(d,c)(d,e)(d,f)2356(e,a)(e,d)(f,a)(f,d)1414datafirstarc4

82196

73

10481987426adjvexinfonextarc36107231910adjvexnextarc注：在無向圖中每個(gè)邊生成兩個(gè)結(jié)點(diǎn)？插入和刪除(d,f)=(f,d)?求頂點(diǎn)的度第14頁，課件共43頁，創(chuàng)作于2023年2月datafirstarc1234abcd8

59371113鄰接表：在有向圖中，將以該頂點(diǎn)作為弧尾頂點(diǎn)的所有弧鏈接成單鏈表。abcd<a,b><a,d>2847<b,d>49<c,a>13<d,a><d,b><d,c>15211313datafirstarc1234abcd<c,a><d,a>3345<a,b><d,b><d,c>413<a,d><b,d>184111749逆鄰接表逆鄰接表：在有向圖中，將以該頂點(diǎn)作為弧頭頂點(diǎn)的所有弧鏈接成單鏈表。？求頂點(diǎn)的度第15頁，課件共43頁，創(chuàng)作于2023年2月鄰接表的結(jié)點(diǎn)結(jié)構(gòu)和數(shù)據(jù)類型datafirstarc表頭結(jié)點(diǎn)typedefstructArcNode{intadjvex;/*鄰接點(diǎn)存儲(chǔ)序號(hào)*/

infoTypeinfo;/*若是網(wǎng)絡(luò)存儲(chǔ)權(quán)值*/

structArcNode*nextarc;/*指向下一個(gè)邊結(jié)點(diǎn)*/}ArcNode;typedefstruct{Vertexdata;/*存儲(chǔ)頂點(diǎn)元素*/

Arcnode*firstarc;/*指向依附于該頂點(diǎn)的第一邊*/}VNode,AdjList[MAXV];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;}ALGraph;adjvexnextarc邊結(jié)點(diǎn)adjvexinfonextarc第16頁，課件共43頁，創(chuàng)作于2023年2月datafirstarcadjvexinfonextarc123456abcdef256134242356141448198742636107231910abefcd4

82196

73

10建立鄰接表*鄰接表初始化（置各單鏈表為空表ga[].firstarc=NULL）*輸入各頂點(diǎn)信息存入

ga[].data*輸入各邊信息，生成新結(jié)點(diǎn)，插入相應(yīng)的單鏈中。第17頁，課件共43頁，創(chuàng)作于2023年2月abcd8

59371113datafirstarc1234abcd2847491315211313鄰接表的基本操作插入：

<b,c>*確定單鏈表*生成新結(jié)點(diǎn)636*頭插鏈表注：有向圖只插入(或刪除）一個(gè)結(jié)點(diǎn)，而無向圖需插入（或刪除）兩個(gè)結(jié)點(diǎn)。刪除：

<d,c>*確定結(jié)點(diǎn)*刪除結(jié)點(diǎn)*釋放結(jié)點(diǎn)<c,a>第18頁，課件共43頁，創(chuàng)作于2023年2月十字鏈表(有向圖)abcd8

59371113a

a

a

b

a

c

a

d

a

12

<a,b>a

14<a,d>a

24

<b,d>a

31

<c,a>a

41

<d,a>a

42

<d,b>a

43

<d,c>tailvexheadvexhlinktlinkinfo弧結(jié)點(diǎn)datafirstinfirstout頂點(diǎn)結(jié)點(diǎn)第19頁，課件共43頁，創(chuàng)作于2023年2月a

46(d,f)abefcd4

82196

73

10ABCDEFa

12(a,b)a

15(a,e)a

16(a,f)a

23(b,c)a

24(b,d)a

34(c,d)a

45(d,e)鄰接多重表（無向圖）markivexilinkjvexjlink邊結(jié)點(diǎn)datafirstedge頂點(diǎn)結(jié)點(diǎn)第20頁，課件共43頁，創(chuàng)作于2023年2月圖的遍歷(GraphTraversal)圖的遍歷從圖中某一頂點(diǎn)出發(fā)，沿著一些邊訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次。為了避免重復(fù)訪問，設(shè)置一個(gè)的輔助數(shù)組visited[]標(biāo)志各頂點(diǎn)是否被訪問過。圖的遍歷的分類：深度優(yōu)先搜索

DFS(DepthFirstSearch)廣度優(yōu)先搜索

BFS(BreadthFirstSearch)第21頁，課件共43頁，創(chuàng)作于2023年2月12563478深度優(yōu)先搜索DFS(DepthFirstSearch)visited12345678DFS基本思想：*訪問頂點(diǎn)v0。*依次從v0未被訪問的鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。遍歷序列：1231256414521426264545262653178177383883733780000000011111111注：訪問v0的鄰接點(diǎn)與訪問v0方法一樣，用遞歸方式實(shí)現(xiàn)。12563478DFS(v0)的主要步驟：(1)訪問頂點(diǎn)v0(2)確定第一鄰接點(diǎn)w(3)若w未訪問，則從w出發(fā)進(jìn)行遍歷DFS(w)(4)確定下一個(gè)鄰接點(diǎn)w(5)重復(fù)(3)(4)直到所有鄰接點(diǎn)都處理結(jié)束

第22頁，課件共43頁，創(chuàng)作于2023年2月DFS(v0)的主要步驟：(1)訪問頂點(diǎn)v0(2)確定第一鄰接點(diǎn)w(3)若w未訪問，則從w出發(fā)進(jìn)行遍歷DFS(w)(4)確定下一個(gè)鄰接點(diǎn)w(5)重復(fù)(3)(4)直到所有鄰接點(diǎn)都處理結(jié)束深度優(yōu)先搜索DFS(DepthFirstSearch)DFS(v0){visite(v0);visited[v0]=1;w=FIRST(v0);while(存在w){if(visited[v0]==0)DFS(w);w=NEXT(v0,w);}}

第23頁，課件共43頁，創(chuàng)作于2023年2月125634datafirstarc123456abcdef5623142435624114DFS(v0){visite(v0);visited[v0]=1;w=FIRST(v0);while(存在w){if(visited[v0]==0)DFS(w);w=NEXT(v0,w);}}

第一鄰接點(diǎn):p=ga[v0].firstarc下一個(gè)鄰接點(diǎn)：p=p->nextarc第24頁，課件共43頁，創(chuàng)作于2023年2月廣度優(yōu)先搜索BFS(BreadthFirstSearch)12563478BFS基本思想：*訪問頂點(diǎn)v0。*依次訪問v0未被訪問的鄰接點(diǎn)*依次從這些鄰接點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索遍歷。注：為了從已訪問的鄰接點(diǎn)出發(fā)，設(shè)置隊(duì)列保存結(jié)點(diǎn)visited12345678遍歷序列：123457861222333444555777888隊(duì)列00000000666111111111112563478第25頁，課件共43頁，創(chuàng)作于2023年2月BFS(v0)的主要步驟：(1)訪問頂點(diǎn)v0(2)頂點(diǎn)v0入隊(duì)列(3)取出隊(duì)頭v<1>確定第一鄰接點(diǎn)w<2>若w未訪問，則訪問w，w入隊(duì)列。<3>確定下一個(gè)鄰接點(diǎn)w<4>重復(fù)<2><3>直到所有鄰接點(diǎn)都處理(4)重復(fù)(3)直到隊(duì)列空。廣度優(yōu)先搜索BFS(BreadthFirstSearch)BFS(v0){init(Q);visite(v0);visited[v0]=1;enqueue(Q,v0);while(!empty(Q)){v=dequeue(Q);w=FIRST(v);while(存在w){if(visited[w]==0){visite(w);visited[w]=1;enqueue(Q,w);}w=NEXT(v,w);}}}第26頁，課件共43頁，創(chuàng)作于2023年2月BFS(v0){init(Q);visite(v0);visited[v0]=1;enqueue(Q,v0);while(!empty(Q)){v=dequeue(Q);w=FIRST(v);while(存在w){if(visited[w]==0){visite(w);visited[w]=1;enqueue(Q,w);}w=NEXT(v,w);}}}125634datafirstarc123456abcdef5623142435624114第一鄰接點(diǎn):p=ga[v0].firstarc下一個(gè)鄰接點(diǎn)：p=p->nextarc第27頁，課件共43頁，創(chuàng)作于2023年2月深度優(yōu)先搜索DFS

(DepthFirstSearch)深度優(yōu)先搜索過程的示例ACDEGBFIHACDEGBFIH123456791234567889深度優(yōu)先搜索過程

深度優(yōu)先生成樹前進(jìn)回退第28頁，課件共43頁，創(chuàng)作于2023年2月廣度優(yōu)先搜索BFS

(BreadthFirstSearch

)廣度優(yōu)先搜索的示例ACDEGBFIH123456789123456789廣度優(yōu)先搜索過程ACDEGBFHI廣度優(yōu)先生成樹第29頁，課件共43頁，創(chuàng)作于2023年2月

問題：當(dāng)對(duì)非連通圖遍歷時(shí),從圖中某一頂點(diǎn)出發(fā),利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點(diǎn),只能訪問到該頂點(diǎn)所在的最大連通子圖(連通分量)的所有頂點(diǎn)。ACDEBFGIHJONMLK非連通無向圖要實(shí)現(xiàn)任意圖的遍歷，則要掃描圖中的所有頂點(diǎn)。TRQVER(){for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]=0)DFS(vi);}TRQVER(){for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]=0)BFS(vi);}第30頁，課件共43頁，創(chuàng)作于2023年2月ACDEBFGIHJONMLK非連通無向圖ACDEBFGHIJKONML非連通圖的連通分量對(duì)于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林。第31頁，課件共43頁，創(chuàng)作于2023年2月ACDEBFGIHJONMLK非連通無向圖ACDEBFGIHJONMLK非連通圖的連通分量第32頁，課件共43頁，創(chuàng)作于2023年2月1624351624351624351251042312104312542深度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷遍歷序列:123456遍歷序列:125634連通圖生成樹不同的遍歷得到不同的生成樹權(quán)值之和:20權(quán)值之和:14第33頁，課件共43頁，創(chuàng)作于2023年2月最小生成樹

(minimumcostspanningtree)最小生成樹----在一個(gè)連通網(wǎng)得到的所有生成樹中,權(quán)值之和最小的生成樹稱為最小生成樹.3564257156146352使用且僅使用該網(wǎng)絡(luò)中的n-1條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的n個(gè)必須頂點(diǎn)；不能使用產(chǎn)生回路的邊；各邊上的權(quán)值的總和達(dá)到最小。應(yīng)用:在若干個(gè)城市中建立通訊網(wǎng)。第34頁，課件共43頁，創(chuàng)作于2023年2月MST性質(zhì)：設(shè)G=（V,E）是一個(gè)連通網(wǎng)絡(luò)，U是頂點(diǎn)集V的一個(gè)子集。若（u,v）是G中所有的一個(gè)端點(diǎn)在U（即uU）里，另一個(gè)端點(diǎn)不在U（即vV-U）里的邊中，具有最小權(quán)值的一條邊，則一定存在G的一棵最小生成樹包含此邊（u,v）。UV-U反正法證明：假設(shè)G中任何一棵最小生成樹中都不包含邊（u,v）。v’u’vu設(shè)T是一棵最小生成樹，不包（u,v）,一定要包含一條邊（u’,v’）。若用（u,v）取代（u’,v’）得到一棵新的生成樹T’,由于W（u,v）<W（u,v），則T’的權(quán)<T的權(quán)，與假設(shè)矛盾。第35頁，課件共43頁，創(chuàng)作于2023年2月535642571561463525461356242361657756643255普里姆(Prim)算法基本思想：

設(shè)連通網(wǎng)絡(luò)N=(V,E)，最小生成樹T=(U,TE)（1）初始狀態(tài)：U={v0},TE=。（2）選擇滿足MST性質(zhì)的一條邊（u,v）,其中uU，vV-U，且邊（u,v）的權(quán)值最小。（3）吸收vU,吸收（u,v）TE。（4）重復(fù)（2）（3），直到U=V。第36頁，課件共43頁，創(chuàng)作于2023年2月553512461423606577556321435642571560352410615

6053150754570

235

06

4260cost[][]lowcostclosest0615

00000

0最小5540最小222最小最小2050034012345cost[][]:利用鄰接矩陣法存儲(chǔ)圖i=j:cost[i][j]=0closest[]和lowcost[]分別存儲(chǔ)頂點(diǎn)序號(hào)和權(quán)值，當(dāng)lowcost[i]=0:頂點(diǎn)i已經(jīng)吸收到U。當(dāng)lowcost[i]0:頂點(diǎn)i未被吸收V-U。當(dāng)0<lowcost[i]<：存儲(chǔ)頂點(diǎn)i與頂點(diǎn)closest[i]之間的權(quán)值。當(dāng)lowcost[i]=：

頂點(diǎn)i未與已吸收的頂點(diǎn)之間沒有關(guān)系（邊）。第37頁，課件共43頁，創(chuàng)作于2023年2月prim(cost[][],n,v){for(i=0;i<n;i++){lowcost[i]=cost[v][i];closest[i]=v;}for(i=1;i<n;i++){min=;for(j=0;j<n;j++)if(lowcost[j]!=0&&lowcost[j]<min) {min=lowcost[j];k=j;}輸出(closest[k],k,min);lowcost[k]=0;for(j=0;j<n;j++) if(lowcost[j]!=0&&cost[k][j]<lowcost[j]) {lowcost[j]=cost[k][j];closest[j]=k;}}}第38頁，課件共43頁，創(chuàng)作于2023年2月3564257156146352克魯斯卡爾(Kruskal)算法基本思想：設(shè)有有n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)

N={V,E

},最初先構(gòu)造一個(gè)只有n個(gè)頂點(diǎn),沒有邊的非連通圖

T={V,

},圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。當(dāng)在E中選到一條具有最小權(quán)值的邊時(shí),若該邊的兩個(gè)頂點(diǎn)落在不同的連通分量上，則將此邊加入到T中;否則將此邊舍去，重新選擇一條權(quán)值最小的邊。如此重復(fù)下去,直到所有頂點(diǎn)在同一個(gè)連通分量上為止。54613212345回路第39頁，課件共43頁，創(chuàng)作于2023年2月最短路徑(ShortestPath)最短路徑問題：從圖中某一頂點(diǎn)(稱為源點(diǎn))到達(dá)另一頂點(diǎn)(稱為終點(diǎn))的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小。問題解法:邊上權(quán)值非負(fù)情形的單源最短路徑問題—

Dijkstra算法邊上權(quán)值為任意值的單源最短路徑問題—Bellman和Ford算法所有頂點(diǎn)之間的最短路徑—Floyd算法746132573611101422第40頁，課件共43頁，創(chuàng)作于2023年2月11107461325736111014227221.2--101.3--2arrive