第7章圖圖的基本概念與存儲(chǔ)

1、第第7章章 圖圖 2圖的基本概念及基本術(shù)語圖的基本概念及基本術(shù)語圖的表示法圖的表示法圖的遍歷圖的遍歷最小生成樹最小生成樹最短路徑最短路徑拓?fù)渑判蛲負(fù)渑判蛑饕獌?nèi)容主要內(nèi)容 3v線性表結(jié)構(gòu)：線性關(guān)系線性表結(jié)構(gòu)：線性關(guān)系v除了起始結(jié)點(diǎn)與終止結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有一個(gè)直除了起始結(jié)點(diǎn)與終止結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼接前驅(qū)和一個(gè)直接后繼v樹形結(jié)構(gòu)：層次關(guān)系樹形結(jié)構(gòu)：層次關(guān)系v除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有一個(gè)父結(jié)點(diǎn)，但可以除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有一個(gè)父結(jié)點(diǎn)，但可以有多個(gè)兒子結(jié)點(diǎn)有多個(gè)兒子結(jié)點(diǎn)v圖：非線性結(jié)構(gòu)更加復(fù)雜圖：非線性結(jié)構(gòu)更加復(fù)雜v每個(gè)結(jié)點(diǎn)每個(gè)結(jié)點(diǎn)(頂點(diǎn)頂點(diǎn))既可以有前驅(qū)結(jié)點(diǎn)也可以有

2、后繼結(jié)既可以有前驅(qū)結(jié)點(diǎn)也可以有后繼結(jié)點(diǎn)，且個(gè)數(shù)不加限制。點(diǎn)，且個(gè)數(shù)不加限制。基本數(shù)據(jù)結(jié)構(gòu)小結(jié)基本數(shù)據(jù)結(jié)構(gòu)小結(jié) 4基本概念基本概念-圖圖Graph=(V,R)V V是頂點(diǎn)的非空是頂點(diǎn)的非空有限集有限集R是邊的有限集是邊的有限集,可為空集可為空集有向圖有向圖無向圖無向圖簡(jiǎn)單分類：簡(jiǎn)單分類： 5弧弧1,2：邊邊弧弧弧尾弧尾弧頭弧頭 6有向圖：有向圖：G1 = V , RV(G1) = 1, 2, 3, 4 R(G1) = , , , , 無向圖：無向圖：G2 = V , RV(G2) = 1, 2, 3, 4, 5 R (G2)= (1,2), (1,4), (2,3), (2,5), (3,4),

3、 (3,5)有序?qū)τ行驅(qū)o序?qū)o序?qū)?7簡(jiǎn)單圖簡(jiǎn)單圖:不考慮頂點(diǎn)到其自身的邊不考慮頂點(diǎn)到其自身的邊,即即(u,v)是圖是圖G的的邊，則邊，則uv；且，如果圖中沒有相同的邊；且，如果圖中沒有相同的邊,則稱圖為則稱圖為簡(jiǎn)單圖簡(jiǎn)單圖以下學(xué)習(xí)的皆是簡(jiǎn)單圖的以下學(xué)習(xí)的皆是簡(jiǎn)單圖的情況！情況！圖的其它分類圖的其它分類 8完全圖完全圖:設(shè)設(shè)|V|=n, |E|=e。對(duì)有向圖對(duì)有向圖G，若，若e=n(n-1)，則稱，則稱G為完全的有向?yàn)橥耆挠邢驁D圖;對(duì)無向圖對(duì)無向圖G，若，若e=n(n-1)/2;則稱則稱G為完全的無向?yàn)橥耆臒o向圖。圖。 完全圖具有最多的邊數(shù)，完全圖具有最多的邊數(shù)，任一對(duì)頂點(diǎn)都有邊相連任一

4、對(duì)頂點(diǎn)都有邊相連有向完全圖有向完全圖無向完全圖無向完全圖 9稀疏圖稀疏圖:有很少條邊的圖（有很少條邊的圖（e1EdgeAEjiEjiji 29無向圖的鄰接矩陣是對(duì)稱的無向圖的鄰接矩陣是對(duì)稱的;有向圖的鄰接矩陣可能是不對(duì)稱的。有向圖的鄰接矩陣可能是不對(duì)稱的。01230101101001011010A.edge012000101010A.edge 30n 在有向圖中在有向圖中, 統(tǒng)計(jì)第統(tǒng)計(jì)第 i 行行 1 的個(gè)數(shù)可得頂點(diǎn)的個(gè)數(shù)可得頂點(diǎn) i 的出的出度，統(tǒng)計(jì)第度，統(tǒng)計(jì)第 j 列列 1 的個(gè)數(shù)可得頂點(diǎn)的個(gè)數(shù)可得頂點(diǎn) j 的入度。的入度。n 在無向圖中在無向圖中, 統(tǒng)計(jì)第統(tǒng)計(jì)第 i 行行 (列列) 1

5、的個(gè)數(shù)可得頂點(diǎn)的個(gè)數(shù)可得頂點(diǎn)i 的的度。度。 3186312954203168532941A.edge賦權(quán)有向圖的鄰接矩陣表示賦權(quán)有向圖的鄰接矩陣表示 32typedef struct VertexType vexsMAX_VERTEX_NUM; /頂點(diǎn)數(shù)組頂點(diǎn)數(shù)組 AdjMatrix arcs; /矩陣矩陣 int vexnum, um; /頂點(diǎn)數(shù)與邊頂點(diǎn)數(shù)與邊(弧弧)數(shù)數(shù) GraphKind kind; /圖的種類圖的種類 MGraph; 圖的鄰接矩陣表示圖的鄰接矩陣表示 33typedef enumDG, DN, AG, ANGraphKind; /圖的種類圖的種類(有向圖，有向網(wǎng)，無向

6、圖，無向網(wǎng)有向圖，有向網(wǎng)，無向圖，無向網(wǎng))圖的鄰接矩陣表示圖的鄰接矩陣表示const MAX_VERTEX_NUM=20; /最大頂點(diǎn)個(gè)數(shù)最大頂點(diǎn)個(gè)數(shù)typedef char VertexType; /頂點(diǎn)類型頂點(diǎn)類型(根據(jù)實(shí)際情況設(shè)定根據(jù)實(shí)際情況設(shè)定) 34typedef struct ArcCell VRType adj; /VRType是頂點(diǎn)關(guān)系類型。是頂點(diǎn)關(guān)系類型。 /對(duì)無權(quán)圖，是對(duì)無權(quán)圖，是1與與0；對(duì)帶權(quán)圖，為權(quán)值信息；對(duì)帶權(quán)圖，為權(quán)值信息 InfoType *info; /指向該弧相關(guān)信息的指針指向該弧相關(guān)信息的指針ArcCell, AdjMatrixMAX_VERTEX_NUM

7、MAX_VERTEX_NUM;/鄰接矩陣類型鄰接矩陣類型圖的鄰接矩陣表示圖的鄰接矩陣表示 35圖的鄰接表圖的鄰接表 (Adjacency List)表示法表示法同一個(gè)頂點(diǎn)發(fā)出的邊鏈接在同一個(gè)邊鏈表中，同一個(gè)頂點(diǎn)發(fā)出的邊鏈接在同一個(gè)邊鏈表中，每一個(gè)鏈結(jié)點(diǎn)代表一條邊每一個(gè)鏈結(jié)點(diǎn)代表一條邊(邊結(jié)點(diǎn)邊結(jié)點(diǎn)), 結(jié)點(diǎn)中有結(jié)點(diǎn)中有另一頂點(diǎn)的下標(biāo)另一頂點(diǎn)的下標(biāo) dest 和指針和指針 next。ABCDdata adjABCD0123dest nextdest next 130210無向圖的鄰接表無向圖的鄰接表 36ABCdata adjABC012dest nextdest next data adjAB

8、C012dest next102 011無向圖的鄰接表無向圖的鄰接表鄰接表鄰接表 (出邊表出邊表)逆鄰接表逆鄰接表 (入邊表入邊表) 37BACD69528data adjABCD0123 dest cost next 1 53 62 83 2(出邊表出邊表)(頂點(diǎn)表頂點(diǎn)表)網(wǎng)絡(luò)網(wǎng)絡(luò) (帶權(quán)圖帶權(quán)圖) 的鄰接表的鄰接表1 9 38const MAX_VERTEX_NUM=20;typedef struct ArcNode int adjvex; /該弧所指向的頂點(diǎn)的位置該弧所指向的頂點(diǎn)的位置 struct ArcNode *nexarc; /指向下一條弧的指針指向下一條弧的指針 InfoTyp

9、e *info; /指向該弧相關(guān)信息的指針指向該弧相關(guān)信息的指針ArcNode;typedef struct vNode VertexType data; /頂點(diǎn)信息頂點(diǎn)信息 ArcNode *firstarc; /指向第一條依附該頂點(diǎn)的弧指向第一條依附該頂點(diǎn)的弧VNode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum, um; /圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) int kind; /圖的種類圖的種類ALGraph; 用鄰接表實(shí)現(xiàn)有向圖用鄰接表實(shí)現(xiàn)有向圖 39BACD69528data adjABCD0123 dest cost next 1 53 62 83 21 9vertices:數(shù)組名數(shù)組名AdjListMAX_VERTEX_NUM類型類型最多容納最多容納20個(gè)元素個(gè)元素 40BACD69528ABCD0123 1 53 62 83 21 9vertices:數(shù)組名數(shù)組名AdjListMAX_VERTEX_NUM類型類型最多容納最多容納20個(gè)元素個(gè)元素datafirstarc 41BACD69528ABCD0123 1 53 62 83 21 9verti