1、第第10章章 圖圖 圖圖(graph)是一種比線性表、樹更為復雜的數據結構。在線性表是一種比線性表、樹更為復雜的數據結構。在線性表中，數據元素之間呈線性關系，即每個元素只有一個直接前驅和一中，數據元素之間呈線性關系，即每個元素只有一個直接前驅和一個直接后繼。圖的應用領域十分廣泛，如化學分析、工程設計、遺個直接后繼。圖的應用領域十分廣泛，如化學分析、工程設計、遺傳學、人工智能等。本章主要介紹圖的定義、圖的存儲結構、圖的傳學、人工智能等。本章主要介紹圖的定義、圖的存儲結構、圖的遍歷、最小生成樹、關鍵路徑和最短路徑。遍歷、最小生成樹、關鍵路徑和最短路徑。 本章重點：本章重點： 1 1、圖的定義及性質

2、、圖的定義及性質 2 2、圖的鄰接矩陣和鄰接表表示、圖的鄰接矩陣和鄰接表表示 3 3、圖的各種遍歷、圖的各種遍歷 4 4、最小生成樹、最小生成樹 5 5、關鍵路徑、關鍵路徑 6 6、最短路徑、最短路徑10.1 圖的定義與相關概念圖的定義與相關概念 圖圖G也是由數據元素集合也是由數據元素集合V與邊的集合與邊的集合E構成的。在圖中，數據元構成的。在圖中，數據元素通常稱為頂點（素通常稱為頂點（Vertex）。其中，頂點集合）。其中，頂點集合V不能為空，邊表示不能為空，邊表示頂點之間的關系。頂點之間的關系。 若若E，則，則表示從頂點表示從頂點x到頂點到頂點y存在一條弧存在一條弧（Arc），），x稱為弧

3、尾（稱為弧尾（tail）或起始點（）或起始點（initial node），），y稱為弧稱為弧頭（頭（head）或終端點（）或終端點（terminal node）。這樣的圖被稱為有向圖）。這樣的圖被稱為有向圖（digraph）。）。 如果如果E且有且有E，即，即E是對稱的，則用無序對是對稱的，則用無序對(x,y)代替有序對代替有序對和和，表示，表示x與與y之間存在一條邊（之間存在一條邊（edge），），這樣的圖稱為無向圖（這樣的圖稱為無向圖（undigraph）。如圖）。如圖10.1所示。所示。10.1 圖的定義與相關概念圖的定義與相關概念 圖圖G的形式化定義為：的形式化定義為：G=(V,E)，

4、其中，其中，V=x|x數據元素集數據元素集合合，E=|Path(x,y)/(xV,yV)。Path(x,y)表示表示的意義或信息。的意義或信息。 在圖在圖10.1中，有向圖中，有向圖G1可以表示為可以表示為G1=(V1,E1)，其中，頂點的，其中，頂點的集合為集合為V1=a,b,c,d，邊的集合為，邊的集合為E1=,。無向圖。無向圖G2可可以表示為以表示為G2=(V2,E2)，其中，頂點的集合為，其中，頂點的集合為V2=a,b,c,d，邊的集，邊的集合為合為E2=(a,b),(a,c),(a,d),(b,c),(c,d)。10.1 圖的定義與相關概念圖的定義與相關概念 1鄰接點鄰接點 對于無向

5、圖對于無向圖G=(V,E)，若邊，若邊(vi,vj)E，則稱，則稱vi和和vj互為鄰接點互為鄰接點（adjacent），即），即vi和和vj相鄰接。邊相鄰接。邊(vi,vj)依附于頂點依附于頂點vi和和vj，或，或者說者說(vi,vj)與頂點與頂點vi、vj相關聯。對于有向圖相關聯。對于有向圖G=(V,A)，若弧，若弧A，則稱頂點，則稱頂點vi鄰接到頂點鄰接到頂點vj，頂點，頂點vj鄰接自頂點鄰接自頂點vi。弧。弧和頂點和頂點vi、vj相關聯。相關聯。 無向圖無向圖G2的邊的集合為的邊的集合為E=(a,b),(a,c),(a,d),(b,c),(c,d)，頂點頂點a和和b互為鄰接點，邊互為鄰接

6、點，邊(a,b)依附于頂點依附于頂點a和和b。頂點。頂點c和和d互為鄰互為鄰接點，邊接點，邊(c,d)依附于頂點依附于頂點c和和d。有向圖。有向圖G1的弧的集合為的弧的集合為A=,，頂點，頂點a鄰接到鄰接到頂點頂點b，弧，弧與頂點與頂點a和和b相關聯。頂點相關聯。頂點c鄰接自頂點鄰接自頂點d，弧，弧與頂點與頂點d和和c相關聯。相關聯。10.1 圖的定義與相關概念圖的定義與相關概念2頂點的度頂點的度對于無向圖，頂點對于無向圖，頂點v的度是指與的度是指與v相關聯的邊的數目，記作相關聯的邊的數目，記作TD(v)。對于。對于有向圖，以頂點有向圖，以頂點v為弧頭的數目稱為頂點為弧頭的數目稱為頂點v的入度

7、的入度(indegree)，記作，記作ID(v)。以頂點。以頂點v為弧尾的數目稱為為弧尾的數目稱為v的出度的出度(outdegree)，記作，記作OD(v)。頂點。頂點v的度的度(degree)為為TD(v)=ID(v)+OD(v)。無向圖無向圖G2中頂點中頂點a的度為的度為3，頂點，頂點b的度為的度為2，頂點，頂點c的度為的度為3，頂點，頂點d的度的度為為2。有向圖。有向圖G1的弧的集合為的弧的集合為A=,，頂點，頂點a、b、c和和d的入度分別為的入度分別為1、2、2和和1，頂點，頂點a、b、c和和d的出度分別為的出度分別為2、1、2和和1，頂點，頂點a、b、c和和d的度分別為的度分別為3、

8、3、4和和2。若圖的頂點的個數為若圖的頂點的個數為n，邊數或弧數為，邊數或弧數為e，頂點，頂點vi的度記作的度記作TD(vi)，則頂，則頂點的度與弧或者邊數滿足關系：點的度與弧或者邊數滿足關系：e=10.1 圖的定義與相關概念圖的定義與相關概念 3路徑路徑 無向圖無向圖G中，從頂點中，從頂點v到頂點到頂點v的路徑（的路徑（path）是從）是從v出發，經出發，經過一系列的頂點序列到達頂點過一系列的頂點序列到達頂點v。如果。如果G是有向圖，則路徑也是有是有向圖，則路徑也是有向的，路徑的長度是路徑上弧或邊的數目。第一個頂點和最后一個向的，路徑的長度是路徑上弧或邊的數目。第一個頂點和最后一個頂點相同的

9、路徑稱為回路或環（頂點相同的路徑稱為回路或環（cycle）。序列中頂點不重復出現的）。序列中頂點不重復出現的路徑稱為簡單路徑。除了第一個頂點和最后一個頂點外，其他頂點路徑稱為簡單路徑。除了第一個頂點和最后一個頂點外，其他頂點不重復出現的回路，稱為簡單回路或簡單環。不重復出現的回路，稱為簡單回路或簡單環。 在圖在圖10.1所示的有向圖所示的有向圖G1中，頂點序列中，頂點序列adca構成了一構成了一個簡單回路。在無向圖個簡單回路。在無向圖G2中，從頂點中，從頂點a到頂點到頂點c所經過的路徑為所經過的路徑為a，d和和c（或（或a、b、c）。）。10.1 圖的定義與相關概念圖的定義與相關概念 4子圖子

10、圖 假設存在兩個圖假設存在兩個圖G=V,E和和G=V,E，若，若G的頂點和關系都是的頂點和關系都是V的子集，即有的子集，即有VV，EE，則，則G為為G的子圖。如圖的子圖。如圖10.2所示。所示。10.1 圖的定義與相關概念圖的定義與相關概念 5連通圖和強連通圖連通圖和強連通圖 對于無向圖對于無向圖G，如果從頂點，如果從頂點vi到頂點到頂點vj存在路徑，則稱存在路徑，則稱vi到到vj是連通是連通的。如果對于圖中任意兩個頂點的。如果對于圖中任意兩個頂點vi、vjV，vi和和vj都是連通的，則稱都是連通的，則稱G是連通圖（是連通圖（connected graph）。無向圖中的極大連通子圖稱為連通）。

11、無向圖中的極大連通子圖稱為連通分量。無向圖分量。無向圖G3與連通分量如圖與連通分量如圖10.3所示。所示。10.1 圖的定義與相關概念圖的定義與相關概念 對于有向圖對于有向圖G，如果對每一對頂點，如果對每一對頂點vi和和vj，且，且vivj，從，從vi到到vj和和vj到到vi都存在路徑，則都存在路徑，則G為強連通圖。有向圖中的極大強連通子圖稱為為強連通圖。有向圖中的極大強連通子圖稱為有向圖的強連通分量。有向圖有向圖的強連通分量。有向圖G4與強連通分量如圖與強連通分量如圖10.4所示。所示。 10.1 圖的定義與相關概念圖的定義與相關概念 6完全圖完全圖 若圖的頂點數目是若圖的頂點數目是n，圖的

12、邊（弧）的數目是，圖的邊（弧）的數目是e。若不存在頂點到。若不存在頂點到自身的邊或弧，即若存在自身的邊或弧，即若存在，則有，則有vivj。對于無向圖，邊數。對于無向圖，邊數e的取值范圍為的取值范圍為0n(n-1)/2。將具有。將具有n(n-1)/2條邊的無向圖稱為完條邊的無向圖稱為完全圖（全圖（completed graph）或無向完全圖。對于有向圖，弧數）或無向完全圖。對于有向圖，弧數e的取的取值范圍是值范圍是0n(n-1)。將具有。將具有n(n-1)條弧的有向圖稱為有向完全圖。條弧的有向圖稱為有向完全圖。10.1 圖的定義與相關概念圖的定義與相關概念 7稀疏圖和稠密圖稀疏圖和稠密圖 具有具

13、有enlogn條弧或邊的圖，稱為稀疏圖。反之，稱為稠密圖。條弧或邊的圖，稱為稀疏圖。反之，稱為稠密圖。 8生成樹生成樹 一個連通圖的生成樹是一個極小連通子圖，它含有圖的全部頂點，一個連通圖的生成樹是一個極小連通子圖，它含有圖的全部頂點，但只有足以構成一棵樹的但只有足以構成一棵樹的n-1條邊。如果在該生成樹中添加一條邊，條邊。如果在該生成樹中添加一條邊，則一定會在圖中出現一個環。一棵具有則一定會在圖中出現一個環。一棵具有n個頂點的生成樹僅有個頂點的生成樹僅有n-1條邊，條邊，如果少于如果少于n-1條邊，則該圖是非連通的。多于條邊，則該圖是非連通的。多于n-1條邊，則一定有環的條邊，則一定有環的出

14、現。反過來，具有出現。反過來，具有n-1條邊的圖不一定能構成生成樹。一個圖的生成條邊的圖不一定能構成生成樹。一個圖的生成樹不一定是唯一的。圖樹不一定是唯一的。圖10.5是無向圖是無向圖G5中最大連通分量的一棵生成樹。中最大連通分量的一棵生成樹。10.1 圖的定義與相關概念圖的定義與相關概念 9網網 在圖的邊或弧上，有時標有與它們相關的數，這種與圖的邊或弧相在圖的邊或弧上，有時標有與它們相關的數，這種與圖的邊或弧相關的數稱作權（關的數稱作權（weight）。這些權可以表示從一個頂點到另一個頂點）。這些權可以表示從一個頂點到另一個頂點的距離或代價。這種帶權的圖稱作網（的距離或代價。這種帶權的圖稱作

15、網（network）。一個網如圖）。一個網如圖10.6所示。所示。10.1 圖的定義與相關概念圖的定義與相關概念10.1.3 10.1.3 圖的抽象數據類型圖的抽象數據類型 1數據對象集合數據對象集合 圖的數據對象為圖的各個頂點和邊的集合。圖中的頂點是沒有先后次圖的數據對象為圖的各個頂點和邊的集合。圖中的頂點是沒有先后次序的。圖分為有向圖和無向圖，圖中結點之間的關系用弧或邊表示，通序的。圖分為有向圖和無向圖，圖中結點之間的關系用弧或邊表示，通過弧或邊相連的頂點相鄰接或相關聯。過弧或邊相連的頂點相鄰接或相關聯。 圖中頂點之間是多對多的關系，即任何一個頂點可以有與之鄰接或關圖中頂點之間是多對多的關

16、系，即任何一個頂點可以有與之鄰接或關聯的頂點。聯的頂點。10.1 圖的定義與相關概念圖的定義與相關概念2基本操作集合基本操作集合（1）CreateGraph(&G)：圖的創建。根據頂點和邊或弧構造一個圖：圖的創建。根據頂點和邊或弧構造一個圖G。（3）DestroyGraph(&T)：銷毀圖的操作。如果圖：銷毀圖的操作。如果圖G存在，則將圖存在，則將圖G銷毀。銷毀。（4）LocateVertex(G,v)：返回頂點：返回頂點v在圖的位置。在圖在圖的位置。在圖G中查找頂點中查找頂點v，如，如果找到該頂點，返回頂點在圖果找到該頂點，返回頂點在圖G中的位置。中的位置。（5）GetVer

17、tex(G,i)：返回圖：返回圖G中序號中序號i對應的值。對應的值。i是圖是圖G某個頂點的序號，某個頂點的序號，返回圖返回圖G中序號中序號i對應的值。對應的值。（6）FirstAdjVertex(G,v)：返回：返回v的第一個鄰接頂點。在圖的第一個鄰接頂點。在圖G中查找中查找v的第一的第一個鄰接頂點，并將其返回。如果在個鄰接頂點，并將其返回。如果在G中沒有鄰接頂點，則返回中沒有鄰接頂點，則返回-1。10.1 圖的定義與相關概念圖的定義與相關概念（7）NextAdjVertex(G,v,w)：返回：返回v的下一個鄰接頂點。在圖的下一個鄰接頂點。在圖G中查找中查找v的下一個鄰接的下一個鄰接頂點，即

18、頂點，即w的第一個鄰接頂點，找到返回其值，否則，返回的第一個鄰接頂點，找到返回其值，否則，返回-1。（8）InsertVertex(&G,v)：圖的頂點插入操作。在圖：圖的頂點插入操作。在圖G中增加新的頂點中增加新的頂點v，并將圖的頂，并將圖的頂點數增點數增1。（9）DeleteVertex(&G,v)：圖的頂點刪除操作。將圖：圖的頂點刪除操作。將圖G中的頂點中的頂點v及相關聯的弧刪除。及相關聯的弧刪除。（10）InsertArc(&G,v,w)：圖的弧插入操作。在圖：圖的弧插入操作。在圖G中增加弧中增加弧。對于無向圖，。對于無向圖，還要插入弧還要插入弧。（11）Del

19、eteArc(&G,v,w)：圖的弧刪除操作。在圖：圖的弧刪除操作。在圖G中刪除弧中刪除弧。對于無向圖，。對于無向圖，還要刪除弧還要刪除弧。（12）DFSTraverseGraph(G)：圖的深度遍歷操作。從圖中的某個頂點出發，對圖進行：圖的深度遍歷操作。從圖中的某個頂點出發，對圖進行深度遍歷。深度遍歷。（13）BFSTraverseGraph(G)：圖的廣度遍歷操作。從圖中的某個頂點出發，對圖進行：圖的廣度遍歷操作。從圖中的某個頂點出發，對圖進行廣度遍歷。廣度遍歷。10.2 圖的存儲結構圖的存儲結構 10.2.1 鄰接矩陣（數組表示法） 1什么是圖的鄰接矩陣什么是圖的鄰接矩陣 圖的鄰

20、接矩陣可利用兩個數組實現：一個一維數組用來存儲圖中的圖的鄰接矩陣可利用兩個數組實現：一個一維數組用來存儲圖中的頂點信息；另一個二維數組用來存儲圖中的頂點之間的關系，該二維頂點信息；另一個二維數組用來存儲圖中的頂點之間的關系，該二維數組被稱為鄰接矩陣。如果圖是一個無權圖，則鄰接矩陣表示為：數組被稱為鄰接矩陣。如果圖是一個無權圖，則鄰接矩陣表示為： 對于帶權圖，有對于帶權圖，有10.2 圖的存儲結構圖的存儲結構 在圖在圖10.1中，兩個圖弧和邊的集合分別為中，兩個圖弧和邊的集合分別為A=,和和E=(a,b),(a,c),(a,d),(b,c),(c,d)。它們的鄰接矩陣表示如圖。它們的鄰接矩陣表示

21、如圖10.7所示。所示。 帶權圖的鄰接矩陣表示如圖帶權圖的鄰接矩陣表示如圖10.8所示。所示。10.2 圖的存儲結構圖的存儲結構 圖的鄰接矩陣存儲結構描述如下：圖的鄰接矩陣存儲結構描述如下：#define INFINITY 65535/*65535被認為是一個無窮大的值被認為是一個無窮大的值*/#define MaxSize 50/*最大頂點個數最大頂點個數*/typedef enumDG,DN,UG,UNGraphKind; /*圖的類型圖的類型*/typedef struct VRType adj;/*對于無權圖，用對于無權圖，用1表示相鄰，表示相鄰，0表示不相鄰表示不相鄰*/ InfoP

22、tr *info; /*與弧或邊的相關信息與弧或邊的相關信息*/ArcNode,AdjMatrixMaxSizeMaxSize;typedef struct/*圖的類型定義圖的類型定義*/ VertexType vexMaxSize; /*用于存儲頂點用于存儲頂點*/ AdjMatrix arc; /*鄰接矩陣，存儲邊或弧的信息鄰接矩陣，存儲邊或弧的信息*/ int vexnum,arcnum; /*頂點數和邊（弧）的數目頂點數和邊（弧）的數目*/ GraphKind kind; /*圖的類型圖的類型*/MGraph; 其中，數組其中，數組vex用于存儲圖中的頂點信息，如用于存儲圖中的頂點信息

23、，如a、b、c、d，arcs用于存儲圖中頂點用于存儲圖中頂點信息。信息。10.2 圖的存儲結構圖的存儲結構 2鄰接矩陣應用舉例鄰接矩陣應用舉例 【例【例10_1】試編寫一個算法，采用鄰接矩陣創建一個如圖】試編寫一個算法，采用鄰接矩陣創建一個如圖10.8所所示的有向網示的有向網G。 分析：主要考察圖的鄰接矩陣表示與算法實現。圖的創建包括兩分析：主要考察圖的鄰接矩陣表示與算法實現。圖的創建包括兩個部分：一個是創建頂點，頂點信息可存儲到一個向量（一維數組）個部分：一個是創建頂點，頂點信息可存儲到一個向量（一維數組）中；一個是創建弧的信息，包括弧的相關頂點和權值，可存儲到二中；一個是創建弧的信息，包括

24、弧的相關頂點和權值，可存儲到二維數組中，其中，二維數組的兩個下標分別表示兩個相關頂點在矩維數組中，其中，二維數組的兩個下標分別表示兩個相關頂點在矩陣中的行號和列號，權值存入到數組中。陣中的行號和列號，權值存入到數組中。10.2 圖的存儲結構圖的存儲結構10.2.2 鄰接表 鄰接表（鄰接表（adjacency list）是圖的一種鏈式存儲方式。采用鄰接表）是圖的一種鏈式存儲方式。采用鄰接表表示圖一般需要兩個表結構：邊表和表頭結點表。表示圖一般需要兩個表結構：邊表和表頭結點表。 邊表：在鄰接表中，對圖中的每個頂點都建立一個單鏈表，第邊表：在鄰接表中，對圖中的每個頂點都建立一個單鏈表，第i個個單鏈表

25、中的結點表示依附于頂點單鏈表中的結點表示依附于頂點vi的邊（對有向圖來說是以頂點的邊（對有向圖來說是以頂點vi為為尾的弧），這種鏈表稱為邊表，其中結點稱為弧結點，弧結點由尾的弧），這種鏈表稱為邊表，其中結點稱為弧結點，弧結點由3個個域組成：鄰接點域（域組成：鄰接點域（adjvex）、數據域（）、數據域（info）和指針域）和指針域（nextarc）。其中，鄰接點域表示與相應的表頭頂點鄰接點的位置，）。其中，鄰接點域表示與相應的表頭頂點鄰接點的位置，數據域存儲與邊或弧的信息，指針域用來指示下一個邊或弧的結點。數據域存儲與邊或弧的信息，指針域用來指示下一個邊或弧的結點。10.2 圖的存儲結構圖的存

26、儲結構 表頭結點表：在每個鏈表前面設置一個頭結點，除了設有存儲各表頭結點表：在每個鏈表前面設置一個頭結點，除了設有存儲各個頂點信息的數據域（個頂點信息的數據域（data）外，還設有指向鏈表中第一個結點的）外，還設有指向鏈表中第一個結點的鏈域（鏈域（firstarc），我們把這種表稱為表頭結點表，相應地，結點），我們把這種表稱為表頭結點表，相應地，結點稱為表頭結點。通常情況下，表頭結點采用順序存儲結構實現，這稱為表頭結點。通常情況下，表頭結點采用順序存儲結構實現，這樣可以隨機地訪問任意頂點。樣可以隨機地訪問任意頂點。 邊表結點和表頭結點的結構如圖邊表結點和表頭結點的結構如圖10.10所示。所示。

27、10.2 圖的存儲結構圖的存儲結構圖圖10.1所示的圖所示的圖G1和和G2用鄰接表表示如圖用鄰接表表示如圖10.11所示。所示。圖圖10.8所示的帶權圖的鄰接表如圖所示的帶權圖的鄰接表如圖10.12所示。所示。10.2 圖的存儲結構圖的存儲結構圖的鄰接表存儲結構描述如下：圖的鄰接表存儲結構描述如下：#define MaxSize 50/*最大頂點個數最大頂點個數*/typedef enumDG,DN,UG,UNGraphKind; /*圖的類型：有向圖、有向圖的類型：有向圖、有向網、無向圖和無向網網、無向圖和無向網*/typedef struct ArcNode/*邊結點的類型定義邊結點的類型

28、定義*/ int adjvex; /*弧指向的頂點的位置弧指向的頂點的位置*/ InfoPtr *info;/*與弧相關的信息與弧相關的信息*/ struct ArcNode *nextarc; /*指示下一個與該頂點相鄰接的頂點指示下一個與該頂點相鄰接的頂點*/ArcNode;typedef struct VNode/*頭結點的類型定義頭結點的類型定義*/ VertexType data; /*用于存儲頂點用于存儲頂點*/ ArcNode *firstarc; /*指示第一個與該頂點鄰接的頂點指示第一個與該頂點鄰接的頂點*/VNode,AdjListMaxSize;10.2 圖的存儲結構圖的

29、存儲結構 typedef struct/*圖的類型定義圖的類型定義*/ AdjList vertex; int vexnum,arcnum;/*圖的頂點數目與弧的數目圖的頂點數目與弧的數目*/ GraphKind kind; /*圖的類型圖的類型*/ AdjGraph; 如果無向圖如果無向圖G中有中有n個頂點和個頂點和e條邊，則圖采用鄰接表表示，需要條邊，則圖采用鄰接表表示，需要n個頭結點和個頭結點和2e個表結點。在個表結點。在e遠小于遠小于n(n-1)/2時，采用鄰接表存儲表時，采用鄰接表存儲表示顯然要比采用鄰接矩陣表示更能節省空間。示顯然要比采用鄰接矩陣表示更能節省空間。10.2 圖的存儲

30、結構圖的存儲結構 有時為了便于求某個頂點的入度，需要建立一個有向圖的逆鄰有時為了便于求某個頂點的入度，需要建立一個有向圖的逆鄰接鏈表，也就是為每個頂點接鏈表，也就是為每個頂點vi建立一個以建立一個以vi為弧頭的鏈表。在鄰接為弧頭的鏈表。在鄰接表中，邊表結點的鄰接點域的值為表中，邊表結點的鄰接點域的值為i的個數，就是頂點的個數，就是頂點vi的入度。的入度。因此如果要求某個頂點的入度，則需要對整個鄰接表進行遍歷。因此如果要求某個頂點的入度，則需要對整個鄰接表進行遍歷。圖圖10.1所示的有向圖所示的有向圖G1的逆鄰接鏈表如圖的逆鄰接鏈表如圖10.13所示。所示。10.2 圖的存儲結構圖的存儲結構 【

31、例【例10_2】編寫一個創建如圖】編寫一個創建如圖10.1所示的無向圖（假設采用鄰接表表示所示的無向圖（假設采用鄰接表表示圖）。圖）。 分析：主要考察圖的鄰接表存儲結構。圖的創建包括兩個部分：創建表頭分析：主要考察圖的鄰接表存儲結構。圖的創建包括兩個部分：創建表頭結點和邊表結點。其中，表頭結點利用一個數組實現，數組包括兩個域：一結點和邊表結點。其中，表頭結點利用一個數組實現，數組包括兩個域：一個保存頂點的值；一個是指針，用于指向與頂點相關聯的頂點對應結點。代個保存頂點的值；一個是指針，用于指向與頂點相關聯的頂點對應結點。代碼如下：碼如下：for(i=0;ivexnum;i+)/*將頂點存儲在表

32、頭結點中將頂點存儲在表頭結點中*/scanf(%s,G-vertexi.data);G-vertexi.firstarc=NULL;/*將相關聯的頂點置為空將相關聯的頂點置為空*/10.2 圖的存儲結構圖的存儲結構10.2.3 十字鏈表 十字鏈表（十字鏈表（orthogonal list）是有向圖的另一種鏈式存儲結構，）是有向圖的另一種鏈式存儲結構，它可以看作是將有向圖的鄰接表與逆鄰接鏈表結合起來的得到的一它可以看作是將有向圖的鄰接表與逆鄰接鏈表結合起來的得到的一種鏈表。在十字鏈表中，對應于有向圖中每一條弧有一個結點，對種鏈表。在十字鏈表中，對應于有向圖中每一條弧有一個結點，對應于每個頂點也有

33、一個結點，這些結點的結構如圖應于每個頂點也有一個結點，這些結點的結構如圖10.15所示。所示。 弧結點包含弧結點包含5個域：尾域個域：尾域tailvex、頭域、頭域headvex、infor域和兩域和兩個指針域個指針域hlink、tlink。其中，尾域。其中，尾域tailvex用于表示弧尾頂點在圖用于表示弧尾頂點在圖中的位置，頭域中的位置，頭域headvex表示弧頭頂點在圖中的位置，表示弧頭頂點在圖中的位置，info域表示域表示弧的相關信息，指針域弧的相關信息，指針域hlink指向弧頭相同的下一個條弧，指向弧頭相同的下一個條弧，tlink指向指向弧尾相同的下一條弧。弧尾相同的下一條弧。10.2

34、 圖的存儲結構圖的存儲結構 頂點結點包含頂點結點包含3個域：個域：data域和域和firstin、firstout域，其中，域，其中，data域存儲與頂點相關的信息，如頂點的名稱，域存儲與頂點相關的信息，如頂點的名稱，firstin和和firstout是兩個指是兩個指針域，分別指向以該頂點為弧頭和弧尾的第一個弧度結點。針域，分別指向以該頂點為弧頭和弧尾的第一個弧度結點。 有向圖有向圖G1的十字鏈表存儲表示如圖的十字鏈表存儲表示如圖10.16所示。所示。10.2 圖的存儲結構圖的存儲結構有向圖的十字鏈表存儲結構描述如下：有向圖的十字鏈表存儲結構描述如下：#define MaxSize 50/*最

35、大頂點個數最大頂點個數*/typedef struct ArcNode/*弧結點的類型定義弧結點的類型定義*/ int headvex,tailvex; /*弧的頭頂點和尾頂點位置弧的頭頂點和尾頂點位置*/ InfoPtr *info;/*與弧相關的信息與弧相關的信息*/ struct *hlink,*tlink; /*指示弧頭和弧尾相同的結點指示弧頭和弧尾相同的結點*/ArcNode;typedef struct VNode/*頂點結點的類型定義頂點結點的類型定義*/ VertexType data; /*用于存儲頂點用于存儲頂點*/ ArcNode *firstin,*firstout;

36、/*分別指向頂點的第一條入弧和出弧分別指向頂點的第一條入弧和出弧*/VNode;typedef struct/*圖的類型定義圖的類型定義*/ VNode vertexMaxSize; int vexnum,arcnum;/*圖的頂點數目與弧的數目圖的頂點數目與弧的數目*/OLGraph;10.2 圖的存儲結構圖的存儲結構10.2.4 10.2.4 鄰接多重鏈表鄰接多重鏈表 鄰接多重鏈表（鄰接多重鏈表（adjacency multilist）是無向圖的另一種鏈式）是無向圖的另一種鏈式存儲結構。在無向圖的鄰接表存儲表示中，雖然很容易求得頂點和存儲結構。在無向圖的鄰接表存儲表示中，雖然很容易求得頂點

37、和邊的各種信息，但是對于每一條邊（邊的各種信息，但是對于每一條邊（vi，vj）都有兩個結點，分別在）都有兩個結點，分別在第第i個和第個和第j個鏈表中，這給圖的某些操作帶來不變，例如，要刪除個鏈表中，這給圖的某些操作帶來不變，例如，要刪除一條邊，此時需要找到表示同一條邊的兩個頂點。因此，在進行這一條邊，此時需要找到表示同一條邊的兩個頂點。因此，在進行這一類操作時，采用鄰接多重鏈表比較合適，鄰接多重鏈表是將圖的一類操作時，采用鄰接多重鏈表比較合適，鄰接多重鏈表是將圖的一條邊用一個結點表示。它的結點結構如圖一條邊用一個結點表示。它的結點結構如圖10.17所示。所示。10.2 圖的存儲結構圖的存儲結構

38、 無向圖無向圖G2的多重鏈表如圖的多重鏈表如圖10.18所示。所示。10.2 圖的存儲結構圖的存儲結構無向圖的多重鏈表存儲結構描述如下：無向圖的多重鏈表存儲結構描述如下：#define MaxSize 50/*最大頂點個數最大頂點個數*/typedef struct EdgeNode/*邊結點的類型定義邊結點的類型定義*/ int mark,ivex,jvex; /*訪問標志和邊的兩個頂點位置訪問標志和邊的兩個頂點位置*/ InfoPtr *info;/*與邊相關的信息與邊相關的信息*/ struct *ilink,*jlink; /*指示與邊頂點相同的結點指示與邊頂點相同的結點*/EdgeN

39、ode;typedef struct VNode/*頂點結點的類型定義頂點結點的類型定義*/ VertexType data; /*用于存儲頂點用于存儲頂點*/ EdgeNode *firstedge; /*指向依附于頂點的第一條邊指向依附于頂點的第一條邊*/VexNode;typedef struct/*圖的類型定義圖的類型定義*/ VexNode vertexMaxSize; int vexnum,edgenum;/*圖的頂點數目與邊的數目圖的頂點數目與邊的數目*/AdjMultiGraph;10.3 圖的遍歷圖的遍歷 與樹的遍歷類似，我們希望從圖中某一頂點出發訪遍圖中其余頂與樹的遍歷類似

40、，我們希望從圖中某一頂點出發訪遍圖中其余頂點，且使每一個頂點僅被訪問一次。這一過程就叫做圖的遍歷點，且使每一個頂點僅被訪問一次。這一過程就叫做圖的遍歷（traversing graph）。）。 10.3.1 圖的深度優先搜索 1什么是圖的深度搜索什么是圖的深度搜索 圖的深度優先搜索（圖的深度優先搜索（depth_first search）遍歷類似于樹的先）遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。圖的深度優先遍歷的思想是：假根遍歷，是樹的先根遍歷的推廣。圖的深度優先遍歷的思想是：假設初始狀態是圖中所有頂點未曾被訪問，從圖中某個頂點設初始狀態是圖中所有頂點未曾被訪問，從圖中某個頂點v0出發，

41、出發，訪問頂點訪問頂點v0。然后依次從。然后依次從v0的未被訪問的鄰接點出發深度優先遍歷的未被訪問的鄰接點出發深度優先遍歷圖，直至圖中所有和圖，直至圖中所有和v0有路徑相通的頂點都被訪問到；若此時圖中有路徑相通的頂點都被訪問到；若此時圖中還有頂點未被訪問，則另選圖中一個未被訪問的頂點作為起始點，還有頂點未被訪問，則另選圖中一個未被訪問的頂點作為起始點，重復執行上述過程，直到圖中所有的頂點都被訪問過。重復執行上述過程，直到圖中所有的頂點都被訪問過。10.3 圖的遍歷圖的遍歷 圖的深度優先搜索遍歷過程如圖圖的深度優先搜索遍歷過程如圖10.18所示。實箭頭表示訪問頂所示。實箭頭表示訪問頂點的方向，虛

42、箭頭表示回溯，數字表示訪問或回溯的次序。點的方向，虛箭頭表示回溯，數字表示訪問或回溯的次序。10.3 圖的遍歷圖的遍歷 2圖的深度優先搜索遍歷的算法實現圖的深度優先搜索遍歷的算法實現 圖的深度優先遍歷（鄰接表實現）的算法描述如下。圖的深度優先遍歷（鄰接表實現）的算法描述如下。 int visitedMaxSize; /* 訪問標志數組訪問標志數組*/ void DFSTraverse(AdjGraph G) /*從第從第1個頂點起，深度優先搜索遍歷圖個頂點起，深度優先搜索遍歷圖G*/ int v; for(v=0;vG.vexnum;v+)visitedv=0;/*訪問標志數組初始化為未被訪問

43、訪問標志數組初始化為未被訪問*/ for(v=0;v=0;w=NextAdjVertex(G,G.vertexv.data,G.vertexw.data)if(!visitedw)DFS(G,w);/*遞歸調用遞歸調用DFS對對v的尚未訪的尚未訪問的序號為問的序號為w的鄰接頂點的鄰接頂點*/10.3 圖的遍歷圖的遍歷 如果該圖是一個無向連通圖或者該圖是一個強連通圖，則只需要如果該圖是一個無向連通圖或者該圖是一個強連通圖，則只需要調用一次調用一次DFS(G,v)就可以遍歷整個圖，否則需要多次調用就可以遍歷整個圖，否則需要多次調用DFS(G,v)。在遍歷圖時，對圖中的每個頂點至多調用一次。在遍歷圖

44、時，對圖中的每個頂點至多調用一次DFS(G,v)函數，因為一旦某個頂點被標志為已被訪問，就不再從它出發進行函數，因為一旦某個頂點被標志為已被訪問，就不再從它出發進行搜索。因此，遍歷圖的過程實質上是對每個頂點查找其鄰接點的過搜索。因此，遍歷圖的過程實質上是對每個頂點查找其鄰接點的過程。其時間耗費取決于所采用的存儲結構。當用二維數組表示鄰接程。其時間耗費取決于所采用的存儲結構。當用二維數組表示鄰接矩陣作為圖的存儲結構時，查找每個頂點的鄰接點所需時間為矩陣作為圖的存儲結構時，查找每個頂點的鄰接點所需時間為O(n2)，其中，其中n為圖中的頂點數。當以鄰接表作為圖的存儲結構時，為圖中的頂點數。當以鄰接表

45、作為圖的存儲結構時，查找鄰接點的時間為查找鄰接點的時間為O(e)，其中，其中，e為無向圖邊的數目或有向圖弧為無向圖邊的數目或有向圖弧的數目。由此，當以鄰接表作為存儲結構時，深度優先搜索遍歷圖的數目。由此，當以鄰接表作為存儲結構時，深度優先搜索遍歷圖的時間復雜度為的時間復雜度為O(n+e)。10.3 圖的遍歷圖的遍歷 另一種寫法是：另一種寫法是： void DFS(AdjGraph G,int v) /*從頂點從頂點v出發遞歸深度優先搜索遍歷圖出發遞歸深度優先搜索遍歷圖G*/ ArcNode *p; visitedv=1;/*訪問標志設置為已訪問訪問標志設置為已訪問*/ Visit(G.vert

46、exv.data); /*訪問第訪問第v個頂點個頂點 */ p=G.vertexv.firstarc; /*取取v的邊表頭指針，的邊表頭指針，p指向指向v的鄰接點的鄰接點*/ while(p) /*依次搜索依次搜索v的鄰接點的鄰接點*/ if(!visitedp-adjvex) /*若若v尚未被訪問尚未被訪問*/DFS(G,p-adjvex);/*以以v的鄰接點縱深搜索的鄰接點縱深搜索*/p=p-nextarc; /*找找v的下一個鄰接點的下一個鄰接點*/ 10.3 圖的遍歷圖的遍歷以鄰接表作為存儲結構，查找以鄰接表作為存儲結構，查找v的第一個鄰接點的算法實現如下。的第一個鄰接點的算法實現如下

47、。int FirstAdjVertex(AdjGraph G,VertexType v)/*返回頂點返回頂點v的第一個鄰接頂點的序號的第一個鄰接頂點的序號*/ArcNode *p;int v1;v1=LocateVertex(G,v);/*v1為頂點為頂點v在圖在圖G中的序號中的序號*/p=G.vertexv1.firstarc;if(p)/*如果頂點如果頂點v的第一的第一個鄰接點存在，返回鄰接點的序號，否則返回個鄰接點存在，返回鄰接點的序號，否則返回-1 */return p-adjvex;elsereturn -1;10.3 圖的遍歷圖的遍歷以鄰接表作為存儲結構，查找以鄰接表作為存儲結構，

48、查找v的相對于的相對于w的下一個鄰接點的算法實現如下。的下一個鄰接點的算法實現如下。int NextAdjVertex(AdjGraph G,VertexType v,VertexType w)/*返回返回v的相對于的相對于w的下一個鄰接頂點的序號的下一個鄰接頂點的序號*/ ArcNode *p,*next;int v1,w1;v1=LocateVertex(G,v);/*v1為頂點為頂點v在圖在圖G中的序號中的序號*/w1=LocateVertex(G,w);/*w1為頂點為頂點w在圖在圖G中的序號中的序號*/for(next=G.vertexv1.firstarc;next;)if(nex

49、t-adjvex!=w1)next=next-nextarc;p=next;/*p指向頂點指向頂點v的鄰接頂點的鄰接頂點w的結點的結點*/if(!p|!p-nextarc)/*如果如果w不存在或不存在或w是最后一個鄰接點，是最后一個鄰接點，則返回則返回-1*/return -1;elsereturn p-nextarc-adjvex;/*返回返回v的相對于的相對于w的下一個鄰的下一個鄰接點的序號接點的序號*/10.3 圖的遍歷圖的遍歷10.3.2 圖的廣度優先搜索 1什么是圖的廣度優先搜索遍歷什么是圖的廣度優先搜索遍歷 圖的廣度優先搜索圖的廣度優先搜索(breadth_first search

50、)遍歷類似于樹的層遍歷類似于樹的層次遍歷過程。圖的廣度優先搜索遍歷的思想是：從圖的某個頂點次遍歷過程。圖的廣度優先搜索遍歷的思想是：從圖的某個頂點v出出發，在訪問了發，在訪問了v之后依次訪問之后依次訪問v的各個未曾訪問過的鄰接點，然后分的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發依次訪問他們的鄰接點，并使別從這些鄰接點出發依次訪問他們的鄰接點，并使“先被訪問的頂先被訪問的頂點的鄰接點點的鄰接點”先于先于“后被訪問的頂點的鄰接點后被訪問的頂點的鄰接點”被訪問，直至圖中被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中還有頂點未所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中還

51、有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作為起始點，重復上述被訪問，則另選圖中一個未曾被訪問的頂點作為起始點，重復上述過程，直至圖中的所有頂點都被訪問到為止。過程，直至圖中的所有頂點都被訪問到為止。10.3 圖的遍歷圖的遍歷 例如，圖例如，圖G6的廣度優先搜索遍歷的過程如圖的廣度優先搜索遍歷的過程如圖10.19所示。其中，所示。其中，箭頭表示廣度遍歷的方向，旁邊的數字表示遍歷的次序。箭頭表示廣度遍歷的方向，旁邊的數字表示遍歷的次序。 因此，圖因此，圖G6的廣度優先搜索遍歷序列為的廣度優先搜索遍歷序列為a、b、c、d、e、f、g、h、i。10.3 圖的遍歷圖的遍歷 2圖的廣度優先遍歷的算法

52、實現圖的廣度優先遍歷的算法實現 與深度優先搜索類似，在圖的廣度優先的遍歷過程中也需要一個與深度優先搜索類似，在圖的廣度優先的遍歷過程中也需要一個訪問標志數組訪問標志數組visitedMaxSize，用來表示頂點是否被訪問過。初，用來表示頂點是否被訪問過。初始時，將圖中的所有頂點的標志數組始時，將圖中的所有頂點的標志數組visitedvi都初始化為都初始化為0，表，表示頂點未被訪問。從第示頂點未被訪問。從第1個頂點個頂點v0出發，訪問該頂點并將標志數組出發，訪問該頂點并將標志數組置為置為1。然后將。然后將v0入隊，當隊列不為空時，將隊頭元素（頂點）出入隊，當隊列不為空時，將隊頭元素（頂點）出隊，

53、依次訪問該頂點的所有鄰接點，同時將標志數組對應位置為隊，依次訪問該頂點的所有鄰接點，同時將標志數組對應位置為1，并將其鄰接點依次入隊。依次類推，直到圖中的所有頂點都已被訪并將其鄰接點依次入隊。依次類推，直到圖中的所有頂點都已被訪問過。問過。10.3 圖的遍歷圖的遍歷圖的廣度優先搜索遍歷的算法實現如下。圖的廣度優先搜索遍歷的算法實現如下。void BFSTraverse(AdjGraph G)/*從第從第1個頂點出發，按廣度優先非遞歸遍歷圖個頂點出發，按廣度優先非遞歸遍歷圖G*/int v,front,rear;ArcNode *p;int queueMaxSize;/*定義一個隊列定義一個隊列

54、Q*/front=rear=-1;/*初始化隊列初始化隊列Q*/for(v=0;vG.vexnum;v+)/*初始化標志位初始化標志位*/visitedv=0;v=0;visitedv=1;/*設置訪問標志為設置訪問標志為1，表示已經被訪問過，表示已經被訪問過*/Visit(G.vertexv.data);rear=(rear+1)%MaxSize;10.3 圖的遍歷圖的遍歷queuerear=v;/*v入隊列入隊列*/while(frontadjvex=0)/*如果該頂點未被訪問過如果該頂點未被訪問過*/visitedp-adjvex=1;Visit(G.vertexp-adjvex.dat

55、a);rear=(rear+1)%MaxSize;queuerear=p-adjvex;p=p-nextarc;/*p指向下一個鄰接點指向下一個鄰接點*/10.3 圖的遍歷圖的遍歷10.3.3 圖的遍歷應用舉例 【例【例10_3】編寫一個算法，要求對圖】編寫一個算法，要求對圖10.18中的無向圖中的無向圖G6進行進行深度優先搜索遍歷和廣度優先搜索遍歷（假設圖采用鄰接表存儲）。深度優先搜索遍歷和廣度優先搜索遍歷（假設圖采用鄰接表存儲）。10.4 圖的連通性問題圖的連通性問題 10.4.1 無向圖的連通分量與最小生成樹 在對無向圖進行遍歷時，對于連通圖，僅需從圖的任何一個頂在對無向圖進行遍歷時，對

56、于連通圖，僅需從圖的任何一個頂點出發，進行深度優先搜索或廣度優先搜索，就可訪問到圖中的所點出發，進行深度優先搜索或廣度優先搜索，就可訪問到圖中的所有頂點。對于非連通圖，則需從多個頂點出發進行搜索，而每一次有頂點。對于非連通圖，則需從多個頂點出發進行搜索，而每一次從一個新的起始點出發進行搜索過程中得到的頂點訪問序列恰為其從一個新的起始點出發進行搜索過程中得到的頂點訪問序列恰為其各個連通分量中的頂點集。各個連通分量中的頂點集。10.4 圖的連通性問題圖的連通性問題 圖圖10.3中的非連通圖中的非連通圖G3的鄰接表如圖的鄰接表如圖10.21所示。圖所示。圖G3是非連通圖且有是非連通圖且有3個連通分量

57、，因此在對圖個連通分量，因此在對圖G3進行深度優先遍歷時，需要從圖的至少進行深度優先遍歷時，需要從圖的至少3個頂個頂點（頂點點（頂點a、頂點、頂點g和頂點和頂點i）出發，才能完成對圖中的每個頂點的訪問。對）出發，才能完成對圖中的每個頂點的訪問。對圖圖G3進行深度遍歷，經過進行深度遍歷，經過3次遞歸調用得到的次遞歸調用得到的3個序列分別為：（個序列分別為：（1）a、b、c、d、m、e、f；（；（2）g、h；（；（3）i、j、k、l。這。這3個頂點集分別加上依個頂點集分別加上依附于這些頂點的邊，就構成了非連通圖附于這些頂點的邊，就構成了非連通圖G3的兩個連通分量，如圖的兩個連通分量，如圖10.3（

58、b）所示。所示。10.4 圖的連通性問題圖的連通性問題 設設E（G）為連通圖）為連通圖G中所有邊的集合，則從圖中任一頂點出發遍歷圖時，中所有邊的集合，則從圖中任一頂點出發遍歷圖時，必定將必定將E(G)分成兩個集合分成兩個集合T（G）和）和B（G），其中），其中T（G）是遍歷圖過程中）是遍歷圖過程中經過的邊的集合，經過的邊的集合，B（G）是剩余邊的集合。顯然，）是剩余邊的集合。顯然，T（G）和圖）和圖G中所有頂中所有頂點一起構成連通圖點一起構成連通圖G的極小連通子圖，根據的極小連通子圖，根據10.1節的定義，它是連通圖的節的定義，它是連通圖的一棵生成樹。由深度優先搜索得到的為深度優先生成樹對于連

59、通圖，由廣一棵生成樹。由深度優先搜索得到的為深度優先生成樹對于連通圖，由廣度優先搜索得到的為廣度優先生成樹。圖度優先搜索得到的為廣度優先生成樹。圖10.22就是對應圖就是對應圖G6的深度優先的深度優先生成樹和廣度優先生成樹。生成樹和廣度優先生成樹。10.4 圖的連通性問題圖的連通性問題 對于非連通圖，從某一個頂點出發，對圖進行深度優先搜索遍歷對于非連通圖，從某一個頂點出發，對圖進行深度優先搜索遍歷或者廣度優先搜遍歷，按照訪問路徑會得到若干棵生成樹，這些生或者廣度優先搜遍歷，按照訪問路徑會得到若干棵生成樹，這些生成樹放在一起就構成了森林。對圖成樹放在一起就構成了森林。對圖G3進行深度優先搜索得到

60、的森林進行深度優先搜索得到的森林如圖如圖10.23所示。所示。10.4 圖的連通性問題圖的連通性問題10.4.2 最小生成樹 許多應用問題都是一個求無向連通圖的最小生成樹問題。假設要許多應用問題都是一個求無向連通圖的最小生成樹問題。假設要在在n個城市之間鋪設光纜，主要目標是要使這個城市之間鋪設光纜，主要目標是要使這 n 個城市的任意兩個個城市的任意兩個之間都可以通信，且使鋪設光纜的總費用最低。之間都可以通信，且使鋪設光纜的總費用最低。 在每兩個城市之間都可以鋪設光纜，在每兩個城市之間都可以鋪設光纜，n個城市之間，最多可能鋪個城市之間，最多可能鋪設設n(n-1)/2條光纜，但鋪設光纜的費用很高，且各個城市之間鋪設條光纜，但鋪設光纜的費用很