Ⅰ 十字鏈表是什麼
十字鏈表是有向圖的另一種鏈式存儲結構，是將有向圖的正鄰接表和逆鄰接表結合起來得到的一種鏈表。
十字鏈表在這種結構中，每條弧的弧頭結點和弧尾結點都存放在鏈表中，並將弧結點分別組織到以弧尾結點為頭結點和以弧頭結點為頭結點的鏈表中。由此可見，圖中的每條弧存在於兩個鏈表中，一個是弧頭相同的鏈表，一個是弧尾相同的鏈表，兩個鏈表在該弧處交叉形成「十」字，因此稱作十字鏈表。十字鏈表的結點結構如圖7－14所示。頂點結點由2個域組成，其中data域存儲和頂點相關的信息，如頂點的名稱等；firstin和firstout為兩個指針域，分別指向以該頂點為弧頭和弧尾的第一個弧結點。弧結點有5個域，其中尾域tailve*和頭域headve*分別指向弧尾和弧頭這兩個頂點在圖中的位置，指針域hlink指向弧頭相同的下一條弧，而指針域tlink指向弧尾相同的下一條弧，Info域指向該弧的相關信息。
十字鏈表的結點結構
Ⅱ 圖的基本概念，圖的存儲--鄰接矩陣、鄰接表、十字鏈表、鄰接多重表
一個圖(G)定義為一個偶對(V,E)，記為G=(V,E)。
V是頂點(Vertex)的非空有限集合，記為V(G)。
E是無序集V&V的一個子集，記為E(G)，其元素是圖的弧(Arc)。
將頂點集合為空的圖稱為空圖。
弧：表示兩個頂點v和w之間存在一個關系，用頂點偶對<v,w>表示。
(1)無向圖:
在一個圖中，如果任意兩個頂點構成的偶對(v,w)∈E 是無序的，即頂點之間的連線是沒有方向的，則稱該圖為無向圖。
(2)有向圖:
在一個圖中，如果任意兩個頂點構成的偶對(v,w)∈E 是有序的，即頂點之間的連線是有方向的，則稱該圖為有向圖。一般記作<v,w>
(3)完全無向圖:
在一個無向圖中，如果任意兩頂點都有一條直接邊相連接，則稱該圖為完全無向圖。在一個含有 n 個頂點的完全無向圖中，有n(n-1)/2條邊。
(4)完全有向圖:
在一個有向圖中，如果任意兩頂點之間都有方向互為相反的兩條弧相連接，則稱該圖為完全有向圖。在一個含有 n 個頂點的完全有向圖中，有n(n-1)條邊。
(5)稠密圖、稀疏圖:
若一個圖接近完全圖，稱為稠密圖;稱邊數很少( )的圖為稀疏圖。
(6)頂點的度、入度、出度:
頂點的度(degree)是指依附於某頂點 的邊數，通常記為TD( )。
在無向圖中，所有頂點度的和是圖中邊的2倍。
在有向圖中，要區別頂點的入度(Indegree)與出度(Outdegree)的概念。
頂點 的入度是指以頂點為終點的弧的數目，記為ID ( );
頂點 出度是指以頂點 為始點的弧的數目，記為 OD( )。
頂點 的出度與入度之和稱為 的度，記為TD( )。即TD( )=OD( )+ID ( )。
(7)邊的權、網圖:
與邊有關的數據信息稱為權(weight)。在實際應用中，權值可以有某種含義。
邊上帶權的圖稱為網圖或網路(network)。如果邊是有方向的帶權圖，則就是一個有向網圖。
(8)路徑、路徑長度:
對無向圖，若從頂點 經過若干條邊能到達 ，則稱頂點 和 是連通的，又稱頂點 到 有路徑。
對有向圖，從頂點 到 有有向路徑，指的是從頂點 經過若干條有向邊能到達 。
路徑上邊或有向邊(弧)的數目稱為路徑長度。
(9)簡單路徑、迴路、簡單迴路:
在一條路徑中，若沒有重復相同的頂點，該路徑稱為簡單路徑。
第一個頂點和最後一個頂點相同的路徑稱為迴路(環)。
除第一個頂點與最後一個頂點之外，其他頂點不重復出現的迴路稱為簡單迴路，或者簡單環。
(10)子圖和生成子圖:
對於圖 G=(V，E)，G』=(V』，E』)，若存在 V』是 V 的子集 ，E』是 E的子集，則稱圖 G』是 G 的一個子圖；
若V』=V且E』是E的子集，則稱圖G』是G的一個生成子圖。
(11)連通圖、連通分量:
對無向圖G=(V,E)，若任意 都是連通的，則稱該圖是連通圖，否則稱為非連通圖。
若G是非連通圖，則極大連通子圖稱為連通分量。
極大的含義：指的是對子圖再增加圖G中的其它頂點，子圖就不再連通。
任何連通圖的連通分量只有一個，即本身，而非連通圖有多個連通分量。
(12)強連通圖、強連通分量:
對於有向圖來說，若圖中任意一對頂點 均有從一個頂點 到另一個頂點 有路徑，也有從 到 的路徑，則稱該有向圖是強連通圖。
有向圖的極大強連通子圖稱為強連通分量。
強連通圖只有一個強連通分量，即本身。非強連通圖有多個強連通分量。
(13)生成樹:
一個連通圖(無向圖)的生成樹是一個極小連通子圖，它含有圖中全部n個頂點和只有足以構成一棵樹的n-1條邊，稱為圖的生成樹。
(14)生成森林:
有向樹是只有一個頂點的入度為0，其餘頂點的入度均為1的有向圖。
有向圖的生成森林是這樣一個子圖，由若干棵有向樹組成，含有圖中全部頂點。
(1)鄰接矩陣法(Adjacency Matrix)
基本思想：對於有n個頂點的圖，用一維數組vexs[n]存儲頂點信息，用二維數組A[n][n]存儲頂點之間關系的信息。該二維數組稱為鄰接矩陣。
在鄰接矩陣中，以頂點在vexs數組中的下標代表頂點，鄰接矩陣中的元素A[i][j]存放的是頂點i到頂點j之間關系的信息。
1)無向圖的數組表示
①無向無權圖的鄰接矩陣
無向無權圖其鄰接矩陣是n階對稱方陣。
若兩條邊相連,A[i][j]=1; 若不相連A[i][j]=0。
②無向帶權圖的鄰接矩陣
若兩條邊相連， ，W為權值。
若兩條邊不相連，A[i][j]=
③無向圖鄰接矩陣的特性
無向圖的鄰接矩陣一定是一個對稱矩陣。因此，在具體存放鄰接矩陣時只需存放 上(或下)三角矩陣的元素即可。
對於頂點 ，其度數是第i行的非0元素(或非 元素)的個數。
無向圖的邊數是上（或下）三角形矩陣的非0元素(或非 元素)的個數。
2)有向圖的數組表示
①有向無權圖的鄰接矩陣
若有向無權圖G=(V,E)有n個頂點，則其鄰接矩陣是n階方陣：
若從 到 有弧，A[i][j]=1；
若從 到 沒有弧，A[i][j]=0；
②有向帶權圖的鄰接矩陣
③有向圖鄰接矩陣的特性
對於頂點 ，第i行的非0元素(或非 元素)的個數是其出度OD( )；
第i列的非0元素(或非 元素)的個數是其入度ID( );
鄰接矩陣中非0元素(或非 元素)的個數就是圖的弧的個數。
對於n個頂點e條邊的無向圖，鄰接矩陣表示時有n n個元素，2 e個非0元素。
對於n個頂點e條邊的有向圖，鄰接矩陣表示時有n n個元素，e個非0元素。
3)圖的鄰接矩陣的操作
定義兩個數組分別存儲頂點信息(數據元素)和邊或弧的信息(數據元素之間的關系) 。
圖的各種操作。
①圖的創建
②圖的頂點定位
實際上是確定一個頂點在 vexs 數組中的位置(下標) ，其過程完全等同於在順序存儲的線性表中查找一個數據元素。
③向圖中增加頂點
向圖中增加一個頂點的操作，類似在順序存儲的線性表的末尾增加一個數據元素。
④向圖中增加一條弧
根據給定的弧或邊所依附的頂點，修改鄰接矩陣中所對應的數組元素。
(2)鄰接鏈表法
1)基本思想：類似於樹的孩子鏈表法，就是對於圖 G 中的每個頂點 ，將所有鄰接於 的頂點 鏈成一個單鏈表，這個單鏈表就稱為頂點 的鄰接鏈表，再將所有點的鄰接表表頭放到數組中，就構成了圖的鄰接鏈表。
對無向圖，其鄰接鏈表是唯一(按順序鏈接)的；對有向圖，其鄰接鏈表有兩種形式。
2)從圖的鄰接表存儲方法容易看出，這種表示具有以下特點:
①表頭向量中每個分量就是一個單鏈表的頭結點，分量個數就是圖中的頂點數目。
②在邊稀疏的情況下，用鄰接表表示圖比鄰接矩陣節省存儲空間。
③在無向圖的鄰接表中，頂點 的度恰為第 i 個鏈表中的結點數。
④有向圖可以建立一個正鄰接表和逆鄰接表，便於統計每個結點的出度和入度。
⑤在鄰接表上容易找到任一頂點的第一個鄰接點和下一個鄰接點，但要判定任意兩個頂點( 和 )之間是否有邊或弧相連，則需搜索第 i 個或第 j 個鏈表，因此，不及鄰接矩陣方便。
對於n個頂點e條邊的無向圖，鄰接表表示時有n個表頭結點，2 e個表結點。
對於n個頂點e條邊的有向圖，鄰接表表示時有n個表頭結點，表結點數不確定，但正鄰接表加上逆鄰接表表結點數為e。
3)表結點及其類型定義
圖的各種操作
①圖的創建
②頂點定位
圖的頂點定位實際上是確定一個頂點在 AdjList 數組中的某個元素的 data 域內容。
③向圖中增加頂點
向圖中增加一個頂點的操作，在 AdjList 數組的末尾增加一個數據元素。
④向圖中增加一條弧
根據給定弧或邊所依附的頂點，修改單鏈表，無向圖修改兩個單鏈表;有向圖修改一個單鏈表。
(3) 十字鏈表法
十字鏈表(Orthogonal List)是有向圖的另一種鏈式存儲結構，是將有向圖的正鄰接表和逆鄰接表結合起來得到的一種鏈表。
在這種結構中，每條弧的弧頭結點和弧尾結點都存放在鏈表中，並將弧結點分別組織到以弧尾結點為頭(頂點)結點和以弧頭結點為頭(頂點)結點的鏈表中。這種結構的結點邏輯結構如圖所示。
data 域:存儲和頂點相關的信息;
指針域 firstin:指向以該頂點為弧頭的第一條弧所對應的弧結點，即逆鄰接鏈表;
指針域 firstout:指向以該頂點為弧尾的第一條弧所對應的弧結點，即正鄰接鏈表;
尾域 tailvex:指示弧尾頂點在圖中的位置;
頭域 headvex:指示弧頭頂點在圖中的位置;
指針域 hlink:指向弧頭相同的下一條弧;
指針域 tlink:指向弧尾相同的下一條弧;
Info 域:指向該弧的相關信息，比如權值;
結點類型定義：
下圖所示是一個有向圖及其十字鏈表(略去了表結點的 info 域)。實質就是先把圖的正鄰接鏈表(出度)畫出來，然後再把firstin,firstout,hlink,tlink連起來。
(4)鄰接多重表法
鄰接多重表(Adjacency Multilist)是無向圖的另一種鏈式存儲結構。
鄰接多重表的結構和十字鏈表類似，每條邊用一個結點表示。
鄰接多重表中的頂點結點結構與鄰接表中的完全相同，而表結點包括六個域。
data 域:存儲和頂點相關的信息;
指針域 firstedge:指向依附於該頂點的第一條邊所對應的表結點;
標志域 mark:用以標識該條邊是否被訪問過;
ivex 和 jvex 域:分別保存該邊所依附的兩個頂點在圖中的位置;
info 域:保存該邊的相關信息;
指針域 ilink:指向下一條依附於頂點 ivex 的邊;
指針域 jlink:指向下一條依附於頂點 jvex 的邊;
結點類型定義:
鄰接多重表與鄰接表的區別:後者的同一條邊用兩個表結點表示，而前者只用一個表結點表示;除標志域外，鄰接多重表與鄰接表表達的信息是相同的，因此，操作的實現也基本相似。
Ⅲ 十字鏈表的介紹
十字鏈表（Orthogonal List)是有向圖的另一種鏈式存儲結構。該結構可以看成是將有向圖的鄰接表和逆鄰接表結合起來得到的。用十字鏈表來存儲有向圖，可以達到高效的存取效果。同時，代碼的可讀性也會得到提升。
Ⅳ 十字鏈表的十字鏈表
十字鏈表（Orthogonal List)是有向圖的另一種鏈式存儲結構。可以看成是將有向圖的鄰接表和逆鄰接表結合起來得到的一種鏈表。在十字鏈表中，對應於有向圖中每一條弧都有一個結點，對應於每個定頂點也有一個結點。
十字鏈表之於有向圖，類似於鄰接表之於無向圖。
也可以理解為 將行的單鏈表和列的單鏈表結合起來存儲稀疏矩陣稱為十字鏈表， 每個節點表示一個非零元素。
Ⅳ 圖的五種存儲結構
圖的鄰接矩陣（Adjacency Matrix）： 圖的鄰接矩陣用兩個數組來表示圖。一個一維數組存儲圖中頂點信息，另一個二維數組（一般稱之為鄰接矩陣）來存儲圖中的邊或者弧的信息。從鄰接矩陣中我們自然知道一個頂點的度（對於無向圖）或者有向圖中一個頂點的入度出度信息。
假設圖G有n個頂點，則鄰接矩陣是一個n*n的方陣。
1.對於如果圖上的每條邊不帶權值來說，那麼我們就用真（一般為1）和假（一般為0）來表示一個頂點到另一個頂點存不存在邊。下面是一個圖的鄰接矩陣的定義：
鄰接矩陣法實現帶權值的無向圖的創建如下：
按照如圖輸入各邊（不重復）
測試程序如下：
結果可得該矩陣，證明創建樹成功。 假設n個頂點e條邊的創建，createGraph演算法的時間復雜度為O（n+n*n+e）。如果需要創建一個有向圖，那麼和上面一樣一個一個錄入邊下標和權值。
鄰接矩陣這種存儲結構的優缺點： 缺點是對於邊數相對頂點較少的稀疏圖來說會存在極大的空間浪費。假設有n個頂點,優點是對於有向完全圖和無向完全圖來說鄰接矩陣是一種不錯的存儲結構，浪費的話也只浪費了n個頂點的容量。
在樹的存儲結構一節中我們提到對於孩子表示法的第三種：用一段連續的存儲單元（數組）存儲樹中的所有結點，利用一個單鏈表來存儲數組中每個結點的孩子的信息。對於圖的存儲結構來說，我們也可以利用這種方法實現圖的存儲
鄰接表(Adjacency List): 這種數組與鏈表相結合的存儲方法叫做鄰接表。1.為什麼不也用單鏈表存儲圖的結點信息呢？原因就是數組這種順序存儲結構讀取結點信息速率快。對於頂點數組中，每個數據元素還需要存儲一個指向第一個鄰接頂點的指針，這樣才可以查找邊的信息2.圖中每個頂點Vi(i > 0)的所有鄰接點構成一個線性表 （在無向圖中這個線性表稱為Vi的邊表，有向圖中稱為頂點作為弧尾的出邊表） ，由於鄰接點的不確定性，所以用鏈表存儲，有多少個鄰接點就malloc一個空間存儲鄰接點，這樣更不會造成空間的浪費（與鄰接矩陣相比來說）。3.對於鄰接表中的某個頂點來說，用戶關心的是這個頂點的鄰接點，完全可以遍歷用單鏈表設計成的邊表或者出邊表得到，所以沒必要設計成雙鏈表。
鄰接表的存儲結構：
假設現在有一無向圖G，如下圖：
從鄰接表結構中，知道一個頂點的度或者判斷兩個頂點之間是否存在邊或者求一個頂點的所有鄰接頂點是很容易的。
假設現在有一有向圖G，如下圖：
無向圖的鄰接表創建示例如下：
假設在上圖（無向圖）中的V0V1V2V3頂點值為ABCD，則依據下面測試程序可得結果：
鄰接表的優缺點： 優點是：鄰接表存儲圖，既能夠知道一個頂點的度和頂點的鄰接結點的信息，並且更不會造成空間的浪費。缺點是鄰接表存儲有向圖時，如果關心的是頂點的出度問題自然用鄰接表結構，但是想了解入度需要遍歷圖才知道（需要考慮逆鄰接表）。
十字鏈表(Orthogonal List) ：有向圖的一種存儲方法，它把鄰接表和逆鄰接表結合起來，因此在十字鏈表結構中可以知道一個頂點的入度和出度情況。
重新定義頂點表的結點如下圖：
現在有一有向圖如下圖：
則它的存儲結構示意圖為：
其定義如下：
十字鏈表是用來存儲有向圖的，這樣可以看出一個頂點的出入度信息。對於無向圖來說完全沒必要用十字鏈表來存儲。
在無向圖中，因為我們關注的是頂點的信息，在考慮節約空間的情況下我們利用鄰接表來存儲無向圖。但是如果我們關注的是邊的信息，例如需要刪除某條邊對於鄰接表來說是挺繁瑣的。它需要操作兩個單鏈表刪除兩個結點。因此我們仿照十字鏈表的方式對邊表結點結構重新定義如下圖：
它的鄰接多重表結構為：
多重鄰接表的優點：對於邊的操作相比於鄰接表來說更加方便。比如說我們現在需要刪除(V0,V2)這條邊，只需將69步驟中的指針改為nullptr即可。
邊集數組(edgeset array)： 邊集數組是由兩個數組組成，一個存儲頂點信息，另一個存儲邊的信息，這個邊數組中的每個數據元素由起點下標，終點下標，和權組成（如果邊上含有權值的話）。
邊數組結構如下圖：
邊集數組實現圖的存儲的優缺點：優點是對於邊的操作方便快捷，操作的只是數組元素。比如說刪除某條邊，只需要刪除一個數組元素。缺點是：對於圖的頂點信息，我們只有遍歷整個邊數組才知道，這個費時。因此對於關注邊的操作來說，邊集數組更加方便。