資料結構系列 - 圖
1. 前言
圖是一種非線性資料結構，是一種更為複雜的資料結構，在圖中，資料元素之間時多對多的關係，即一個數據元素對應多個直接前驅和多個直接後繼元素。圖的應用領域十分廣泛，如化學分析，工程設計、遺傳學、人工智慧等。
2. 圖的定義和相關概念
圖是一種資料元素間為多對多關係的資料結構，加上一組基本操作構成的抽象資料型別。
資料物件V ：V是具有相同特性的資料元素的集合，稱為頂點集。
資料關係R：
R={VR}
VR={<v,w>|v,w(-V且P(v,w),<v,w>表示從v到w的弧，謂詞P(v,w)定義了弧<v,w>的意義或資訊}
基本操作P：
- CreateGraph(&G,V,VR)
- 初始條件：V是圖的頂點集，VR是圖中弧的集合。
- 操作結果：按V和VR的定義構造圖G
- DestroyGraph(&G);
- 初始條件：圖G存在
- 操作結果：銷燬圖G
- LocateVex(G,u);
- 初始條件：圖G存在，u一G中頂點有相同特徵
- 操作結果：若G中存在頂點u, 則返回該頂點在圖中位置；否則返回其它資訊。
- GetVex(G,v);
- 初始條件：圖G存在，v是G中某個頂點
- 操作結果：返回v的值。
- PutVex(&G,v,value);
- 初始條件：圖G存在，v是G中某個頂點
- 操作結果：對v賦值value
- FirstAdjVex(G,v);
- 初始條件：圖G存在，v是G中某個頂點
- 操作結果：返回v的第一個鄰接頂點。若頂點在G中沒有鄰接頂點，則返回“空”
- NextAdjVex(G,v,w);
- 初始條件：圖G存在,v是G中某個頂點,w是v的鄰接頂點。
- 操作結果：返回v的（相對於w的）下一個鄰接頂點。若w是v的最後一個鄰接點，則返回“空”
- InsertVex(&G,v);
- 初始條件：圖G存在，v和圖中頂點有相同特徵
- 操作結果：在圖G中增添新頂點v
- DeleteVex(&G,v);
- 初始條件：圖G存在，v是G中某個頂點
- 操作結果：刪除G中頂點v及其相關的弧
- InsertAcr(&G,v,w);
- 初始條件：圖G存在，v和w是G中兩個頂點
- 操作結果：在G中增添弧<v,w>,若G是無向的，則還增添對稱弧<w,v>
- DeleteArc(&G,v,w);
- 初始條件：圖G存在，v和w是G中兩個頂點
- 操作結果：在G中刪除弧<v,w>,若G是無向的，則還刪除對稱弧<w,v>
- DFSTraverser(G,v,Visit());
- 初始條件：圖G存在，v是G中某個頂點，Visit是頂點的應用函式
- 操作結果：從頂點v起深度優先遍歷圖G，並對每個頂點呼叫函式Visit一次。一旦Visit()失敗，則操作失敗。
- BFSTRaverse(G,v,Visit());
- 初始條件：圖G存在，v是G中某個頂點，Visit是頂點的應用函式
- 操作結果：從頂點v起廣度優先遍歷圖G，並對每個頂點呼叫函式Visit一次。一旦Visit()失敗，則操作失敗。
圖 有向圖和無向圖
對上圖有：G1=(V1,{A1})
其中：V1={v1,v2,v3,v4} A1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}
如果用n表示圖中頂點數目，用e表示邊或弧的數目，則有：
對於無向圖，e的取值範圍是0到n(n-1)/2,有n(n-1)/2條邊的無向圖稱為完全圖。
對於有向圖，e有取值範圍是0到n(n-1)。具有n(n-1)條弧的有向圖稱為有向完全圖。
有很少條邊或弧的圖稱為稀疏圖，反之稱為稠密圖。
3. 圖的儲存結構
圖的儲存方式有四種：鄰接矩陣表示法、鄰接表表示法、十字連結串列表示法和多重連結串列表示法。
（1）鄰接矩陣表示法
圖的鄰接矩陣表示也稱為陣列表示，圖的鄰接矩陣就是利用C語言中的兩個陣列實現。其中一個是一維陣列，用來儲存圖中的頂點資訊；另一個是二維陣列，用來儲存圖中的頂點之間的關係，該二維陣列被稱為鄰接矩陣。
圖的鄰接矩陣表示法也稱為陣列表示。如果圖式一個無權圖，則鄰接矩陣表示為：
對於帶權圖，有
上圖的鄰接矩陣表示如下圖所示：
圖的鄰接矩陣儲存結構用C語言描述如下：
#define INFINITY 10000 /*定義一個無限大的值*/ #define MaxSize 50 /*最大頂點個數*/ typedef enum{DG,DN,UG,UN}GraphKind; /*圖的型別：有向圖、有向網、無向圖和無向網*/ typedef struct { VRType adj; /*對於無權圖，用1表示相鄰，0表示不相鄰；對於帶權圖，儲存權值*/ InfoPtr *info; /*與弧或邊的相關資訊*/ }ArcNode,AdjMatrix[MaxSize][MaxSize]; typedef struct /*圖的型別定義*/ { VertexType vex[MaxSize]; /*用於儲存頂點*/ AdjMatrix arc; /*鄰接矩陣，儲存邊或弧的資訊*/ int vexnum,arcnum; /*頂點數和邊（弧）的數目*/ GraphKind kind; /*圖的型別*/ }MGraph;
帶權圖的鄰接矩陣表示示意圖：
（2）鄰接表表示法
圖的鄰接表表示法是一種鏈式儲存方式。在圖的鄰接表中，對圖中的每個頂點都建立一個單鏈表，用來表示邊或弧，這種表示頂點之間關係的連結串列稱為邊表，相應地，結點稱為邊結點。在每個單鏈表前面設定一個頭結點，存放圖中的各個頂點結點，這種表稱為表頭結點表，相應地，結點稱為表頭結點。
圖的鄰接表儲存結構可以用C語言描述如下：
#define MaxSize 50 /*最大頂點個數*/
typedef enum{DG,DN,UG,UN}GraphKind; /*圖的型別：有向圖、有向網、無向圖和無向網*/
typedef struct ArcNode /*邊結點的型別定義*/
{
int adjvex; /*弧指向的頂點的位置*/
InfoPtr *info; /*與弧相關的資訊*/
struct ArcNode *nextarc; /*指示下一個與該頂點相鄰接的頂點*/
}ArcNode;
typedef struct VNode /*頭結點的型別定義*/
{
VertexType data; /*用於儲存頂點*/
ArcNode *firstarc; /*指示第一個與該頂點鄰接的頂點*/
}VNode,AdjList[MaxSize];
typedef struct /*圖的型別定義*/
{
AdjList vertex;
int vexnum,arcnum; /*圖的頂點數目與弧的數目*/
GraphKind kind; /*圖的型別*/
}AdjGraph;
（3）十字連結串列表示法（有向圖）
十字連結串列是有向圖的又一種鏈式儲存結構，它是將有向圖的鄰接表與逆鄰接連結串列結合起來的儲存結構表示。因此，在十字連結串列中，同樣包括表頭結點和邊結點。在十字連結串列中，將表頭結點稱為頂點結點，邊結點稱為弧結點。
有向圖的十字連結串列儲存結構可以用C語言描述如下：
#define MaxSize 50 /*最大頂點個數*/
typedef struct ArcNode /*弧結點的型別定義*/
{
int headvex,tailvex; /*弧的頭頂點和尾頂點位置*/
InfoPtr *info; /*與弧相關的資訊*/
struct *hlink,*tlink; /*指示弧頭和弧尾相同的結點*/
}ArcNode;
typedef struct VNode /*頂點結點的型別定義*/
{
VertexType data; /*用於儲存頂點*/
ArcNode *firstin,*firstout; /*分別指向頂點的第一條入弧和出弧*/
}VNode;
typedef struct /*圖的型別定義*/
{
VNode vertex[MaxSize];
int vexnum,arcnum; /*圖的頂點數目與弧的數目*/
}OLGraph;
（4）鄰接多重連結串列表示法（無向圖）
鄰接多重連結串列表示是無向圖的另一種鏈式儲存結構。在無向圖的鄰接表儲存表示中，雖然可以很容易對鄰接表進行操作，但是圖的每一條邊在鄰接表中需要儲存兩個結點，如果要檢查某個邊是否被訪問過，則需要在鄰接表中找到兩個結點。而鄰接多重表是將圖的一條邊用一個結點表示。
無向圖的多重連結串列儲存結構可以用C語言描述如下：
#define MaxSize 50 /*最大頂點個數*/
typedef struct EdgeNode /*邊結點的型別定義*/
{
int mark,ivex,jvex; /*訪問標誌和邊的兩個頂點位置*/
InfoPtr *info; /*與邊相關的資訊*/
struct *ilink,*jlink; /*指示與邊頂點相同的結點*/
}EdgeNode;
typedef struct VNode /*頂點結點的型別定義*/
{
VertexType data; /*用於儲存頂點*/
EdgeNode *firstedge; /*指向依附於頂點的第一條邊*/
}VexNode;
typedef struct /*圖的型別定義*/
{
VexNode vertex[MaxSize];
int vexnum,edgenum; /*圖的頂點數目與邊的數目*/
}AdjMultiGraph;