圖是一種複雜的非線性結構，通常用來表示和存儲具有“多對多”關系的資料，是資料結構中非常重要的一種結構。這篇文章将帶你回憶圖相關的最重要的概念以及圖的存儲結構。
線上性結構中，資料元素之間滿足唯一的線性關系，每個資料元素(除第一個和最後一個外)隻有一個直接前趨和一個直接後繼；
在樹形結構中，資料元素之間有着明顯的層次關系，并且每個資料元素隻與上一層中的一個元素(parent node)及下一層的多個元素(孩子節點)相關；
而在圖形結構中，節點之間的關系是任意的，圖中任意兩個資料元素之間都有可能相關。
圖(Graph)G由頂點集合V(G)和邊集合E(G)構成。例如，
上圖中，代表邊的頂點對是無序的，則稱G為無向圖。用圓括号序偶表示無向邊。例如可以用(0，1)表示頂點0和1之間的邊。
如果表示邊的頂點對是有序的，則稱G為有向圖。用尖括号序偶表示有向邊。
一圖的基本術語端點和鄰接點
無向圖：若存在一條邊(i，j) 的頂點i和頂點j為端點，它們互為鄰接點。
有向圖：若存在一條邊 的頂點i為起始端點(簡稱為起點)，頂點j為終止端點(簡稱終點)，它們互為鄰接點。
頂點的度、入度和出度
無向圖：以頂點i為端點的邊數稱為該頂點的度。
有向圖：以頂點i為終點的入邊的數目，稱為該頂點的入度。以頂點i為始點的出邊的數目，稱為該頂點的出度。一個頂點的入度與出度的和為該頂點的度。
若一個圖中有n個頂點和e條邊，每個頂點的度為di(0≤i≤n-1)，則有：
完全圖
無向圖：每兩個頂點之間都存在着一條邊，稱為完全無向圖， 包含有n(n-1)/2條邊。
有向圖：每兩個頂點之間都存在着方向相反的兩條邊，稱為完全有向圖，包含有n(n-1)條邊。
稠密圖、稀疏圖、子圖
當一個圖接近完全圖時，則稱為稠密圖。相反，當一個圖含有較少的邊數(即當e<稀疏圖。
路徑和路徑長度
設有兩個圖G=(V，E)和G'=(V'，E')，若V'是V的子集，即V'屬于V，且E'是E的子集，即E'屬于E，則稱G'是G的子圖。在一個圖G=(V，E)中，從頂點i到頂點j的一條路徑(i,i1...,ij )。其中所有的(ix,iy)∈E(G)，或者∈E(G)。路徑長度是指一條路徑上經過的邊的數目。若一條路徑上除開始點和結束點可以相同外，其餘頂點均不相同，則稱此路徑為簡單路徑。
回路或環
若一條路徑上的開始點與結束點為同一個頂點，則此路徑被稱為回路或環。開始點與結束點相同的簡單路徑被稱為簡單回路或簡單環。
連通、(強)連通圖和(強)連通分量
無向圖：若從頂點i到頂點j有路徑，則稱頂點i和j是連通的。若圖中任意兩個頂點都連通，則稱為連通圖，否則稱為非連通圖。無向圖G中的極大連通子圖稱為G的連通分量。顯然，任何連通圖的連通分量隻有一個，即本身，而非連通圖有多個連通分量。
有向圖：若從頂點i到頂點j有路徑，則稱從頂點i到j是連通的。若圖G中的任意兩個頂點i和j都連通，即從頂點i到j和從頂點j到i都存在路徑，則稱圖G是強連通圖。有向圖G中的極大強連通子圖稱為G的強連通分量。顯然，強連通圖
隻有一個強連通分量，即本身。非強連通圖有多個強連通分量。
在一個非強連通中找強連通分量的方法。
① 在圖中找有向環。
② 擴充該有向環：如果某個頂點到該環中任一頂點有路徑，并且該環
中任一頂點到這個頂點也有路徑，則加入這個頂點。
權和網
圖中每一條邊都可以附帶有一個對應的數值，這種與邊相關的數值稱為權。權可以表示從一個頂點到另一個頂點的距離或花費的代價。邊上帶有權的圖稱為帶權圖，也稱作網。
二圖的存儲結構
圖的存儲結構用來存儲每個頂點的資訊以及存儲每條邊的資訊。主要的兩種存儲結構是鄰接矩陣和鄰接表。
鄰接矩陣存儲方法
鄰接矩陣是表示頂點之間相鄰關系的矩陣。鄰接矩陣的主要特點：一個圖的鄰接矩陣表示是唯一的，特别适合于稠密圖的存儲。鄰接矩陣的存儲空間為O(n^2)。
設G=(V，E)是具有n(n＞0)個頂點的圖，頂點的編号依次為0～n-1。G的鄰接矩陣A是n階方陣，其定義如下：
(1)如果G是無向圖，則：A[i][j]=1：若(i,j)∈E(G)， 0:其他；
(2)如果G是有向圖，則：A[i][j]=1：若∈E(G)， 0:其他；
(3)如果G是帶權無向圖，則：A[i][j]= wij：若i≠j且(i,j)∈E(G)， 0：i=j ，∞：其他；
(4)如果G是帶權有向圖，則：A[i][j]= wij：若i≠j且∈E(G)， 0：i=j ，∞：其他。
圖的鄰接矩陣存儲類型定義如下：
#define MAXV // 聲明頂點的類型typedef struct{ int no; //頂點編号InfoType info; //頂點其他資訊} VertexType;// 聲明的鄰接矩陣類型typedef struct // 圖的定義{ int edges[MAXV][MAXV]; //鄰接矩陣int n，e; //頂點數，邊數VertexType vexs[MAXV]; //存放頂點資訊} MGraph;
鄰接表存儲方法
圖的鄰接表存儲方法是一種順序配置設定與鍊式配置設定相結合的存儲方法。對圖中每個頂點i建立一個單連結清單，将頂點i的所有鄰接點鍊起來。并且為每個單連結清單上添加一個表頭節點(表示頂點資訊)。并将所有表頭節點構成一個數組，下标為i的元素表示頂點i的表頭節點。鄰接表的特點如下：鄰接表表示不唯一。特别适合于稀疏圖存儲。鄰接表的存儲空間為O(n+e)。
圖的鄰接表存儲類型定義如下：
// 聲明邊節點類型typedef struct ANode{ int adjvex; //該邊的終點編号struct ANode *nextarc; //指向下一條邊的指針InfoType info; //該邊的權值等資訊} ArcNode;// 聲明鄰接表頭節點類型typedef struct Vnode{ Vertex data; //頂點資訊ArcNode *firstarc; //指向第一條邊} VNode;//聲明圖鄰接表類型typedef struct{ VNode adjlist[MAXV] ; //鄰接表int n,e; //圖中頂點數n和邊數e} ALGraph;
思考：
圖的鄰接矩陣和鄰接圖兩者存儲結構各有什麼優缺點？
end
點選“❀在看”，讓更多朋友們看到吧~