圖（graph）是一種非線性結構
圖的特點（多對多），頂點之間的關系是任意的，圖中任意兩個頂點之間都可能相關，頂點的前驅和後繼個數無限制。
圖：資料元素間存在多對多關系的資料結構，加上一組基本操作構成的抽象資料類型。
圖的基本術語
頂點：圖中的資料元素。
弧：若 <v, w>∈vr，則 <v, w> 表示從 v 到 w 的一條弧，且稱 v 為弧尾，稱 w 為弧頭，此時的圖稱為有向圖。
g1 = (v1, a1) v1 = {v1, v2, v3, v4}
a1 = {< v1, v2>, < v1, v3>, < v3, v4>, < v4, v1>}
邊：若 <v, w>∈vr 必有<w, v>∈vr，則以無序對 (v, w) 代表這兩個有序對，表示 v 和 w 之間的一條邊，此時的圖稱為無向圖。
g2 = (v2, e2) v2 = {v1, v2, v3, v4, v5}
e2 = {(v1, v2), (v1, v4), (v2, v3), (v2, v5) , (v3, v4), (v3, v5)}
無向圖中邊的取值範圍：0≤e≤n(n-1)/2。（用 n 表示圖中頂點數目，用 e 表示邊的數目。且不考慮頂點到其自身的邊。）
完全圖：有 n(n-1)/2 條邊的無向圖（即：每兩個頂點之間都存在着一條邊)稱為完全圖。
有向圖中弧的取值範圍：0≤e≤n(n-1)。（用 n 表示圖中頂點數目，用 e 表示弧的數目。且不考慮頂點到其自身的弧。）
有向完全圖：有 n (n - 1) 條弧的有向圖（即：每兩個頂點之間都存在着方向相反的兩條弧）稱為有向完全圖。
稀疏圖：含有很少條邊或弧的圖。
稠密圖：含有很多條邊或弧的接近完全圖的圖。
權：與圖的邊或弧相關的數，這些數可以表示從一個頂點到另一個頂點的距離或耗費。
網： 帶權的圖。
子圖：如果圖 g = (v, e) 和 g´= (v ´, e´)，滿足：v ´包含于v 且 e´包含于 e，則稱 g´為g 的子圖。
鄰接點：若 (v, v´) 是一條邊，則稱頂點 v 和 v´互為鄰接點，或稱 v 和 v´相鄰接；稱邊 (v, v´) 依附于頂點 v和 v´，或稱 (v, v´) 與頂點 v 和 v´ 相關聯。若 <v, v´> 是一條弧，則稱頂點 v 鄰接到 v´，頂點v´鄰接自頂點 v。并稱弧 <v, v´> 與頂點 v 和 v´ 相關聯。
度：無向圖中頂點 v 的度是和 v相關聯的邊的數目，記為：td(v)。
入度：有向圖中以頂點 v 為頭的弧的數目稱為 v 的入度，記為：id(v)。
出度：有向圖中以頂點 v 為尾的弧的數目稱為 v 的出度，記為：od(v)。
度：入度和出度之和，即：td(v) = id(v) + od(v)。
如果頂點 vi 的度為 td(vi)，則一個有 n 個頂點 e 條邊（弧）的圖，滿足如下關系：
路徑：從頂點 v 到 v´ 的路徑是一個頂點序列。對于有向圖，路徑也是有向的。
路徑長度：路徑上邊或弧的數目。
回路（環）：第一個頂點和最後一個頂點相同的路徑。
簡單路徑：序列中頂點不重複出現的路徑。
連通：從頂點 v 到 v´ 有路徑，則說 v 和 v´ 是連通的。
連通圖：圖中任意兩個頂點都是連通的。
連通分量：無向圖的極大連通子圖（該子圖是 連通子圖，g中再加一個頂點就不連通，再減一條邊就不極大）；任何連通圖的連通分量隻有一個，即其本身；非連通圖有多個連通分量（非連通圖的每一個連通部分）。
強連通圖： 任意兩個頂點都連通的有向圖。
強連通分量：有向圖的極大強連通子圖（該子圖是強連通子圖，圖中再加一個頂點就不連通，再減一條邊就不極大）；任何強連通圖的強連通分量隻有一個，即其本身；非強連通圖有多個強連通分量。
連通圖的生成樹：包含無向圖g 所有頂點的的極小連通子圖（該子圖是g 的連通子圖，在該子圖中删除任何一條邊，子圖不再連通；加入一條邊，則子圖一定有環。 ）一個圖可以有許多棵不同的生成樹。
所有生成樹具有以下共同特點：
1、生成樹的頂點個數與圖的頂點個數相同；
2、生成樹是圖的極小連通子圖；
3、一個有 n 個頂點的連通圖的生成樹有 n-1 條邊；
4、生成樹中任意兩個頂點間的路徑是唯一的；
5、在生成樹中再加一條邊必然形成回路。
6、含 n 個頂點 n-1 條邊的圖不一定是生成樹。
（無向圖） 生成森林：由若幹棵生成樹組成，含有圖中全部頂點，但隻有足以構成若幹棵不相交的生成樹的邊。
有向樹：如果一個有向圖恰有一個頂點的入度為 0 ，其餘頂點的入度均為 1 ，則是一棵有向樹。
有向圖的生成森林：由若幹棵有向樹組成，含有圖中全部頂點，但隻有足以構成若幹棵不相交的有向樹的弧。
圖的存儲結構
圖的存儲結構要儲存兩類資訊：
1)頂點的資料
2)頂點間的關系
順序存儲：任意兩頂點都可能有聯系，不能用元素在存儲區中的實體位置來表示元素之間的關系。
多重連結清單：與樹類似，浪費存儲單元；操作不友善。
數組表示法（鄰接矩陣表示法）
一個有 n 個頂點的圖，可用兩個數組存儲。其中一個一維數組存儲資料元素（頂點）的資訊，另一個二維數組（鄰接矩陣）存儲資料元素之間的關系（邊或弧）的資訊。
鄰接矩陣：設 g = (v, vr) 是具有 n 個頂點的圖，頂點的順序依次為 {v1, v2, …, vn}，則 g 的鄰接矩陣是具有如下性質的 n 階方陣：
比如：
使用鄰接矩陣存儲
再比如
使用鄰接矩陣
特點：
1、無向圖的鄰接矩陣對稱，可壓縮存儲；有 n 個頂點的無向圖所需存儲空間為 n(n-1)/2。
2、有 n 個頂點的有向圖所需存儲空間為n²，用于稀疏圖時空間浪費嚴重。占用存儲空間隻與它的頂點數有關，與邊數無關；适用于邊稠密的圖；
3、無向圖中頂點 vi 的度 td(vi) 是鄰接矩陣中第 i 行 1 的個數。
4、有向圖中：頂點 vi 的出度是鄰接矩陣中第 i 行 1 的個數。 頂點 vi 的入度是鄰接矩陣中第 i 列 1 的個數。
網的鄰接矩陣可定義為：
使用鄰接矩陣表示
代碼如下：
鄰接表（類似于樹的孩子連結清單表示法）
鄰接點域，存放與 vi 鄰接的頂點在表頭數組中的位置。
鍊域，訓示下一條邊或弧。
表頭結點之後的連結清單，表示的是該表頭的結點代表的圖的頂點的鄰接的頂點，其中資料域的數字代表的是表頭數組的下标，也就是頂點。
若無向圖中有 n 個頂點、e 條邊，則其鄰接表需 n 個頭結點和 2e 個表結點。适宜存儲稀疏圖。
無向圖中頂點 vi 的度為第 i 個單連結清單中的結點數。
建立無向鄰接表
思想：如何給存儲結構指派
1.建立頂點數組。讀入各頂點資料vextex，将link域賦null。
2.建立各頂點的鄰接表。
讀入頂點對<i,j>, 生成兩個節點，分别插入頂點j,i的鄰接表的頭部。直至處理完所有的邊。
時間複雜度o（n+e）
辛苦的勞動，轉載請注明出處，謝謝……
http://www.cnblogs.com/kubixuesheng/p/4399408.html