第6章圖第6章圖第6章圖學習目的要求:掌握圖的基本概念。熟練掌握圖的存儲結構。熟練掌握圖的深度優先遍歷和廣度優先遍歷的方法和算法。掌握最小生成樹的普里姆和克魯斯卡爾算法。掌握最短路徑的兩個經典算法:迪杰斯特拉和弗洛伊德算法。掌握拓撲排序的概念，會求拓撲序列。了解關鍵路徑。第6章圖學習目的要求:掌握圖的基本概念。本章內容6.1圖的基本術語6.2圖的存儲結構6.3圖的遍歷6.4最小生成樹6.5最短路徑6.6拓撲排序6.7關鍵路徑圖(Graph)是一種典型的非線性結構，它較線性結構與樹形結構更復雜。在線性表中，數據元素滿足唯一的線性關系，每一個元素(第一個和最后一個除外)有且僅有一個直接前驅和直接后繼；在樹形結構中，數據元素有明顯的層次關系，即每個元素只有一個直接前驅，但可以有多個直接后繼；在圖形結構中，數據元素之間的關系是任意的，每個元素即可以有多個直接前驅，也可以有多個直接后繼。圖的最早應用可追溯到18世紀，偉大的數學家歐拉(Euler)利用圖解決了著名的哥尼斯堡七橋問題，這一創舉為圖在現代科學技術領域的應用奠定了基礎。圖的應用十分廣泛，已滲透到諸如電子線路分析、系統工程、人工智能和計算機科學領域。本章內容6.1圖的基本術語6.5最短路徑圖(Graph)6.1圖的基本術語6.1.1圖的定義1.圖(Graph)圖是一種數據結構，圖中的數據元素通常稱作頂點(Vertex)，V是頂點的有窮非空集合；VR是兩個頂點間關系的集合。若<v,w>∈VR，則<v,w>表示從V到W的一條弧(Arc)，且稱v為弧尾(Tail)或初始點(Initialnode)，稱w為弧頭(Head)或終端點(Terminalnode)，此時的圖稱為有向圖(Digraph)。若<v,w>∈VR必有<w,v>∈VR，即VR是對稱的，則以無序偶對(v,w)代替這兩個有序偶對，此無序偶對(v,w)表示v和w之間的一條邊(Edge)，此時的圖稱為無向圖(Undigraph)。若圖G中只有頂點而沒有邊，稱為零圖。對如下的無向圖G1和有向圖G2可表示為：6.1圖的基本術語6.1.1圖的定義1.圖(Graph6.1圖的基本術語G1=（V1，{A1}）其中：V1={v0,v1,v2,v3}A1={(v0,v1),(v0,v2),(v3,v1),(v3,v2)}G2=（V2，{E2}）其中：V2={v0,v1,v2}E2={<v0,v1>,<v0,v2>,<v1,v2>}6.1.2圖的基本術語1.完全圖（CompletedGraph）無向完全圖:若一個無向圖有n個頂點，且每一個頂點與其他n-1個頂點之間都有邊，這樣的圖稱為無向完全圖。對于一個具有n個頂點的無向完全圖，它共有n(n-1)/2條邊。有向完全圖:

若一個有向圖有n個頂點，且每一個頂點與其他

n-1個頂點之間都有一條以該頂點為起點的弧，這樣的圖稱為有向完全圖。對于一個具有n個頂點的有向完全圖，它共有n(n-1)條弧。6.1圖的基本術語G1=（V1，{A1}）6.1.2圖的6.1圖的基本術語2.子圖（Subgraph）設有兩個圖A和B且滿足條件:V(B)是V(A)的子集，E(B)是E(A)的子集或A(B)是A(A)的子集，則稱圖B是圖A的子圖。6.1圖的基本術語2.子圖（Subgraph）6.1圖的基本術語3.路徑(Path)在無向圖G=(V,{E})中，從頂點Vp到Vq的一條路徑是頂點序列(Vp,Vi1,Vi2,…，Vin,Vq)且(Vp,Vi1),(Vi1,Vi2),…,(Vin,Vq)是E(G)中的邊。對于有向圖G=(V,{A})，從頂點Vp到Vq的一條路徑是頂點序列(Vp,Vi1,Vi2,…，Vin,Vq)應滿足<Vp,Vi1>,<Vi1,Vi2>,…,<Vin,Vq>是A中的弧，其路徑也是有向的。路徑上邊或弧的數目稱為路徑長度。4.簡單路徑序列中頂點不重復出現的路徑稱為簡單路徑。5.回路（Cycle）和簡單回路在一條路徑中，如果其起始點和終止點是同一頂點，則稱其為回路或環。除第一個頂點和最后一個頂點外，其余頂點不重復出現的回路，稱為簡單回路或簡單環。6.1圖的基本術語3.路徑(Path)6.1圖的基本術語6.連通圖(ConnectedGraph)和強連通圖在無向圖G中，若從Vi到Vj有路徑，則稱Vi和Vj是連通的。若G中任意兩頂點都是連通的，則稱G是連通圖。對于有向圖而言，若有向圖G中每一對不同頂點Vi和Vj之間有從Vi到Vj和從Vj到Vi的路徑，則稱G為強連通圖。6.1圖的基本術語6.連通圖(ConnectedGr6.1圖的基本術語7.連通分量和強連通分量連通分量指的是無向圖G中的極大連通子圖。強連通分量指的是有向圖G中的極大強連通子圖。注意:這里是極大而不是最大。8.鄰接點（Adjacent）和相關邊對于無向圖G=(V,E)，若(Vi,Vj)是E(G)中的一條邊，則稱頂點Vi和Vj互為鄰接點，即Vi和Vj相鄰接，邊(V0,V2)是與頂點V0與V2相關聯的邊。對于有向圖G=(V,A)，若<Vi,Vj>是A(G)中的一條弧，則稱頂點Vi鄰接到頂點Vj，頂點Vj鄰接于頂點Vi，而弧<Vi,Vj>則是與頂點Vi和Vj相關聯的弧。6.1圖的基本術語7.連通分量和強連通分量8.鄰接點（6.1圖的基本術語

9.度(Degree)、入度(Indegree)和出度(Outdegree)所謂頂點的度，就是指和該頂點相關聯的邊或弧的數目。在有向圖中，以終止于該頂點的弧的數目稱為該頂點的入度;以起始于該頂點的弧的數目稱為該頂點的出度;某頂點的入度和出度之和稱為該頂點的度。頂點V0的度為3；頂點V1的度為2。頂點V0的入度為1，出度為2，度為3；頂點V1的入度為2，出度為1，度為3；頂點V2的入度為1，出度為1，度為2。6.1圖的基本術語9.度(Degree)、入度(Ind6.1圖的基本術語10.權和網(Net)在一個圖中，每條邊都可以標上具有某種含義的數值，該數值稱為該邊的權。邊上帶權的圖稱為帶權圖，也稱為網。6.1圖的基本術語10.權和網(Net)6.2圖的存儲結構6.2.1鄰接矩陣鄰接矩陣是表示頂點之間相鄰關系的矩陣，可以用一個二維數組來表示。設G=(V,E)

是具有n個頂點的圖，頂點序號依次為0，1，2，…，n-1，則G的鄰接矩陣是如下定義的n階方陣:a[i][j]={1對于無向圖，(Vi,Vj)∈E(G)；對于有向圖，<Vi,Vj>∈E(G)0其他對于帶權圖(網)的鄰接矩陣可以定義為:a[i][j]=Wi對于無向圖，(Vi,Vj)∈E(G)；對于有向圖，<Vi,Vj>∈E(G)；Wi為權∞其他{圖的存儲結構有多種，存儲結構的選擇取決于具體的應用和需要進行的運算。下面給出三種常用的存儲結構：鄰接矩陣、鄰接表和邊集數組。6.2圖的存儲結構6.2.1鄰接矩陣鄰接矩陣是表示頂點之6.2圖的存儲結構在圖的鄰接矩陣中，無向圖的鄰接矩陣是對稱的，而有向圖的鄰接矩陣不一定對稱。并且從鄰接矩陣很容易判定任意兩個頂點之間是否有邊存在，并易于求得各個頂點的度。對于無向圖，頂點Vi的度是鄰接矩陣中第i行（或第i列）的非零元素的個數。對于有向圖，頂點Vi的度是鄰接矩陣中第i行和第i列的非零元素的個數之和;頂點Vi的出度是鄰接矩陣中第i行的非零元素的個數;頂點Vi的入度是鄰接矩陣中第i列的非零元素的個數。G1和G2的鄰接矩陣分別是矩陣A1、A2有向帶權圖和無向帶權圖的鄰接矩陣分別是A3、A46.2圖的存儲結構在圖的鄰接矩陣中，無向圖的鄰接矩陣是對稱6.2圖的存儲結構在C語言中，圖的鄰接矩陣的存儲表示如下：#defineMAX_VERTEX_NUM66#defineINFINITY1e6typedefintVRType;//頂點間關系類型typedefintVertexType;//頂點類型enumGraphKind{DG=0,DN=1,UDG=2,UDN=3};//圖的種類typedefstructArcCell{//矩陣元素類型

VRTypeadj;//VRType是頂點關系類型。對無權圖，用0或1表示相鄰與否；對帶權圖，則為權值類型

InfoType*info;//該弧相關信息指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{

VertexTypevexs[MAX_VERTEX_NUM];//頂點數組

AdjMatrixarcs;//鄰接矩陣

intvexnum,arcnum;//圖的頂點數和弧數

GraphKindkind;//圖的種類}MGraph;6.2圖的存儲結構在C語言中，圖的鄰接矩陣的存儲表示如下：6.2圖的存儲結構根據鄰接矩陣的定義，可以得出建立圖的鄰接矩陣的C++算法如下：6.2.2鄰接表鄰接表(AdjacencyList)是圖的一種鏈式存儲結構。在鄰接表中，對圖的每個頂點建立一個單鏈表，第i個單鏈表中的結點表示依附于頂點vi的邊(對有向圖是以頂點vi為起點的弧)。每個結點由三個域組成，其中鄰接點域(adjvex)指示與頂點vi鄰接的點在圖中的位置，鏈域(nextard)指示下一條邊或弧的結點；數據域(info)存儲和邊或弧相關的信息，如權值等。每個鏈表上附設一個表頭結點。在表頭結點中，除了設有鏈域(firstarc)指向鏈表中的第一個結點外，還設有存儲頂點vi的名稱或其它有關信息的數據域(data)。這些表頭結點通常以順序結構的形式存儲，以便隨機地訪問任一頂點的鏈表。圖G1和圖G2的鄰接表如下圖所示。一個圖的鄰接表存儲結構可形式地說明如下。6.2圖的存儲結構根據鄰接矩陣的定義，可以得出建立圖的鄰接6.2圖的存儲結構typedefintInfoType;typedefintVertexType;typedefstructArcNode{//邊或弧結點類型

intadjvex;//與該邊或弧所關聯的頂點在圖中的位置(即在頂點數組中的下標)

structArcNode*nextarc;//指向下一個邊或弧結點的指針

InfoType*info;//該邊或弧相關信息的指針}ArcNode;typedefstructVNode{//表頭結點類型

VertexTypedata;//頂點信息

ArcNode*firstarc;//指向依附于該頂點的第一條邊或弧的指針}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{//以鄰接表表示的圖的存儲結構

AdjListvertices;//表頭數組

intvexnum,arcnum;//頂點數和邊或弧的條數

GraphKindkind;//圖的種類}ALGraph;6.2圖的存儲結構typedefintInfoType6.2圖的存儲結構若無向圖中有n個頂點、e條邊，則它的鄰接表需要n個頭結點和2e個邊結點。顯然，在邊稀疏的情況下，用鄰接表比用鄰接矩陣節省存儲空間，當和邊相關的信息較多時更是如此。在無向圖的鄰接表中，頂點vi的度恰為第i個鏈表中結點的個數；而在有向圖中，第i個鏈表中的結點數只是頂點vi的出度，為求入度必須遍歷整個鄰接表。在整個鄰接表中其鄰接點域的值為i的結點個數是頂點vi的入度。有時，為了便于確定頂點的入度或以頂點vi為終點的弧，可以建立一個有向圖的逆鄰接表，即對每個頂點vi建立一個鏈接以vi為終點的弧的表。6.2圖的存儲結構若無向圖中有n個頂點、e條邊，則它的鄰接6.2圖的存儲結構建立圖的鄰接表的C++程序見Graph2.cpp6.2圖的存儲結構建立圖的鄰接表的C++程序見Graph26.2圖的存儲結構6.2.3邊集數組帶權圖(網)的另一種存儲結構是邊集數組，它適用于一些以邊為主的操作。用邊集數組表示帶權圖時，列出每條邊所依附的兩個頂點及邊上的權，即每個數組元素代表一條邊的信息。例如，下圖的邊集數組是：016133346422205501515536544525在這個邊集數組中第一列是邊的起點，第二列是邊的終點，第三列是邊的權值。每一行表示一條邊。6.2圖的存儲結構6.2.3邊集數組016在這個邊集6.2圖的存儲結構6.2.4十字鏈表十字鏈表是有向圖的另一種鏈式存儲結構。可以看成將有向圖的鄰接表和逆鄰接表結合起來得到的一種鏈表。在十字鏈表中，對應于有向圖中的每一條弧有一個結點，對應于每一個頂點也有一個結點。這些結點的結構如下所示：在弧結點中有5個域：其中尾域(tailvex)和頭域(headvex)分別指示弧尾和弧頭這兩個頂點在圖中的位置(即在頂點數組中的下標)，鏈域(hlink)指向弧頭相同的下一條弧，而鏈域(tlink)指向弧尾相同的下一條弧，info域指向該弧的相關信息。弧頭相同的弧在同一個鏈表上，弧尾相同的弧也在同一個鏈表上。它們的頭結點就是頂點結點，它由三個域組成：其中data域存儲和頂點相關的信息，如頂點的名稱等；firstin和firstout是兩個鏈域，分別指向以該頂點為弧頭或弧尾的第一個弧結點。下圖給出了一個有向圖及其十字鏈表。6.2圖的存儲結構6.2.4十字鏈表十字鏈表是有向圖的另6.2圖的存儲結構有向圖的十字鏈表存儲表示的形式說明如下所示：#defineMAX_VERTEX_NUM36typedefintInfoType;typedefstructArcBox{

inttailvex,headvex;

structArcBox*hlink,*tlink;

InfoTypeinfo;//弧的權值}ArcBox;//弧結點類型6.2圖的存儲結構有向圖的十字鏈表存儲表示的形式說明如下所6.2圖的存儲結構typedefstructVexNode{

VertexTypedata;//頂點名稱

ArcBox*firstin,*firstout;}VexNode;//頂點結點類型typedefstruct{

VexNodexlist[MAX_VERTEX_NUM];//頂點數組

intvexnum,arcnum;//圖中的頂點數和弧數}OLGraph;//圖的十字鏈表存儲結構類型只要輸入n個頂點和e條弧的信息，便可建立該有向圖的十字鏈表，其算法請見程序Graph3.cpp。6.2圖的存儲結構typedefstructVexNo6.2圖的存儲結構6.2圖的存儲結構6.2圖的存儲結構6.2圖的存儲結構第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖第6章圖學習目的要求:掌握圖的基本概念。熟練掌握圖的存儲結構。熟練掌握圖的深度優先遍歷和廣度優先遍歷的方法和算法。掌握最小生成樹的普里姆和克魯斯卡爾算法。掌握最短路徑的兩個經典算法:迪杰斯特拉和弗洛伊德算法。掌握拓撲排序的概念，會求拓撲序列。了解關鍵路徑。第6章圖學習目的要求:掌握圖的基本概念。本章內容6.1圖的基本術語6.2圖的存儲結構6.3圖的遍歷6.4最小生成樹6.5最短路徑6.6拓撲排序6.7關鍵路徑圖(Graph)是一種典型的非線性結構，它較線性結構與樹形結構更復雜。在線性表中，數據元素滿足唯一的線性關系，每一個元素(第一個和最后一個除外)有且僅有一個直接前驅和直接后繼；在樹形結構中，數據元素有明顯的層次關系，即每個元素只有一個直接前驅，但可以有多個直接后繼；在圖形結構中，數據元素之間的關系是任意的，每個元素即可以有多個直接前驅，也可以有多個直接后繼。圖的最早應用可追溯到18世紀，偉大的數學家歐拉(Euler)利用圖解決了著名的哥尼斯堡七橋問題，這一創舉為圖在現代科學技術領域的應用奠定了基礎。圖的應用十分廣泛，已滲透到諸如電子線路分析、系統工程、人工智能和計算機科學領域。本章內容6.1圖的基本術語6.5最短路徑圖(Graph)6.1圖的基本術語6.1.1圖的定義1.圖(Graph)圖是一種數據結構，圖中的數據元素通常稱作頂點(Vertex)，V是頂點的有窮非空集合；VR是兩個頂點間關系的集合。若<v,w>∈VR，則<v,w>表示從V到W的一條弧(Arc)，且稱v為弧尾(Tail)或初始點(Initialnode)，稱w為弧頭(Head)或終端點(Terminalnode)，此時的圖稱為有向圖(Digraph)。若<v,w>∈VR必有<w,v>∈VR，即VR是對稱的，則以無序偶對(v,w)代替這兩個有序偶對，此無序偶對(v,w)表示v和w之間的一條邊(Edge)，此時的圖稱為無向圖(Undigraph)。若圖G中只有頂點而沒有邊，稱為零圖。對如下的無向圖G1和有向圖G2可表示為：6.1圖的基本術語6.1.1圖的定義1.圖(Graph6.1圖的基本術語G1=（V1，{A1}）其中：V1={v0,v1,v2,v3}A1={(v0,v1),(v0,v2),(v3,v1),(v3,v2)}G2=（V2，{E2}）其中：V2={v0,v1,v2}E2={<v0,v1>,<v0,v2>,<v1,v2>}6.1.2圖的基本術語1.完全圖（CompletedGraph）無向完全圖:若一個無向圖有n個頂點，且每一個頂點與其他n-1個頂點之間都有邊，這樣的圖稱為無向完全圖。對于一個具有n個頂點的無向完全圖，它共有n(n-1)/2條邊。有向完全圖:

若一個有向圖有n個頂點，且每一個頂點與其他

n-1個頂點之間都有一條以該頂點為起點的弧，這樣的圖稱為有向完全圖。對于一個具有n個頂點的有向完全圖，它共有n(n-1)條弧。6.1圖的基本術語G1=（V1，{A1}）6.1.2圖的6.1圖的基本術語2.子圖（Subgraph）設有兩個圖A和B且滿足條件:V(B)是V(A)的子集，E(B)是E(A)的子集或A(B)是A(A)的子集，則稱圖B是圖A的子圖。6.1圖的基本術語2.子圖（Subgraph）6.1圖的基本術語3.路徑(Path)在無向圖G=(V,{E})中，從頂點Vp到Vq的一條路徑是頂點序列(Vp,Vi1,Vi2,…，Vin,Vq)且(Vp,Vi1),(Vi1,Vi2),…,(Vin,Vq)是E(G)中的邊。對于有向圖G=(V,{A})，從頂點Vp到Vq的一條路徑是頂點序列(Vp,Vi1,Vi2,…，Vin,Vq)應滿足<Vp,Vi1>,<Vi1,Vi2>,…,<Vin,Vq>是A中的弧，其路徑也是有向的。路徑上邊或弧的數目稱為路徑長度。4.簡單路徑序列中頂點不重復出現的路徑稱為簡單路徑。5.回路（Cycle）和簡單回路在一條路徑中，如果其起始點和終止點是同一頂點，則稱其為回路或環。除第一個頂點和最后一個頂點外，其余頂點不重復出現的回路，稱為簡單回路或簡單環。6.1圖的基本術語3.路徑(Path)6.1圖的基本術語6.連通圖(ConnectedGraph)和強連通圖在無向圖G中，若從Vi到Vj有路徑，則稱Vi和Vj是連通的。若G中任意兩頂點都是連通的，則稱G是連通圖。對于有向圖而言，若有向圖G中每一對不同頂點Vi和Vj之間有從Vi到Vj和從Vj到Vi的路徑，則稱G為強連通圖。6.1圖的基本術語6.連通圖(ConnectedGr6.1圖的基本術語7.連通分量和強連通分量連通分量指的是無向圖G中的極大連通子圖。強連通分量指的是有向圖G中的極大強連通子圖。注意:這里是極大而不是最大。8.鄰接點（Adjacent）和相關邊對于無向圖G=(V,E)，若(Vi,Vj)是E(G)中的一條邊，則稱頂點Vi和Vj互為鄰接點，即Vi和Vj相鄰接，邊(V0,V2)是與頂點V0與V2相關聯的邊。對于有向圖G=(V,A)，若<Vi,Vj>是A(G)中的一條弧，則稱頂點Vi鄰接到頂點Vj，頂點Vj鄰接于頂點Vi，而弧<Vi,Vj>則是與頂點Vi和Vj相關聯的弧。6.1圖的基本術語7.連通分量和強連通分量8.鄰接點（6.1圖的基本術語

9.度(Degree)、入度(Indegree)和出度(Outdegree)所謂頂點的度，就是指和該頂點相關聯的邊或弧的數目。在有向圖中，以終止于該頂點的弧的數目稱為該頂點的入度;以起始于該頂點的弧的數目稱為該頂點的出度;某頂點的入度和出度之和稱為該頂點的度。頂點V0的度為3；頂點V1的度為2。頂點V0的入度為1，出度為2，度為3；頂點V1的入度為2，出度為1，度為3；頂點V2的入度為1，出度為1，度為2。6.1圖的基本術語9.度(Degree)、入度(Ind6.1圖的基本術語10.權和網(Net)在一個圖中，每條邊都可以標上具有某種含義的數值，該數值稱為該邊的權。邊上帶權的圖稱為帶權圖，也稱為網。6.1圖的基本術語10.權和網(Net)6.2圖的存儲結構6.2.1鄰接矩陣鄰接矩陣是表示頂點之間相鄰關系的矩陣，可以用一個二維數組來表示。設G=(V,E)

是具有n個頂點的圖，頂點序號依次為0，1，2，…，n-1，則G的鄰接矩陣是如下定義的n階方陣:a[i][j]={1對于無向圖，(Vi,Vj)∈E(G)；對于有向圖，<Vi,Vj>∈E(G)0其他對于帶權圖(網)的鄰接矩陣可以定義為:a[i][j]=Wi對于無向圖，(Vi,Vj)∈E(G)；對于有向圖，<Vi,Vj>∈E(G)；Wi為權∞其他{圖的存儲結構有多種，存儲結構的選擇取決于具體的應用和需要進行的運算。下面給出三種常用的存儲結構：鄰接矩陣、鄰接表和邊集數組。6.2圖的存儲結構6.2.1鄰接矩陣鄰接矩陣是表示頂點之6.2圖的存儲結構在圖的鄰接矩陣中，無向圖的鄰接矩陣是對稱的，而有向圖的鄰接矩陣不一定對稱。并且從鄰接矩陣很容易判定任意兩個頂點之間是否有邊存在，并易于求得各個頂點的度。對于無向圖，頂點Vi的度是鄰接矩陣中第i行（或第i列）的非零元素的個數。對于有向圖，頂點Vi的度是鄰接矩陣中第i行和第i列的非零元素的個數之和;頂點Vi的出度是鄰接矩陣中第i行的非零元素的個數;頂點Vi的入度是鄰接矩陣中第i列的非零元素的個數。G1和G2的鄰接矩陣分別是矩陣A1、A2有向帶權圖和無向帶權圖的鄰接矩陣分別是A3、A46.2圖的存儲結構在圖的鄰接矩陣中，無向圖的鄰接矩陣是對稱6.2圖的存儲結構在C語言中，圖的鄰接矩陣的存儲表示如下：#defineMAX_VERTEX_NUM66#defineINFINITY1e6typedefintVRType;//頂點間關系類型typedefintVertexType;//頂點類型enumGraphKind{DG=0,DN=1,UDG=2,UDN=3};//圖的種類typedefstructArcCell{//矩陣元素類型

VRTypeadj;//VRType是頂點關系類型。對無權圖，用0或1表示相鄰與否；對帶權圖，則為權值類型

InfoType*info;//該弧相關信息指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{

VertexTypevexs[MAX_VERTEX_NUM];//頂點數組

AdjMatrixarcs;//鄰接矩陣

intvexnum,arcnum;//圖的頂點數和弧數

GraphKindkind;//圖的種類}MGraph;6.2圖的存儲結構在C語言中，圖的鄰接矩陣的存儲表示如下：6.2圖的存儲結構根據鄰接矩陣的定義，可以得出建立圖的鄰接矩陣的C++算法如下：6.2.2鄰接表鄰接表(AdjacencyList)是圖的一種鏈式存儲結構。在鄰接表中，對圖的每個頂點建立一個單鏈表，第i個單鏈表中的結點表示依附于頂點vi的邊(對有向圖是以頂點vi為起點的弧)。每個結點由三個域組成，其中鄰接點域(adjvex)指示與頂點vi鄰接的點在圖中的位置，鏈域(nextard)指示下一條邊或弧的結點；數據域(info)存儲和邊或弧相關的信息，如權值等。每個鏈表上附設一個表頭結點。在表頭結點中，除了設有鏈域(firstarc)指向鏈表中的第一個結點外，還設有存儲頂點vi的名稱或其它有關信息的數據域(data)。這些表頭結點通常以順序結構的形式存儲，以便隨機地訪問任一頂點的鏈表。圖G1和圖G2的鄰接表如下圖所示。一個圖的鄰接表存儲結構可形式地說明如下。6.2圖的存儲結構根據鄰接矩陣的定義，可以得出建立圖的鄰接6.2圖的存儲結構typedefintInfoType;typedefintVertexType;typedefstructArcNode{//邊或弧結點類型

intadjvex;//與該邊或弧所關聯的頂點在圖中的位置(即在頂點數組中的下標)

structArcNode*nextarc;//指向下一個邊或弧結點的指針

InfoType*info;//該邊或弧相關信息的指針}ArcNode;typedefstructVNode{//表頭結點類型

VertexTypedata;//頂點信息

ArcNode*firstarc;//指向依附于該頂點的第一條邊或弧的指針}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{//以鄰接表表示的圖的存儲結構

AdjListvertices;//表頭數組

intvexnum,arcnum;//頂點數和邊或弧的條數

GraphKindkind;//圖的種類}ALGraph;6.2圖的存儲結構typedefintInfoType6.2圖的存儲結構若無向圖中有n個頂點、e條邊，則它的鄰接表需要n個頭結點和2e個邊結點。顯然，在邊稀疏的情況下，用鄰接表比用鄰接矩陣節省存儲空間，當和邊相關的信息較多時更是如此。在無向圖的鄰接表中，頂點vi的度恰為第i個鏈表中結點的個數；而在有向圖中，第i個鏈表中的結點數只是頂點vi的出度，為求入度必須遍歷整個鄰接表。在整個鄰接表中其鄰接點域的值為i的結點個數是頂點vi的入度。有時，為了便于確定頂點的入度或以頂點vi為終點的弧，可以建立一個有向圖的逆鄰接表，即對每個頂點vi建立一個鏈接以vi為終點的弧的表。6.2圖的存儲結構若無向圖中有n個頂點、e條邊，則它的鄰接6.2圖的存儲結構建立圖的鄰接表的C++程序見Graph2.cpp6.2圖的存儲結構建立圖的鄰接表的C++程序見Graph26.2圖的存儲結構6.2.3邊集數組帶權圖(網)的另一種存儲結構是邊集數組，它適用于一些以邊為主的操作。用邊集數組表示帶權圖時，列出每條邊所依附的兩個頂點及邊上的權，即每個數組元素代表一條邊的信息。例如，下圖的邊集數組是：016133346422205501515536544525在這個邊集數組中第一列是邊的起點，第二列是邊的終點，第三列是邊的權值。每一行表示一條邊。6.2圖的存儲結構6.2.3邊集數組016在這個邊集6.2圖的存儲結構6.2.4十字鏈表十字鏈表是有向圖的另一種鏈式存儲結構。