一、樹與圖的存盤方式
樹（無環連通圖）、圖的存盤：
? 有向圖：
a ---> b? 無向圖：
a ---> b,b ---> a無向圖可以看作是特殊的有向圖！
1.鄰接矩陣
稠密圖一般使用鄰接矩陣存盤，空間復雜度達到（n * n）
存盤方式：
?
g[b][b]存盤a ---> b的資訊，如果有權值c則g[b][b] = c；如果沒有權值則為bool，表示是否連通注：鄰接矩陣不能存盤重邊，一般只保留一條（最短的：如樸素dijkstra演算法和prim演算法）
2.鄰接表
鄰接表適用于存盤稀疏圖，是一種最常用的圖存盤方式：對于每一個節點，都開一個單鏈表（類似拉鏈法）存盤該節點可以訪問到的點，存盤次序無關緊要，
插入邊：
初始化鏈表：
memset(h, -1, sizeof h);
插入操作：
不帶權值：
//鄰接表
int h[N], e[M], ne[M], idx;// M = 2 * N
//插入邊a ---> b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
帶權值：
int h[N], w[N], e[N], ne[N], idx;
void add(int a, int b, int c) // 添加一條邊a->b，邊權為c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a]. h[a] = idx ++;
}
二、樹與圖的遍歷方式
1.深度優先遍歷
（1）圖的深度優先遍歷框架模板：
//u為節點編號
void dfs(int u){
st[u]=true; // 標記一下，記錄為已經被搜索過了
// 遍歷u的鄰接點
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];//拿到出邊的對應的節點編號
if(!st[j])//如果未被訪問過，繼續深搜
{
dfs(j);
}
}
}
（2）例題：樹的重心
【參考代碼】
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
int n;
int h[N], e[M], ne[M], idx;
int ans = N;
bool st[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx, idx ++;
}
//回傳以u為根節點的子樹中節點的個數，包括u節點
int dfs(int u)
{
st[u] = true;// 標記一下，已經搜索過
//size是表示將u點去除后，剩下的子樹中數量的最大值；
//sum表示以u為根的子樹的點的多少，初值為1，因為已經有了u這個點
int size = 0, sum = 1;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];//拿到出邊的對應的節點編號
if(!st[j])
{
int s = dfs(j); // 當前子樹的大小（//s是以j為根節點的子樹中點的數量）
size = max(size, s);// 取子樹種節點數較大者
sum += s;
}
}
//n-sum表示的是減掉u為根的子樹，整個樹剩下的點的數量
size = max(size, n - sum);
ans = min(ans, res);
return sum;
}
int main()
{
cin >> n;
//初始化鏈表
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);//無向圖
}
//從第一個節點開始搜索
dfs(1);
printf("%d\n", ans);
return 0;
}
2.廣度優先遍歷
圖寬搜的框架和前面BFS的框架基本一模一樣，只是將圖的結構擴展到寬搜框架里，前面的BFS是根據具體題目來擴展點，圖的話采用鄰接表存盤圖，從1號節點編號開始，擴展的是每一個點的臨邊，
（1）圖的廣度優先遍歷框架模板：
1. queue <---- 1號點
2. while(佇列不為空)
{
t <---隊頭
彈出隊頭
擴展隊頭元素（擴展t的所有鄰接點j）
{
獲取鄰接點（編號）j
if(j未遍歷，符合條件)// 第一次遍歷才是最短路徑
{
queue <----- j入隊// （鄰接節點）
更新距離 //d[x] = d[t]++
}
}
}
3. 最后隊為空，結束
（2）例題：圖中點的層次
給定一個 n 個點 mm條邊的有向圖，圖中可能存在重邊和自環，
所有邊的長度都是 1，點的編號為 1～n，
請你求出 1號點到 n 號點的最短距離，如果從 1 號點無法走到 n 號點，輸出 ?1，
輸入格式
第一行包含兩個整數 n 和 m，
接下來 m 行，每行包含兩個整數 a 和 b，表示存在一條從 a 走到 b 的長度為 1 的邊，
輸出格式
輸出一個整數，表示 1 號點到 n 號點的最短距離，
資料范圍
1≤n,m≤105
輸入樣例：
4 5 1 2 2 3 3 4 1 3 1 4輸出樣例：
1
【參考代碼】
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int d[N];//存盤點到起點的距離
int n, m;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int bfs()
{
//初始化距離，且起用于判斷是否訪問過
memset(d, -1, sizeof d);
//1.一號節點（編號）入隊，設定距離
queue<int>q;
q.push(1);
d[1] = 0;
//2.佇列不為空
while(q.size())
{
//2.1拿到隊頭節點，隊頭出隊
auto t = q.front();
q.pop();
//2.2擴展隊頭元素（t的所有鄰接節點）
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];//得到鄰接節點j
if(d[j] == -1)//如果j節點沒有被訪問過
{
q.push(j);//入隊
d[j] = d[t] + 1;//更新距離
}
}
}
//3.回傳結果
return d[n];
}
int main()
{
cin >> n >> m;
//初始化鏈表
memset(h, -1, sizeof h);
while (m -- )
{
int a, b;
cin >> a >> b;
add(a, b);
}
cout << bfs();
return 0;
}
（3）圖廣搜的應用——拓撲排序
基本介紹：
拓撲序列：在一個有向圖無環中，對所有的節點進行排序，要求沒有一個節點指向它前面的節點，即，所有的邊從前指向后！
注：無向圖沒有拓撲序列
入度：一個點有多少條進來（指向自己）的邊
出度：一個點有多少條出去（指向其它點）的邊
重要結論性質：一個有向無環圖至少存在一個入度為0的節點！
求解步驟：
（1）先統計好圖中所有點的入度情況
（2）找到圖中入度為0的節點，將它刪去，由它發射出來的所有邊也要刪掉，即它指向的鄰接節點度數-1
（3）將刪去節點后剩下的圖，繼續按（2）的規則繼續刪節點，
按照節點被洗掉的順序，依次把這些被洗掉的節點記錄要一個序列里邊，當圖中所有節點被洗掉后，那么這個序列就是一個拓撲序列了！
注：當同時出現兩個或以上入度為0的節點時，拓撲序列結果不唯一！
基本BFS框架：
bool topsort()
{
1. queue <---- 所有度為0的點
2. while queue不為空
{
t <---- 隊頭
彈出隊頭
列舉t所有的出邊 t ---> j
{
刪掉出邊 t ---> j: d[j] --;// 入度-1
if(d[j] == 0)// 當節點j入度為0時，入隊
queue <---- j
}
}
如果有n - 1個節點入隊的話，說明是拓撲序列回傳true，否則不是回傳false
}
例題：
給定一個 n 個點 m 條邊的有向圖，點的編號是 1 到 n，圖中可能存在重邊和自環，
請輸出任意一個該有向圖的拓撲序列，如果拓撲序列不存在，則輸出 ?1，
若一個由圖中所有點構成的序列 AA 滿足：對于圖中的每條邊 (x,y)，x 在 A 中都出現在 y 之前，則稱 A 是該圖的一個拓撲序列，
輸入格式
第一行包含兩個整數 n 和 m，
接下來 mm 行，每行包含兩個整數 x 和 y，表示存在一條從點 x 到點 y 的有向邊 (x,y)，
輸出格式
共一行，如果存在拓撲序列，則輸出任意一個合法的拓撲序列即可，
否則輸出 ?1，
資料范圍
1≤n,m≤105
輸入樣例：
3 3 1 2 2 3 1 3輸出樣例：
1 2 3
【參考代碼】
陣列模擬佇列：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int d[N];//統計節點入度情況
int q[N];//佇列
int n, m;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool topsort()
{
int hh = 0, tt = -1;
//1.
for (int i = 1; i <= n; i ++ )// 將所有入度為0的點入隊
if(d[i] == 0)
q[++ tt] = i;
//2.
while(hh <= tt)
{
int t = q[hh ++];// 獲取隊頭元素的同時，也就彈出了隊頭元素！
//刪掉t的所有出邊
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
d[j] --;
if(d[j] == 0)
q[++ tt] = j;//當節點j入度為0時，入隊
}
}
return tt==n-1;
//表示如果n個點都入隊了話,那么該圖為拓撲圖,回傳true,否則回傳false
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- )
{
int a, b;
cin >> a >> b;
add(a, b);
d[b] ++;//因為是a指向b,所以b點的入度要加1
}
if(topsort())
{
for (int i = 0; i < n; i ++ )
cout << q[i] << " ";
//經上方回圈可以發現佇列中的點的次序就是拓撲序列
//注:拓撲序列的答案并不唯一
puts("");
}
else
puts("-1");
return 0;
}
STL：queue，開一個top[N]陣列來記錄拓撲序列！
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int d[N];//統計節點入度情況
int top[N];//記錄拓撲序列
int n, m, cnt;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool topsort()
{
queue<int>q;
for (int i = 1; i <= n; i ++ )// 將所有入度為0的點入隊
if(d[i] == 0)
q.push(i);
//2.
while(q.size())
{
int t = q.front();
top[cnt ++] = t;//加入到 拓撲序列中
q.pop();
//刪掉t的所有出邊
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
d[j] --;
if(d[j] == 0)
q.push(j);//當節點j入度為0時，入隊
}
}
return cnt == n;
//表示如果n個點都入隊了話,那么該圖為拓撲圖,回傳true,否則回傳false
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- )
{
int a, b;
cin >> a >> b;
add(a, b);
d[b] ++;//因為是a指向b,所以b點的入度要加1
}
if(topsort())
{
for (int i = 0; i < n; i ++ )
cout << top[i] << " ";
//經上方回圈可以發現佇列中的點的次序就是拓撲序列
//注:拓撲序列的答案并不唯一
puts("");
}
else
puts("-1");
return 0;
}
三、總結
在理解思路的基礎上，學習總結代碼！
學習內容源自：
acwing演算法基礎課
注：如果文章有任何錯誤或不足，請各位大佬盡情指出，評論留言留下您寶貴的建議！如果這篇文章對你有些許幫助，希望可愛親切的您點個贊推薦一手，非常感謝啦
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/412967.html
標籤：其他
上一篇：3分鐘快速了解豬齒魚權限
下一篇：AcWing打卡-2014-島