一 圖的定義定義：圖（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的數據域 ， 存儲權值信息即可，如下圖所示 。

文章插圖
【數據結構之圖的基本概念 vj是什么意思】

• 屬狗的今年多大
• 四時之風的意思
• 愛護花草樹木的標語
• 霜葉紅于二月花
• 墨西哥人吃什么 墨西哥人的飲食習慣
• 潮汕清蒸東星斑的做法 潮汕清蒸東星斑怎么做
• 潮汕清蒸鲅魚最正宗的做法 潮汕最正宗的清蒸鲅魚怎么做
• 糖醋黃魚的做法 糖醋黃魚怎么做
• 打鹵面怎么保鮮 蒸好的鹵面怎么保存過夜
• 祖父的園子教學設計