【正文】 VertexType data。 /*與弧相關(guān)的信息 */ struct ArcNode *nextarc。 /*圖的類型：有向圖、有向網(wǎng)、無(wú)向圖和無(wú)向網(wǎng) */ typedef struct ArcNode /*邊結(jié)點(diǎn)的類型定義 */ { int adjvex。 圖 。 邊表結(jié)點(diǎn)和表頭結(jié)點(diǎn)的結(jié)構(gòu)如圖 。 圖的存儲(chǔ)結(jié)構(gòu) 表頭結(jié)點(diǎn)表：在每個(gè)鏈表前面設(shè)置一個(gè)頭結(jié)點(diǎn)，除了設(shè)有存儲(chǔ)各個(gè)頂點(diǎn)信息的數(shù)據(jù)域（ data）外，還設(shè)有指向鏈表中第一個(gè)結(jié)點(diǎn)的鏈域（ firstarc），我們把這種表稱為表頭結(jié)點(diǎn)表，相應(yīng)地，結(jié)點(diǎn)稱為表頭結(jié)點(diǎn)。 邊表：在鄰接表中，對(duì)圖中的每個(gè)頂點(diǎn)都建立一個(gè)單鏈表，第 i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn) vi的邊（對(duì)有向圖來(lái)說(shuō)是以頂點(diǎn) vi為尾的?。@種鏈表稱為邊表，其中結(jié)點(diǎn)稱為弧結(jié)點(diǎn)，弧結(jié)點(diǎn)由 3個(gè)域組成：鄰接點(diǎn)域（ adjvex）、數(shù)據(jù)域（ info）和指針域（ nextarc）。 圖的存儲(chǔ)結(jié)構(gòu) 鄰接表 鄰接表（ adjacency list）是圖的一種鏈?zhǔn)酱鎯?chǔ)方式。 分析：主要考察圖的鄰接矩陣表示與算法實(shí)現(xiàn)。 其中，數(shù)組 vex用于存儲(chǔ)圖中的頂點(diǎn)信息，如 ’ a’、 ’ b’、 ’ c’、 ’ d’， arcs用于存儲(chǔ)圖中頂點(diǎn)信息。 /*頂點(diǎn)數(shù)和邊（?。┑臄?shù)目 */ GraphKind kind。 /*用于存儲(chǔ)頂點(diǎn) */ AdjMatrix arc。 /*與弧或邊的相關(guān)信息 */ }ArcNode,AdjMatrix[MaxSize][MaxSize]。 /*圖的類型 */ typedef struct { VRType adj。 帶權(quán)圖的鄰接矩陣表示如圖 。如果圖是一個(gè)無(wú)權(quán)圖，則鄰接矩陣表示為： 對(duì)于帶權(quán)圖，有 A [ i ] [ j ] = 1 當(dāng) v i , v j ∈ E 或 ( v i , v j )∈ E0 反 之A [ i ] [ j ] = w i j 當(dāng) v i , v j ∈ E 或 ( v i , v j )∈ E∞ 反 之 圖的存儲(chǔ)結(jié)構(gòu) 在圖 ，兩個(gè)圖弧和邊的集合分別為A={a,b,a,d,b,c,c,a,c,b,d,c}和E={(a,b),(a,c),(a,d),(b,c),(c,d)}。從圖中的某個(gè)頂點(diǎn)出發(fā)，對(duì)圖進(jìn)行廣度遍歷。從圖中的某個(gè)頂點(diǎn)出發(fā)，對(duì)圖進(jìn)行深度遍歷。對(duì)于無(wú)向圖，還要?jiǎng)h除弧 w,v。G,v,w)：圖的弧刪除操作。對(duì)于無(wú)向圖，還要插入弧 w,v。G,v,w)：圖的弧插入操作。將圖 G中的頂點(diǎn) v及相關(guān)聯(lián)的弧刪除。 （ 9） DeleteVertex(amp。G,v)：圖的頂點(diǎn)插入操作。在圖 G中查找 v的下一個(gè)鄰接頂點(diǎn)，即 w的第一個(gè)鄰接頂點(diǎn)，找到返回其值，否則，返回 1。如果在 G中沒有鄰接頂點(diǎn)，則返回 1。 （ 6） FirstAdjVertex(G,v)：返回 v的第一個(gè)鄰接頂點(diǎn)。 （ 5） GetVertex(G,i)：返回圖 G中序號(hào) i對(duì)應(yīng)的值。 （ 4） LocateVertex(G,v)：返回頂點(diǎn) v在圖的位置。T)：銷毀圖的操作。根據(jù)頂點(diǎn)和邊或弧構(gòu)造一個(gè)圖 G。 圖的定義與相關(guān)概念 2．基本操作集合 （ 1） CreateGraph(amp。圖分為有向圖和無(wú)向圖，圖中結(jié)點(diǎn)之間的關(guān)系用弧或邊表示，通過(guò)弧或邊相連的頂點(diǎn)相鄰接或相關(guān)聯(lián)。 a db ce51 271 0864 圖的定義與相關(guān)概念 圖的抽象數(shù)據(jù)類型 1．?dāng)?shù)據(jù)對(duì)象集合 圖的數(shù)據(jù)對(duì)象為圖的各個(gè)頂點(diǎn)和邊的集合。這種帶權(quán)的圖稱作網(wǎng)（ work）。 a bd cfme 圖的定義與相關(guān)概念 9．網(wǎng) 在圖的邊或弧上，有時(shí)標(biāo)有與它們相關(guān)的數(shù)，這種與圖的邊或弧相關(guān)的數(shù)稱作權(quán)（ weight）。一個(gè)圖的生成樹不一定是唯一的。多于 n1條邊，則一定有環(huán)的出現(xiàn)。如果在該生成樹中添加一條邊，則一定會(huì)在圖中出現(xiàn)一個(gè)環(huán)。反之，稱為稠密圖。將具有 n(n1)條弧的有向圖稱為有向完全圖。將具有 n(n1)/2條邊的無(wú)向圖稱為完全圖（ pleted graph）或無(wú)向完全圖。若不存在頂點(diǎn)到自身的邊或弧，即若存在 vi,vj，則有 vi≠vj。有向圖 G4與強(qiáng)連通分量如圖 。 a bd c( a ) 無(wú) 向 圖 G3fmjika bd cfmjik( b ) 無(wú) 向 圖 G3的 3 個(gè) 連 通 分 量eghleglh 圖的定義與相關(guān)概念 對(duì)于有向圖 G，如果對(duì)每一對(duì)頂點(diǎn) vi和 vj，且 vi≠vj，從 vi到 vj和 vj到 vi都存在路徑，則 G為強(qiáng)連通圖。無(wú)向圖中的極大連通子圖稱為連通分量。 有 向 圖 G1的 子 圖aba ab cab ca db caab無(wú) 向 圖 G2的 子 圖ab cab ca db c 圖的定義與相關(guān)概念 5．連通圖和強(qiáng)連通圖 對(duì)于無(wú)向圖 G，如果從頂點(diǎn) vi到頂點(diǎn) vj存在路徑，則稱 vi到 vj是連通的。 圖的定義與相關(guān)概念 4．子圖 假設(shè)存在兩個(gè)圖 G={V,E}和 G’={V’,E’}，若 G’的頂點(diǎn)和關(guān)系都是V的子集，即有 V’V， E’E，則 G’為 G的子圖。 在圖 G1中，頂點(diǎn)序列 a→ d→ c→ a構(gòu)成了一個(gè)簡(jiǎn)單回路。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡(jiǎn)單路徑。如果 G是有向圖，則路徑也是有向的，路徑的長(zhǎng)度是路徑上弧或邊的數(shù)目。有向圖 G1的弧的集合為A={a,b,a,d,b,c,c,a,c,b,d,c}，頂點(diǎn) a、 b、 c和 d的入度分別為 2和 1，頂點(diǎn) a、 b、 c和 d的出度分別為 2和 1，頂點(diǎn) a、 b、 c和 d的度分別為 4和 2。頂點(diǎn) v的度 (degree)為 TD(v)=ID(v)+OD(v)。對(duì)于有向圖，以頂點(diǎn) v為弧頭的數(shù)目稱為頂點(diǎn) v的入度 (indegree)，記作ID(v)。頂點(diǎn) c鄰接自頂點(diǎn) d，弧d,c與頂點(diǎn) d和 c相關(guān)聯(lián)。頂點(diǎn) c和 d互為鄰接點(diǎn)，邊 (c,d)依附于頂點(diǎn) c和 d?；i,vj和頂點(diǎn) vi、 vj相關(guān)聯(lián)。邊 (vi,vj)依附于頂點(diǎn) vi和 vj，或者說(shuō) (vi,vj)與頂點(diǎn) vi、 vj相關(guān)聯(lián)。無(wú)向圖 G2可以表示為 G2=(V2,E2)，其中，頂點(diǎn)的集合為 V2={a,b,c,d}，邊的集合為 E2={(a,b),(a,c),(a,d),(b,c),(c,d)}。 Path(x,y)表示x,y的意義或信息。如圖 。這樣的圖被稱為有向圖（ digraph）。其中，頂點(diǎn)集合 V不能為空，邊表示頂點(diǎn)之間的關(guān)系。 本章重點(diǎn)： 圖的定義及性質(zhì) 圖的鄰接矩陣和鄰接表表示 圖的各種遍歷 最小生成樹 關(guān)鍵路徑 最短路徑 圖的定義與相關(guān)概念 圖 G也是由數(shù)據(jù)元素集合 V與邊的集合 E構(gòu)成的。 圖的應(yīng)用領(lǐng)域十分廣泛 ， 如化學(xué)分析 、 工程設(shè)計(jì) 、 遺傳學(xué) 、 人工智能等 。第 10章 圖 圖 (graph)是一種比線性表 、 樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu) 。 在線性表中 ， 數(shù)據(jù)元素之間呈線性關(guān)系 ， 即每個(gè)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼 。 本章主要介紹圖的定義 、 圖的存儲(chǔ)結(jié)構(gòu) 、 圖的遍歷 、 最小生成樹 、 關(guān)鍵路徑和最短路徑 。在圖中，數(shù)據(jù)元素通常稱為頂點(diǎn)（ Vertex）。 若 x,y∈ E，則 x,y表示從頂點(diǎn) x到頂點(diǎn) y存在一條弧（ Arc）， x稱為弧尾（ tail）或起始點(diǎn)（ initial node）， y稱為弧頭（ head）或終端點(diǎn)（ terminal node）。 如果 x,y∈ E且有 y,x∈ E，即 E是對(duì)稱的，則用無(wú)序?qū)?(x,y)代替有序?qū)?x,y和 y,x，表示 x與 y之間存在一條邊（ edge），這樣的圖稱為無(wú)向圖（ undigraph）。 a db ca db c有 向 圖 G1無(wú) 向 圖 G2 圖的定義與相關(guān)概念 圖 G的形式化定義為： G=(V,E)，其中， V={x|x∈ 數(shù)據(jù)元素集合 }， E={x,y|Path(x,y)/\(x∈ V,y∈ V)}。 在圖 ，有向圖 G1可以表示為 G1=(V1,E1)，其中，頂點(diǎn)的集合為 V1={a,b,c,d}，邊的集合為E1={a,b,a,d,b,c,c,a,c,b,d,c}。 圖的定義與相關(guān)概念 1．鄰接點(diǎn) 對(duì)于無(wú)向圖 G=(V,E)，若邊 (vi,vj)∈ E，則稱 vi和 vj互為鄰接點(diǎn)（ adjacent），即 vi和 vj相鄰接。對(duì)于有向圖 G=(V,A)，若弧vi,vj∈ A，則稱頂點(diǎn) vi鄰接到頂點(diǎn) vj，頂點(diǎn) vj鄰接自頂點(diǎn) vi。 無(wú)向圖 G2的邊的集合為 E={(a,b),(a,c),(a,d),(b,c),(c,d)}，頂點(diǎn) a和 b互為鄰接點(diǎn)，邊 (a,b)依附于頂點(diǎn) a和 b。有向圖 G1的弧的集合為A={a,b,a,d,b,c,c,a,c,b,d,c}，頂點(diǎn) a鄰接到頂點(diǎn) b，弧 a,b與頂點(diǎn) a和 b相關(guān)聯(lián)。 圖的定義與相關(guān)概念 2．頂點(diǎn)的度 對(duì)于無(wú)向圖，頂點(diǎn) v的度是指與 v相關(guān)聯(lián)的邊的數(shù)目，記作 TD(v)。以頂點(diǎn) v為弧尾的數(shù)目稱為 v的出度 (outdegree)，記作OD(v)。 無(wú)向圖 G2中頂點(diǎn) a的度為 3，頂點(diǎn) b的度為 2，頂點(diǎn) c的度為 3，頂點(diǎn) d的度為 2。 若圖的頂點(diǎn)的個(gè)數(shù)為 n，邊數(shù)或弧數(shù)為 e，頂點(diǎn) vi的度記作 TD(vi)，則頂點(diǎn)的度與弧或者邊數(shù)滿足關(guān)系： e= 圖的定義與相關(guān)概念 3．路徑 無(wú)向圖 G中，從頂點(diǎn) v到頂點(diǎn) v’的路徑（ path）是從 v出發(fā)，經(jīng)過(guò)一系列的頂點(diǎn)序列到達(dá)頂點(diǎn) v’。第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路或環(huán)（ cycle）。除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其他頂點(diǎn)不重復(fù)出現(xiàn)的回路，稱為簡(jiǎn)單回路或簡(jiǎn)單環(huán)。在無(wú)向圖 G2中，從頂點(diǎn) a到頂點(diǎn) c所經(jīng)過(guò)的路徑為 a，d和 c（或 a、 b、 c）。如圖 。如果對(duì)于圖中任意兩個(gè)頂點(diǎn) vi、 vj∈ V， vi和 vj都是連通的，則稱 G是連通圖（ connected graph）。無(wú)向圖 G3與連通分量如圖 。有向圖中的極大強(qiáng)連通子圖稱為有向圖的強(qiáng)連通分量。 a db c有 向 圖 G4adb c有 向 圖 G4的 兩 個(gè) 強(qiáng) 連 通 分 量 圖的定義與相關(guān)概念 6．完全圖 若圖的頂點(diǎn)數(shù)目是 n，圖的邊（?。┑臄?shù)目是 e。對(duì)于無(wú)向圖，邊數(shù) e的取值范圍為 0~n(n1)/2。對(duì)于有向圖，弧數(shù) e的取值范圍是 0~n(n1)。 圖的定義與相關(guān)概念 7．稀疏圖和稠密圖 具有 enlogn條弧或邊的圖，稱為稀疏圖。 8．生成樹 一個(gè)連通圖的生成樹是一個(gè)極小連通子圖，它含有圖的全部頂點(diǎn)，但只有足以構(gòu)成一棵樹的 n1條邊。一棵具有 n個(gè)頂點(diǎn)的生成樹僅有 n1條邊，如果少于 n1條邊，則該圖是非連通的。反過(guò)來(lái)，具有 n1條邊的圖不一定能構(gòu)成生成樹。圖 G5中最大連通分量的一棵生成樹。這些權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或代價(jià)。一個(gè)網(wǎng)如圖 所示。圖中的頂點(diǎn)是沒有先后次序的。 圖中頂點(diǎn)之間是多對(duì)多的關(guān)系，即任何一個(gè)頂點(diǎn)可以有與之鄰接或關(guān)聯(lián)的頂點(diǎn)。G)：圖的創(chuàng)建。 （ 3） DestroyGraph(amp。如果圖 G存在，則將圖 G銷毀。在圖 G中查找頂點(diǎn) v，如果找到該頂點(diǎn)，返回頂點(diǎn)在圖 G中的位置。 i是圖 G某個(gè)頂點(diǎn)的序號(hào)，返回圖 G中序號(hào) i對(duì)應(yīng)的值。在圖 G中查找 v的第一個(gè)鄰接頂點(diǎn)，并將其返回。 圖的定義與相關(guān)概念 （ 7） NextAdjVertex(G,v,w)：返回 v的下一個(gè)鄰接頂點(diǎn)。 （ 8） InsertVertex(amp。在圖 G中增加新的頂點(diǎn) v，并將圖的頂點(diǎn)數(shù)增 1。G,v)：圖的頂點(diǎn)刪除操作。 （ 10） InsertArc(amp。在圖 G中增加弧 v,w。 （ 11） DeleteArc(amp。在圖 G中刪除弧 v,w。 （ 12） DFSTra