第7章圖圖的基本概念與存儲

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

2、后繼結(jié)既可以有前驅(qū)結(jié)點也可以有后繼結(jié)點，且個數(shù)不加限制。點，且個數(shù)不加限制?；緮?shù)據(jù)結(jié)構(gòu)小結(jié)基本數(shù)據(jù)結(jié)構(gòu)小結(jié) 4基本概念基本概念-圖圖Graph=(V,R)V V是頂點的非空是頂點的非空有限集有限集R是邊的有限集是邊的有限集,可為空集可為空集有向圖有向圖無向圖無向圖簡單分類：簡單分類： 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簡單圖簡單圖:不考慮頂點到其自身的邊不考慮頂點到其自身的邊,即即(u,v)是圖是圖G的的邊，則邊，則uv；且，如果圖中沒有相同的邊；且，如果圖中沒有相同的邊,則稱圖為則稱圖為簡單圖簡單圖以下學習的皆是簡單圖的以下學習的皆是簡單圖的情況！情況！圖的其它分類圖的其它分類 8完全圖完全圖:設設|V|=n, |E|=e。對有向圖對有向圖G，若，若e=n(n-1)，則稱，則稱G為完全的有向為完全的有向圖圖;對無向圖對無向圖G，若，若e=n(n-1)/2;則稱則稱G為完全的無向為完全的無向圖。圖。 完全圖具有最多的邊數(shù)，完全圖具有最多的邊數(shù)，任一對頂點都有邊相連任一

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

5、的個數(shù)可得頂點的個數(shù)可得頂點i 的的度。度。 3186312954203168532941A.edge賦權有向圖的鄰接矩陣表示賦權有向圖的鄰接矩陣表示 32typedef struct VertexType vexsMAX_VERTEX_NUM; /頂點數(shù)組頂點數(shù)組 AdjMatrix arcs; /矩陣矩陣 int vexnum, um; /頂點數(shù)與邊頂點數(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; /最大頂點個數(shù)最大頂點個數(shù)typedef char VertexType; /頂點類型頂點類型(根據(jù)實際情況設定根據(jù)實際情況設定) 34typedef struct ArcCell VRType adj; /VRType是頂點關系類型。是頂點關系類型。 /對無權圖，是對無權圖，是1與與0；對帶權圖，為權值信息；對帶權圖，為權值信息 InfoType *info; /指向該弧相關信息的指針指向該弧相關信息的指針ArcCell, AdjMatrixMAX_VERTEX_NUM

7、MAX_VERTEX_NUM;/鄰接矩陣類型鄰接矩陣類型圖的鄰接矩陣表示圖的鄰接矩陣表示 35圖的鄰接表圖的鄰接表 (Adjacency List)表示法表示法同一個頂點發(fā)出的邊鏈接在同一個邊鏈表中，同一個頂點發(fā)出的邊鏈接在同一個邊鏈表中，每一個鏈結(jié)點代表一條邊每一個鏈結(jié)點代表一條邊(邊結(jié)點邊結(jié)點), 結(jié)點中有結(jié)點中有另一頂點的下標另一頂點的下標 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(出邊表出邊表)(頂點表頂點表)網(wǎng)絡網(wǎng)絡 (帶權圖帶權圖) 的鄰接表的鄰接表1 9 38const MAX_VERTEX_NUM=20;typedef struct ArcNode int adjvex; /該弧所指向的頂點的位置該弧所指向的頂點的位置 struct ArcNode *nexarc; /指向下一條弧的指針指向下一條弧的指針 InfoTyp

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