一 圖的定義
定義：圖（Graph）是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G(V,E)，其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合，
在圖中需要注意的是：
（1）線性表中我們把資料元素叫元素，樹中將資料元素叫結點，在圖中資料元素，我們則稱之為頂點（Vertex），
（2）線性表可以沒有元素，稱為空表；樹中可以沒有節點，稱為空樹；但是，在圖中不允許沒有頂點（有窮非空性），
（3）線性表中的各元素是線性關系，樹中的各元素是層次關系，而圖中各頂點的關系是用邊來表示（邊集可以為空），
二 圖的基本概念
（1）無向圖
如果圖中任意兩個頂點之間的邊都是無向邊（簡而言之就是沒有方向的邊），則稱該圖為無向圖（Undirected graphs），
（2）有向圖
如果圖中任意兩個頂點之間的邊都是有向邊（簡而言之就是有方向的邊），則稱該圖為有向圖（Directed graphs），
（3）完全圖
①無向完全圖：在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖，（含有n個頂點的無向完全圖有(n×(n-1))/2條邊）如下圖所示：
②有向完全圖：在有向圖中，如果任意兩個頂點之間都存在方向互為相反的兩潭訓，則稱該圖為有向完全圖，（含有n個頂點的有向完全圖有n×(n-1)條邊）如下圖所示：
PS：當一個圖接近完全圖時，則稱它為稠密圖（Dense Graph），而當一個圖含有較少的邊時，則稱它為稀疏圖（Spare Graph），
（4）頂點的度
頂點Vi的度（Degree）是指在圖中與Vi相關聯的邊的條數，對于有向圖來說，有入度（In-degree）和出度（Out-degree）之分，有向圖頂點的度等于該頂點的入度和出度之和，
（5）鄰接
①若無向圖中的兩個頂點V1和V2存在一條邊(V1,V2)，則稱頂點V1和V2鄰接（Adjacent）；
②若有向圖中存在一條邊<V3,V2>，則稱頂點V3與頂點V2鄰接，且是V3鄰接到V2或V2鄰接直V3；
PS：無向圖中的邊使用小括號“()”表示，而有向圖中的邊使用尖括號“<>”表示，
（6）路徑
在無向圖中，若從頂點Vi出發有一組邊可到達頂點Vj，則稱頂點Vi到頂點Vj的頂點序列為從頂點Vi到頂點Vj的路徑（Path），
（7）連通
若從Vi到Vj有路徑可通，則稱頂點Vi和頂點Vj是連通（Connected）的，
（8）權
有些圖的邊或弧具有與它相關的數字，這種與圖的邊或弧相關的數叫做權（Weight），
三、圖的存盤結構
圖的存盤結構除了要存盤圖中的各個頂點本身的資訊之外，還要存盤頂點與頂點之間的關系，因此，圖的結構也比較復雜，常用的圖的存盤結構有鄰接矩陣和鄰接表等，
3.1 鄰接矩陣表示法
圖的鄰接矩陣（Adjacency Matrix）存盤方式是用兩個陣列來表示圖，一個一維陣列存盤圖中頂點資訊，一個二維陣列（稱為鄰接矩陣）存盤圖中的邊或弧的資訊，
我們可以設定兩個陣列，頂點陣列為vertex[4]={v0,v1,v2,v3}，邊陣列arc[4][4]為上圖右邊這樣的一個矩陣，對于矩陣的主對角線的值，即arc[0][0]、arc[1][1]、arc[2][2]、arc[3][3]，全為0是因為不存在頂點的邊，
不足：由于存在n個頂點的圖需要n*n個陣列元素進行存盤，當圖為稀疏圖時，使用鄰接矩陣存盤方法將會出現大量0元素，這會造成極大的空間浪費，這時，可以考慮使用鄰接表表示法來存盤圖中的資料，
3.2 鄰接表表示法
首先，回憶我們在線性表時談到，順序存盤結構就存在預先分配記憶體可能造成存盤空間浪費的問題，于是引出了鏈式存盤的結構，同樣的，我們也可以考慮對邊或弧使用鏈式存盤的方式來避免空間浪費的問題，
鄰接表由表頭節點和表節點兩部分組成，圖中每個頂點均對應一個存盤在陣列中的表頭節點，如果這個表頭節點所對應的頂點存在鄰接節點，則把鄰接節點依次存放于表頭節點所指向的單向鏈表中，
（1）無向圖：下圖所示的就是一個無向圖的鄰接表結構，
從上圖中我們知道，頂點表的各個結點由data和firstedge兩個域表示，data是資料域，存盤頂點的資訊，firstedge是指標域，指向邊表的第一個結點，即此頂點的第一個鄰接點，邊表結點由adjvex和next兩個域組成，adjvex是鄰接點域，存盤某頂點的鄰接點在頂點表中的下標，next則存盤指向邊表中下一個結點的指標，例如：v1頂點與v0、v2互為鄰接點，則在v1的邊表中，adjvex分別為v0的0和v2的2，
PS：對于無向圖來說，使用鄰接表進行存盤也會出現資料冗余的現象，例如上圖中，頂點V0所指向的鏈表中存在一個指向頂點V3的同事，頂點V3所指向的鏈表中也會存在一個指向V0的頂點，
（2）有向圖：若是有向圖，鄰接表結構是類似的，但要注意的是有向圖由于有方向的，因此，有向圖的鄰接表分為出邊表和入邊表（又稱逆鄰接表），出邊表的表節點存放的是從表頭節點出發的有向邊所指的尾節點；入邊表的表節點存放的則是指向表頭節點的某個頂點，如下圖所示，
（3）帶權圖：對于帶權值的網圖，可以在邊表結點定義中再增加一個weight的資料域，存盤權值資訊即可，如下圖所示，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/65027.html
標籤：C
上一篇：資料結構入門-線性結構
下一篇：圖的深度遍歷和廣度遍歷