合适的存圖方式往往能事半功倍，這裡介紹三種方式：鄰接矩陣、鄰接表、鍊式前向星。
鄰接矩陣
1）存圖思想
用一個矩陣來記錄一個圖，矩陣第 i 行第 j 列的值就表示頂點 i 到頂點 j 的權值
2 代碼實作
1 #include<stdio.h>
2 #include<string>
3 const int V = 1000; //最大頂點數
4 int mat[V][V];
5
6 int main()
7 {
8 //初始化操作
9 //假設權值為0表示沒有該邊
10 memset(mat, 0, sizeof(mat));
11
12 //增加邊
13 //增加頂點i到頂點j的權值為w的邊
14 mat[i][j] = w;
15
16 //删除邊
17 mat[i][j] = 0;
18
19 //查詢邊
20 mat[i][j]
21 } 3）優點
a.簡單易學
b.對已确定的邊進行操作效率高：對已确定的邊（兩頂點已知），進行增加、删除（或更改權值）、查詢，都是O(1)的時間複雜度
4)缺點
a.過高的空間複雜度：這幾乎是一個緻命的缺點，對于頂點數V,鄰接矩陣存圖的空間複雜度高達O(V * V),頂點數高于10000就不用考慮了。對于稀疏矩陣，太浪費記憶體了
鄰接表
對每個頂點，使用不定長的連結清單來存儲從該點出發的所有邊的情況，第 i 個連結清單的第 j 個值就是頂點 i 到頂點 j 的權值。
2）代碼實作
1 #include<stdio.h>
2 #include<vector>
3 #include<string>
4 using namespace std;
5
6 const int V = 100000;
7 vector<int>e[V]; //定義了V個連結清單
8
9 int main()
10 {
11 int i,j,k;
12 //鄰接連結清單的初始化
13 //将起點為"i "的連結清單清空
14 e[i].clear();
15
16 //增加邊
17 //增加頂點"i"到頂點"j"的邊
18 e[i].push_back(j);
19
20 //查詢邊值
21 //查詢以"i"為起點的第"j"條邊
22 e[i][j];
23
24 //尋找權值為k的邊
25 for (int j = 0; j < (int)e[i].size(); j++)
26 {
27 if (e[i][j] == k)
28 {
29 //do something
30 }
31 }
32
33 } a.較為簡單易學：數組轉連結清單，定長轉不定長
b.記憶體使用率較高：對于頂點數V、邊數E,空間複雜度為O(V + E),能較好的處理稀疏圖
c.對不确定的邊操作比較友善：比如，要周遊從某點出發的某條邊，不會像鄰接矩陣一樣可能周遊到不存在的邊
4）缺點
a.重邊不好處理：判重比較麻煩，還要周遊已有的邊，不能直接判斷；一般情況下使用鄰接表存圖是會存儲重邊的，不會做重邊的判斷
b.對确定邊效率不高：比如對于給定
i->j
的邊要進行查詢或修改等操作隻有通過周遊這種方式找到
鍊式前向星
主要的資料結構是邊數組（存儲邊的數組），當然想要完美表示圖，光有一個邊集數組還不夠，還要有一個數組每一個點的第一條邊。同時，每一條邊都需要存儲接下來一條邊的“指針”
1 #include<stdio.h>
2 #include<string>
3 const int V = 100000;
4 const int E = 100000;
5
6 //邊結構體的定義
7 struct Edge
8 {
9 int to; //該邊的另一個頂點
10 int w; //該邊的權值
11 int next; //下一條邊的數組下标
12 };
13
14 //head[i]表示頂點i的第一條邊的數組下标，"-1"表示頂點i沒有邊
15 int head[V];
16 Edge edge[E];
17
18
19 //增加邊
20 //新增加邊"a -> b",該邊的權值為w,數組下标為"id"
21 inline void AddEdge(int a, int b, int w, int id)
22 {
23 edge[id].to = b;
24 edge[id].w = w;
25 edge[id].next = head[a]; // 新增的邊要成為頂點`a`的第一條邊，而不是最後一條邊
26 head[a] = id; //類似于連結清單的頭插法，最後一條邊指向"-1"
27 return;
28 }
29 int main()
30 {
31 int a,b,w;
32 //鍊式前向星的初始化
33 //隻需要初始化頂點數組就可以了
34 memset(head, -1, sizeof(head));
35
36 //周遊從a出發的所有邊
37 for (int i = head[a]; i != -1; i = edge[i].next)
38 {
39 //do something
40 if(edge[i].to == b) //找到邊a -> b
41 if(edge[i].w == w) //找到權值為w的邊
42 }
43 } a.記憶體使用率高：相比
vector
實作的鄰接表而言，可以準确開辟最多邊數的記憶體，不像
vector
實作的鄰接表有爆記憶體的風險
b..對不确定的邊操作比較友善：和鄰接表一樣不會周遊到不存在的邊
a.操作複雜一點：要求比較熟練，不熟練寫起來比較慢
b.重邊不好處理：這點與鄰接表一樣，隻有通過周遊判重
c.對确定邊操作效率不高：也與鄰接表一樣，不能通過兩點馬上确定邊，隻能周遊查找
總結
對于鄰接矩陣，由于記憶體消耗局限性的，幾乎隻能用于簡單的圖論題
鄰接表存圖是最為常見的一種方法，絕大部分采用C++STL中的
vector
實作，一般情況下大部分圖論題目都能使用該存圖方式。
而鍊式前向星是一種較好的用來代替鄰接表的資料結構，在鄰接表存圖不能使用時可以使用，幾乎可以用于全部圖論題目。如果熟練掌握，可以作為主要的存圖方法。
參考連結：izqt.github.io/2015/07/21/ACM圖論之存圖方式
個性簽名：時間會解決一切