數(shù)據(jù)結(jié)構(gòu)第7章圖圖的定義和術(shù)語ppt課件

1、武漢科技大學(xué)Wuhan University of Science and Technology張 凱計(jì)算機(jī)學(xué)院 軟件工程系2021年3月12日;圖的連通性問題第第7 7章章 圖圖圖的定義和術(shù)語圖的存儲構(gòu)造圖的遍歷有向無環(huán)圖及其運(yùn)用最短途徑;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語有向圖：圖G中的每條邊都是有方向的；;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語無向圖：圖G中的每條邊都是無方向的;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語完全圖：圖G恣意兩個(gè)頂點(diǎn)都有一條邊相銜接；假設(shè)n個(gè)頂點(diǎn)的無向圖有n(n-1)/2條邊, 稱為無向完全圖;v根本術(shù)語根本術(shù)語

2、7.1 圖的定義和術(shù)語圖的定義和術(shù)語完全圖：圖G恣意兩個(gè)頂點(diǎn)都有一條邊相銜接；假設(shè)n個(gè)頂點(diǎn)的有向圖有n(n-1)條邊, 稱為有向完全圖;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語稀疏圖：稠密圖： 邊較少的圖。通常邊數(shù)e小于nlogn邊很多的圖。通常邊數(shù)e大于nlogn;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語設(shè)有兩個(gè)圖 G(V, E) 和 G(V, E)。假設(shè) V V 且 E E, 那么稱 圖G 是 圖G 的子圖。子 圖：G;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語設(shè)有兩個(gè)圖 G(V, E) 和 G(V, E)。假設(shè) V V 且 E E, 那么稱 圖G

3、是 圖G 的子圖。子 圖：G;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語帶權(quán)圖：即邊上帶權(quán)的圖。其中權(quán)是指每條邊可以標(biāo)上具有某種含義的數(shù)值即與邊相關(guān)的數(shù)。帶權(quán)圖網(wǎng) 絡(luò)：;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語途徑： 在圖 G(V, E) 中, 假設(shè)從頂點(diǎn)vi出發(fā), 沿一些邊經(jīng)過一些頂點(diǎn)vp1, vp2, , vpm，到達(dá)頂點(diǎn)vj。那么稱頂點(diǎn)序列( vi vp1 vp2 . vpm vj ) 為從頂點(diǎn)vi到頂點(diǎn)vj的途徑。它經(jīng)過的邊(vi, vp1)、(vp1, vp2)、.、(vpm, vj)該當(dāng)是屬于E的邊。V1V2V3V4V5V6V1V2V3V4V5V6;v根本

4、術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語途徑長度：非帶權(quán)圖的途徑長度是指此途徑上邊的條數(shù)；帶權(quán)圖的途徑長度是指途徑上各邊的權(quán)之和。V1V2V3V4V5V62317812;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語簡單途徑：途徑上各頂點(diǎn) v1,v2,.,vm 均不相互反復(fù)?；?路：假設(shè)途徑上第一個(gè)頂點(diǎn) v1 與最后一個(gè)頂點(diǎn)vm 重合，那么稱這樣的途徑為回路或環(huán)。V1V2V3V4V5V6V1V2V3V4V5V6(a)簡單途徑(b)非簡單途徑;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語簡單途徑：途徑上各頂點(diǎn) v1,v2,.,vm 均不相互反復(fù)。回 路：假設(shè)途徑上第一個(gè)

5、頂點(diǎn) v1 與最后一個(gè)頂點(diǎn)vm 重合，那么稱這樣的途徑為回路或環(huán)。V1V2V3V4V5V6(c)回路;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語連通圖： 在無向圖中, 假設(shè)從頂點(diǎn)v1到頂點(diǎn)v2有途徑, 那么稱頂點(diǎn)v1與v2是連通的。假設(shè)圖中恣意一對頂點(diǎn)都是連通的, 那么稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。在有向圖中, 假設(shè)對于每一對頂點(diǎn)vi和vj, 都存在一條從vi到vj和從vj到vi的途徑, 那么稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。強(qiáng)連通圖：;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語連通圖;v根本術(shù)語根本術(shù)語7.1 圖的定義和

6、術(shù)語圖的定義和術(shù)語非連通圖三個(gè)連通分量;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語強(qiáng)連通圖;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語非強(qiáng)連通圖兩個(gè)強(qiáng)連通分量;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語鄰接點(diǎn) 對于無向圖G=(V, E)，假設(shè)邊(v, v)E，那么稱頂點(diǎn) v 和 v 互為鄰接點(diǎn)，即 v 和 v 相鄰接?；蚍Q邊 (v, v ) 依靠于頂點(diǎn)v 和 v，或稱(v, v)和頂點(diǎn) v 和 v 相關(guān)聯(lián)。 ;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)

7、語圖的定義和術(shù)語鄰接點(diǎn) 對于有向圖G=(V，E)，假設(shè)弧 E，那么稱頂點(diǎn) v 鄰接到頂點(diǎn) v，或稱頂點(diǎn) v 鄰接自頂點(diǎn) v ，或弧和頂點(diǎn) v, v 相關(guān)聯(lián)。;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語頂點(diǎn)v的入度/出度 以頂點(diǎn) v 為終點(diǎn)有向邊的條數(shù)稱 v 的入度，記為ID(v)； 以頂點(diǎn) v 為起點(diǎn)有向邊的條數(shù)稱 v 的出度，記為OD(v)。 頂點(diǎn) v 的度 TD(v) = ID(v) OD(v)頂點(diǎn)v的度(Degree)是和v相關(guān)聯(lián)的邊的數(shù)目，記為 TD(v);v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語 一個(gè)連通圖的生成樹是一個(gè)極小連通子圖，它含有圖中全部頂點(diǎn)，但只

8、需足以構(gòu)成一棵樹的n-1條邊。 假設(shè)在一棵生成樹上添加一條邊，必定構(gòu)成一個(gè)環(huán)，由于這條邊使得它依靠的那兩個(gè)頂點(diǎn)之間有了第二條途徑。生成樹V1V4V6V5V2V3156554636215432V1V3V5V2V4V6;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語 假設(shè)一個(gè)有向圖恰有一個(gè)頂點(diǎn)的入度為 0，其他頂點(diǎn)的入度均為 1，那么是一棵有向樹。一個(gè)有向圖的生成森林由假設(shè)干棵有向樹組成，含有圖中全部頂點(diǎn)，但只需足以構(gòu)成假設(shè)干棵不相交的有向樹的弧。生成森林;v根本術(shù)語根本術(shù)語7.1 圖的定義和術(shù)語圖的定義和術(shù)語 假設(shè)一個(gè)有向圖恰有一個(gè)頂點(diǎn)的入度為 0，其他頂點(diǎn)的入度均為 1，那么是一棵有向

9、樹。一個(gè)有向圖的生成森林由假設(shè)干棵有向樹組成，含有圖中全部頂點(diǎn)，但只需足以構(gòu)成假設(shè)干棵不相交的有向樹的弧。生成森林;v圖的籠統(tǒng)類型定義圖的籠統(tǒng)類型定義7.1 圖的定義和術(shù)語圖的定義和術(shù)語ADT Graph 數(shù)據(jù)對象V：V是具有一樣特性的數(shù)據(jù)元素的集 合，稱為頂點(diǎn)集。 數(shù)據(jù)關(guān)系R：R= VR VR=|v,wV且P(v,w)， 表示從v到w的弧，謂詞P(v,w)定義了 弧的意義或信息 根本操作P：ADT Graph;v圖的籠統(tǒng)類型定義圖的籠統(tǒng)類型定義7.1 圖的定義和術(shù)語圖的定義和術(shù)語根本操作CreateGraph(&G,V,VR); / 按V和VR的定義構(gòu)造圖GDestroyGraph(

10、&G); / 銷毀圖GLocateVex(G, u); / 假設(shè)G中存在頂點(diǎn)u，那么前往該頂點(diǎn) / 在圖中位置；否那么前往其它信息GetVex(G, v); / 前往 v 的值PutVex(&G, v, value); / 對 v 賦值valueFirstAdjVex(G, v); / 前往v的第一個(gè)鄰接點(diǎn)。 / 假設(shè)v在G中沒有鄰接點(diǎn)，那么前往“空;v圖的籠統(tǒng)類型定義圖的籠統(tǒng)類型定義7.1 圖的定義和術(shù)語圖的定義和術(shù)語NextAdjVex(G, v, w); / 前往v的(相對于w的)下一 / 個(gè)鄰接點(diǎn)。假設(shè)w是v的最后一個(gè)鄰接點(diǎn)，那么“空InsertVex(&G,

11、v); / 在圖G中增添新頂點(diǎn)v。DeleteVex(&G, v); / 刪除G中頂點(diǎn)v及其相關(guān)的弧InsertArc(&G, v, w); / 在G中增添弧，假設(shè)G / 是無向的，那么還增添對稱弧DeleteArc(&G, v, w); / 在G中刪除弧，假設(shè)G / 是無向的，那么還刪除對稱弧;v圖的籠統(tǒng)類型定義圖的籠統(tǒng)類型定義7.1 圖的定義和術(shù)語圖的定義和術(shù)語DFSTraverse(G, v, Visit(); / 從頂點(diǎn)v起深度優(yōu)先遍歷圖G，并對每個(gè)頂點(diǎn)調(diào)用/ 函數(shù) Visit一次且僅一次。BFSTraverse(G, v, Visit(); / 從頂點(diǎn)v起廣度

12、優(yōu)先遍歷圖G，并對每個(gè)頂點(diǎn)調(diào)用/ 函數(shù) Visit一次且僅一次。;v圖的存儲構(gòu)造圖的存儲構(gòu)造7.2 圖的存儲構(gòu)造圖的存儲構(gòu)造n圖的數(shù)組(鄰接矩陣)存儲表示n圖的鄰接表存儲表示n有向圖的十字鏈表存儲表示n無向圖的鄰接多重表存儲表示;v圖的數(shù)組圖的數(shù)組(鄰接矩陣鄰接矩陣)存儲表示存儲表示 1 假設(shè) vi 和 vj 之間有弧或邊 Aij= 0 反之7.2 圖的存儲構(gòu)造圖的存儲構(gòu)造 設(shè)圖 A = (V, E) 有n個(gè)頂點(diǎn)，那么圖的鄰接矩陣是用于描畫圖中頂點(diǎn)之間關(guān)系(即弧或邊的權(quán))的矩陣。設(shè)圖 A = (V, E) 有n個(gè)頂點(diǎn)，那么圖的鄰接矩陣是一個(gè)二維數(shù)組，定義為： ;v圖的數(shù)組圖的數(shù)組(鄰接矩陣鄰接

13、矩陣)存儲表示存儲表示7.2 圖的存儲構(gòu)造圖的存儲構(gòu)造 v3v1v4v2v4v3v2v1A =0110101011010010v1 v2 v3 v4分析1：無向圖的鄰接矩陣是對稱的；分析2：頂點(diǎn)i 的度第 i 行 (列) 中 1 的個(gè)數(shù)；特 別：完全圖的鄰接矩陣中，對角元素為0，其他全1。;v圖的數(shù)組圖的數(shù)組(鄰接矩陣鄰接矩陣)存儲表示存儲表示7.2 圖的存儲構(gòu)造圖的存儲構(gòu)造;v圖的數(shù)組圖的數(shù)組(鄰接矩陣鄰接矩陣)存儲表示存儲表示7.2 圖的存儲構(gòu)造圖的存儲構(gòu)造v4v3v2v1A =0001100000000110v1 v2 v3 v4注：在有向圖的鄰接矩陣中， 第i行含義：以結(jié)點(diǎn)vi為尾的弧

14、(即出度邊； 第i列含義：以結(jié)點(diǎn)vi為頭的弧(即入度邊。;v圖的數(shù)組圖的數(shù)組(鄰接矩陣鄰接矩陣)存儲表示存儲表示7.2 圖的存儲構(gòu)造圖的存儲構(gòu)造v4v3v2v1A =0001100000000110v1 v2 v3 v4分析1：有向圖的鄰接矩陣能夠是不對稱的。分析2：頂點(diǎn)的出度=第i行元素之和，OD(vi)=A.Edgeij 頂點(diǎn)的入度=第i列元素之和，ID(vi)=A.Edgeji 頂點(diǎn)的度=第i行元素之和+第i列元素之和, 即：TD(vi)=OD(vi) + ID(vi);v網(wǎng)網(wǎng)(帶權(quán)圖帶權(quán)圖)的鄰接矩陣的鄰接矩陣 7.2 圖的存儲構(gòu)造圖的存儲構(gòu)造定義為：A.Edgeij=Wij 或 (v

15、i, vj ) VR 無邊(弧)v1v2v3v4v5v654859315671356598475;v圖的鄰接矩陣圖的鄰接矩陣 7.2 圖的存儲構(gòu)造圖的存儲構(gòu)造容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度判別頂點(diǎn)之間能否有邊弧、找頂點(diǎn)的鄰接點(diǎn)等等。n個(gè)頂點(diǎn)需求n*n個(gè)單元存儲邊(弧);空間效率為O(n2)。 對稀疏圖而言尤其浪費(fèi)空間。鄰接矩陣法優(yōu)點(diǎn)：鄰接矩陣法缺陷：;圖的數(shù)組鄰接矩陣存儲表示#define INFINITY INT_MAX / 最大值#define MAX_VERTEX_NUM 20 / 最大頂點(diǎn)個(gè)數(shù)typedef enum DG, DN, UDG, UDN GraphKind; /圖類型

16、有向圖/網(wǎng),無向圖/網(wǎng)typedef struct ArcCell VRType adj; / 對無權(quán)圖,用1或0表示相鄰否；對帶權(quán)圖,那么為權(quán)值類型 InfoType *info; / 指向該弧相關(guān)信息的指針 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; / 描畫頂點(diǎn)的數(shù)組 AdjMatrix arcs; / 鄰接矩陣 int vexnum, arcnum; / 圖的當(dāng)前頂點(diǎn)數(shù)和弧(邊)數(shù) GraphKind kind; / 圖的種類標(biāo)志 MGraph;

17、構(gòu)造圖的算法 Status CreateGraph (Mgraph & G) /采用數(shù)組(鄰接矩陣)表示法，構(gòu)造圖G。 scanf( &G.kind)； switch (G.kind) case DG：return CreateDG(G)； /構(gòu)造有向圖G case DN：return CreateDN(G)； /構(gòu)造有向網(wǎng)G case UDG：return CreateUDG(G)；/構(gòu)造無向圖G case UDN：return CreateUDN(G)；/構(gòu)造無向網(wǎng)G default： return ERROR； / CreateGraph;采用數(shù)組表示法，構(gòu)造無向網(wǎng)GSt

18、atus CreateUDC(MGraph &G) sacnf( &G.vexnum, &G.arcnum, &IncInfo); for(i=0;iG.vexnum;+i) scanf(&G.vexsi); /構(gòu)造頂點(diǎn)向量 for(i=0；iG.vexnum；+i) /初始化鄰接矩陣 for(j=0;jG.vexnum;+j) G.arcsij=INFINITY,NULL; / adj,info for(k=0；kG.arcnum；+k) /構(gòu)造鄰接矩陣 scanf(&v1，&v2，&w)； /輸入一條邊依靠的頂點(diǎn)及權(quán)值 i=L

19、ocateVex(G,v1);j=LocateVex(G,v2); /v1和v2在G中位置 G.arcsij.adj=w；/弧的權(quán)值 if (IncInfo) Input (*G.); G.arcsji=G.arcsij; /置的對稱弧 return OK;/CreateUDN ;v圖的鄰接表存儲表示圖的鄰接表存儲表示(鏈?zhǔn)芥準(zhǔn)?7.2 圖的存儲構(gòu)造圖的存儲構(gòu)造 對每個(gè)頂點(diǎn)vi 建立一個(gè)單鏈表，把與vi 有關(guān)聯(lián)的邊的信息(即度或出度邊)鏈接起來，表中每個(gè)結(jié)點(diǎn)都設(shè)為3個(gè)域；每個(gè)單鏈表還該當(dāng)附設(shè)一個(gè)頭結(jié)點(diǎn)(設(shè)為2個(gè)域)，存vi信息；adjvexnextArcinfodataf

20、irstArc表結(jié)點(diǎn)頭結(jié)點(diǎn)鄰接點(diǎn)域，表示vi一個(gè)鄰接點(diǎn)的位置鏈域，指向vi下一個(gè)邊或弧的結(jié)點(diǎn)數(shù)據(jù)域，與邊有關(guān)信息如權(quán)值數(shù)據(jù)域，存儲頂點(diǎn) vi 信息鏈域，指向單鏈表的第一個(gè)結(jié)點(diǎn)每個(gè)單鏈表的頭結(jié)點(diǎn)另外用順序存儲構(gòu)造存儲。;v圖的鄰接表存儲表示圖的鄰接表存儲表示(鏈?zhǔn)芥準(zhǔn)?7.2 圖的存儲構(gòu)造圖的存儲構(gòu)造例：無向圖的鄰接表鄰接表1234524452531注：鄰接表不獨(dú)一，因各個(gè)邊結(jié)點(diǎn)的鏈入順序是恣意的。v1v2v3v4v52331;v圖的鄰接表存儲表示圖的鄰接表存儲表示(鏈?zhǔn)芥準(zhǔn)?7.2 圖的存儲構(gòu)造圖的存儲構(gòu)造例：有向圖的鄰接表鄰接表(出邊) 1234 23 4v1v2v3v4 1;v圖的鄰接表存

21、儲表示圖的鄰接表存儲表示(鏈?zhǔn)芥準(zhǔn)?7.2 圖的存儲構(gòu)造圖的存儲構(gòu)造例：有向圖的逆鄰表鄰接表(入邊)1234 4 1 1v1v2v3v4 3;v十字鏈表十字鏈表7.2 圖的存儲構(gòu)造圖的存儲構(gòu)造 它是有向圖的另一種鏈?zhǔn)綐?gòu)造。 思緒：將鄰接矩陣用鏈表存儲，是鄰接表、逆鄰接表的結(jié)合。1、每條弧對應(yīng)一個(gè)結(jié)點(diǎn)(稱為弧結(jié)點(diǎn)，設(shè)5個(gè)域2、每個(gè)頂點(diǎn)也對應(yīng)一個(gè)結(jié)點(diǎn)稱為頂點(diǎn)結(jié)點(diǎn)，設(shè)3個(gè)域tailvexheadvexHlinktlinkinfo頂點(diǎn)結(jié)點(diǎn)弧結(jié)點(diǎn)dataFirstinFirstout;v十字鏈表十字鏈表7.2 圖的存儲構(gòu)造圖的存儲構(gòu)造tailvexheadvexhlinktlinkinfotailvex

22、: 弧尾頂點(diǎn)位置 headvex: 弧頭頂點(diǎn)位置hlink: 弧頭一樣的下一弧位置tlink: 弧尾一樣的下一弧位置info: 弧信息data : 存儲頂點(diǎn)信息。firstin : 以頂點(diǎn)為弧頭的第一條弧結(jié)點(diǎn)。firstout: 以頂點(diǎn)為弧尾的第一條弧結(jié)點(diǎn)。datafirstinfirstout;v十字鏈表存儲構(gòu)造描畫十字鏈表存儲構(gòu)造描畫7.2 圖的存儲構(gòu)造圖的存儲構(gòu)造#define MAX_VERTEX_NUM 20Typedef struct ArcBox /弧結(jié)點(diǎn)構(gòu)造 int tailvex , headvex ; struct ArcBox * hlink , tlink; InfoType *info; ArcBox；Typedef struct VexNode /頂點(diǎn)構(gòu)造 VertexType data; ArcBox * firstin,*firstout;VexNode; Typedef str