圖的儲存
2023-04-20 06:00:33
所謂圖（graph），是圖論中基本的數學物件，包括一些頂點，和連線頂點的邊。
圖可以分為有向圖和無向圖，有向圖中的邊是有方向的，而無向圖的邊是雙向連通的。
-
鄰接矩陣 (適用於稠密圖)
用一個二維陣列來記錄各個點之間的關係，若u到v之間有一條邊則可用map[u][v]=1來表示，具體如下
對應的無向圖為
對於帶權圖 將1改成權值即可
鄰接矩陣的優點顯而易見：簡單好寫，查詢速度快。但缺點也很明顯：空間複雜度太高了。 n個點對應大小 n^2的陣列，如果點的數量達到10000，這種方法就完全不可行了。
-
鄰接表
首先，我們用一個結構體vector儲存每個邊的起點和終點，然後用一個二維vector儲存邊的資訊。
用map[a][b]=c 來表示頂點為a的第b條邊是c號邊
以下面為例:
8 9
1 2 //0號邊
1 3 //1號邊
1 4 //2號邊
2 5 //3號邊
2 6 //4號邊
3 7 //5號邊
4 7 //6號邊
4 8 //7號邊
7 8 //8號邊
最終二維vector中儲存的是如下資訊
0 1 2 //1號頂點連著0、1、2號邊
3 4 //2號頂點連著3、4號邊
5 //3號頂點連著5號邊
6 7 //4號頂點連著6、7號邊
//5號頂點沒有邊
//6號頂點沒有邊
8 //7號頂點連著8號邊
//8號頂點沒有邊
1 #include<iostream>
2 #include<algorithm>
3 #include<vector>
4 using namespace std;
5
6 struct edge {
7 int st, ed;
8 };
9 vector <int> map[100001];
10 vector <edge> vec;
11 int main() {
12
13 int n, m;
14 cin >> n >> m;
15 for (int i = 0; i < m; i++) {
16 int st, ed;
17 cin >> st >> ed;
18 vec.push_back({ st, ed }); //初始化存邊的s陣列
19 }
20
21 for (int i = 0; i < m; i++)
22 map[vec[i].st].push_back(i);
23 //初始化map陣列，vec[i].st表示頂點，在該頂點加入其對應的邊
24
25 return 0;
26 }
如何去遍歷呢？
x表示頂點
map[x].size()表示該頂點具有邊的個數
map[x][i]表示x頂點的第i條邊是哪一條邊
vec[map[x][i]].ed 表示x頂點的第i條邊的邊的終點
以該圖為例:
map[1][0]表示 0 號邊 map[2][0]表示第3條邊 map[4[1]表示第8條邊
那麼vec[map[1][0]].ed就等於2號頂點
1 void dfs(int x) {
2 cout << x<<" ";
3
4 for (int i = 0; i < map[x].size(); i++)
5 {
6 int j = vec[map[x][i]].ed;
7 if (!st[j])
8 {
9 st[j] = 1;
10 dfs(j);
11 }
12 }
13 }
-
鏈式前向星 (h陣列初始化為-1)
idx是邊的編號，a是邊的起點，b是邊的終點
e[idx] 存idx號邊指向的點。
h[a] 存從a號點出發的某一條邊的編號
ne[idx] 存idx號邊(起點為a)的上一條邊（也是以a為起點的）
i=ne[i]迴圈遍歷所有從a出發的邊
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
輸出鄰接表:
1:->4->7->2
2:->5->8->1
3:->9->4
4:->6->3->1
5:->2
6:->4
7:->1
8:->2
9:->3
對比原圖
節點的編號是指上圖所畫的樹中節點的值，範圍是從1->n,編號用e[i]陣列儲存。
節點的下標指節點在陣列中的位置索引，陣列之間的關係就是通過下標來建立連線，下標用idx來記錄。idx範圍從0開始，如果idx==-1表示空。
e[i]的值是編號，是下標為i節點的編號。
ne[i]的值是下標，是下標為i的節點的next節點的下標。
h[i]儲存的是下標，是編號為i的節點的next節點的下標，比如編號為1的節點的下一個節點是2，那麼我輸出e[h[1]]就是2。