編輯
一、圖定義
圖是一種較線性表和樹更為複雜的數據結構，其定義為:
圖是由頂點的有窮非空集合與頂點之間邊的集合構成，通常表示為:G(V, E), G表示一個圖，V表示圖中頂點的集合，E表示頂點之間邊的集合。
如下，就是一個圖：
編輯
二、圖術語瞭解
圖中數據元素我們稱之為頂點，圖中任意兩個頂點都可能存在關係，頂點之間關係用邊來表示。
若兩個頂點Vi與Vj之間的邊沒有方向，則稱這條邊為無向邊, 用(Vi，Vj)表示，注意這裡是圓括號
如果圖中任意頂點之間都是無向邊，則稱該圖為無向圖，在無向圖中任意兩個頂點之間都存在邊，則稱該圖為無向完全圖,上圖就是一個無向完全圖。
若兩個頂點Vi與Vj之間的邊有方向，則稱這條邊為有向邊，也稱作弧, 用
如果圖中任意頂點之間都是有向邊，則稱該圖為有向圖，在有向圖中任意兩個頂點之間都存在方向互為相反的兩條弧，則稱該圖為有向完全圖，如下圖：
編輯
有些圖的邊或者弧具有與其相關的數字，這種與圖或弧相關的數字叫做權值。
在無向圖中如果兩個頂點之間有路徑，則稱這兩個頂點是聯通的，如果圖中任意兩個頂點都是聯通的，則稱圖是連通圖。
在無向圖中頂點的邊數叫做頂點的度。
在有向圖中頂點分為出度和入度，入度就是指向自己的邊數，而出度則相反。
如下圖：
A結點：出度為3，入度為1
編輯
B結點：出度為1，入度為2
以上講解了一些圖的基本術語，沒什麼難度，大概瞭解一下就可以了。
三、圖的存儲
圖的結構比較複雜，任意兩個元素都可能產生關係，所以一般存儲結構無法滿足。
鄰接矩陣存儲方式
圖是由頂點和邊(或者弧)組成的，可以單獨存儲頂點和邊，頂點簡單，可以用一位數組來存儲，但是邊呢?邊就是兩個頂點之間的關係，可以用一個二維數組來存儲，這種存儲方式就是鄰接矩陣存儲方式。
鄰接矩陣存儲方式就是用兩個數組來存儲，一個一維數組，一個二維數組，一維數組用來存儲頂點，二維數組用來存儲頂點之間的關係，也就是邊或者弧。
無向圖鄰接矩陣存儲方式：
如下無向圖：
編輯
一維數組存儲頂點數組：
編輯
二維數組存儲頂點(邊，弧)之間關係：
編輯
無向圖邊之間關係的二維數組用0或者1來填充，如果兩個頂點之間直接連通則為1，不直接連通則為0，有個注意點就是直接不是間接連通。比如A與B之間直接連通所以填1，而A與D之間不直接連通則為0.
有向圖鄰接矩陣存儲方式：
如下有向圖：
編輯
存儲頂點的一維數組與上面一樣
二維數組存儲頂點(邊，弧)之間關係：
編輯
無向圖中兩個頂點之間有直接相連的邊則為1，而有向圖中如上圖中B與C之間，有B指向C的邊則為1，而沒有C指向B的邊則為0。
帶權鄰接矩陣存儲方式：
如下圖有向帶權圖：
編輯
存儲頂點的一維數組與上面一樣
二維數組存儲頂點(邊，弧)之間關係：
編輯
很簡單，就是將有向圖中1替換為對應權值，此外，如圖中A,C之間，沒有A指向C的邊則用∞表示。
對於帶權有向圖將各個頂點理解成一個個村莊，邊就是村莊之間的路，權值就是距離，AB村莊之間有A指向B的路程，並且路程是100，則二維數組中直接用100表示，BA之間沒有路，則用無窮大表示，代表永遠不可達，自己到自己就是0了。
