NO.91十六屆藍橋杯備戰|圖論基礎-圖的存儲和遍歷|鄰接矩陣|vector|鏈式前向星(C++)

圖的基本概念

圖的定義

圖G是由頂點集V和邊集E組成，記為G = (V, E)，其中V(G)表?圖G中頂點的有限?空集；E(G)表?圖G中頂點之間的關系（邊）集合。若 $\left\{ v_{1},v_{2},\dots,v_{n} \right\}$ ，則? $∣ V ∣$ 表
?圖G中頂點的個數，也稱圖G的階， $\in V, v \in V}$ ，? $∣ E ∣$ 表?圖G中邊的條數。
圖是較線性表和樹更為復雜的數據結構。

線性表中，除第?個和最后?個元素外，每個元素只有?個唯?的前驅和唯?的后繼結點，元素和元素之間是?對?的關系；
在樹形結構中，數據元素之間有著明顯的層次關系，每個元素有唯?的雙親，但可能有多個孩?，元素和元素之間是?對多的關系；
?圖形結構中，元素和元素之間的關系更加復雜，結點和結點之間的關系是任意的，任意兩個結點之間都可能相關，圖中元素和元素之間是多對多的關系

有向圖和?向圖

圖根據邊的類型，可以分為?向圖和有向圖
![[Pasted image 20250411211513.png]]

在圖相關的算法中，我們可以將?向圖中的邊看成兩條?向相反的有向邊，從?將?向圖轉化為有向圖
![[Pasted image 20250411211622.png]]

簡單圖與多重圖

?環：??指向??的?條邊
![[Pasted image 20250411211640.png]]

重邊：圖中存在兩個或兩個以上完全相同的邊
![[Pasted image 20250411211811.png]]

簡單圖：若圖中沒有重邊和?環，為簡單圖。
多重圖：若圖中存在重邊或?環，為多重圖。
![[Pasted image 20250411211832.png]]

稠密圖和稀疏圖

有很少條邊(如e < nlog2 n )的圖稱為稀疏圖，反之稱為稠密圖
![[Pasted image 20250411211857.png]]

頂點的度

頂點v的度是指與它相關聯的邊的條數，記作deg(v)。由該頂點發出的邊稱為頂點的出度，到達該頂點的邊稱為頂點的?度。

?向圖中，頂點的度等于該頂點的?度(indev)和出度(outdev)，即deg(v)=indeg(v)=outdeg(v)。
有向圖中，頂點的度等于該頂點的?度與出度之和，其中頂點v的?度indeg(v)是以v為終點的有向邊的條數，頂點v的出度outdeg(v)是以v為起始點的有向邊的條數，deg(v)=indeg(v)+outdeg(v)

路徑

在圖G=(V，E)中，若從頂點 $v_{i}$ 出發，沿?些邊經過某些頂點 $v_{p1},v_{p2},\dots,v_{pm}$ ，到達頂點 $v_{j}$ 。則稱頂點序列 $(v_{i},v_{p1},v_{p2},\dots,v_{pm},v_{j})$ 為從頂點 $v_{i}$ 到頂點 $v_{j}$ 的路徑。
注意：兩個頂點間的路徑可能不唯?
![[Pasted image 20250411212248.png]]

簡單路徑與回路

若路徑上各頂點 $v_{1},v_{2},\dots,v_{m}$ 均不重復，則稱這樣的路徑為簡單路徑。若路徑上第?個頂點 $v_{1}$ 和最后?個頂點 $v_{m}$ 相同，則稱這樣的路徑為回路或環
![[Pasted image 20250411212403.png]]

路徑?度和帶權路徑?度

某些圖的邊具有與它相關的數值，稱其為該邊的權值。這些權值可以表?兩個頂點間的距離、花費的代價、所需的時間等。?般將該種帶權圖稱為?絡
![[Pasted image 20250411212509.png]]

對于不帶權的圖，?條路徑的路徑?度是指該路徑上的邊的條數。
對于帶權的圖，?條路徑的路徑?度是指該路徑上各個邊權值的總和。
![[Pasted image 20250411212521.png]]

?圖

設圖 $\left\{ V, E\right\}$ 和圖 $\left\{ V',E' \right\}$ ，若 $V'\in V$ 且 $E'\in E$ ，則稱 $G^{'}$ 是 $G$ 的?圖。若有 $V (G^{'}) = V (G)$ 的?圖 $G^{'}$ ，則稱 $G^{'}$ 為 $G$ 的?成?圖。
相當于就是在原來圖的基礎上，拿出來?些頂點和邊，組成?個新的圖。但是要注意，拿出來的點和邊要能構成?個圖才?
![[Pasted image 20250411212748.png]]

G1_1和G1_2為?向圖G1的?圖，G1_1為G1的?成?圖。
G2_1和G2_2為有向圖G2的?圖，G2_1為G2的?成?圖。

連通圖與連通分量

在?向圖中，若從頂點 $v_{1}$ 到頂點 $v_{2}$ 有路徑，則稱頂點 $v_{1}$ 與頂點 $v_{2}$ 是連通的。如果圖G中任意?對頂點都是連通的，則圖G稱為連通圖，否則稱為?連通圖。

假設?個圖有n個頂點，如果邊數?于n-1，那么此圖?定是?連通圖。
極?聯通?圖：?向圖中，拿出?個?圖，這個?圖包含盡可能多的點和邊。
連通分量：?向圖中的極?連通?圖稱為連通分量

?成樹

連通圖的?成樹是包含圖中全部頂點的?個極?連通?圖。若圖中頂點數為n，則它的?成樹含有n-1條邊。對?成樹??，若砍去?條邊，則會變成?連通圖，若加上?條邊則會形成?個回路
![[Pasted image 20250411213241.png]]

圖的存儲和遍歷

圖的存儲有兩種：鄰接矩陣和鄰接表：

其中，鄰接表的存儲?式與樹的孩?表?法完全?樣。因此，?vector數組以及鏈式前向星就能實現。
?鄰接矩陣就是??個?維數組，其中edges[i][j]存儲頂點 i 與頂點 j 之間，邊的信息。
圖的遍歷分兩種：DFS和BFS，和樹的遍歷?式以及實現?式完全?樣。因此，可以仿照樹這個數據結構來學習

鄰接矩陣

鄰接矩陣，指??個矩陣(即?維數組)存儲圖中邊的信息(即各個頂點之間的鄰接關系)，存儲頂點之間鄰接關系的矩陣稱為鄰接矩陣。
對于帶權圖??，若頂點 $v_{i}$ 和 $v_{j}$ 之間有邊相連，則鄰接矩陣中對應項存放著該邊對應的權值，若頂點 $v_{i}$ 和 $v_{j}$ 不相連，則? $\infty$ 來代表這兩個頂點之間不存在邊。
對于不帶權的圖，可以創建?個?維的bool類型的數組，來標記頂點vi 和vj 之間有邊相連
![[Pasted image 20250411214010.png]]

矩陣中元素個數為nxn，即空間復雜度為O(n^2) ，n為頂點個數，和實際邊的條數?關，適合存儲稠密圖

#include <iostream>  
#include <cstring>  
using namespace std;  
const int N = 1010;  
int n, m;  
int edges[N][N];  
int main()  
{  memset(edges, -1, sizeof edges);  cin >> n >> m; // 讀?結點個數以及邊的個數  for(int i = 1; i <= m; i++)  {  int a, b, c; cin >> a >> b >> c;  // a - b 有?條邊，權值為 c  edges[a][b] = c;  // 如果是?向邊，需要反過來再存?下  edges[b][a] = c;  }return 0;  
}

vector數組

和樹的存儲?模?樣，只不過如果存在邊權的話，我們的vector數組??放?個結構體或者是pair即可。

#include <iostream>  
#include <vector>  using namespace std;  
typedef pair<int, int> PII;  
const int N = 1e5 + 10;  
int n, m;  
vector<PII> edges[N];  int main()  
{  cin >> n >> m; // 讀?結點個數以及邊的個數  for(int i = 1; i <= m; i++)  {  int a, b, c; cin >> a >> b >> c;  // a 和 b 之間有?條邊，權值為 c  edges[a].push_back({b, c});  // 如果是?向邊，需要反過來再存?下  edges[b].push_back({a, c});  }  return 0;  
}

鏈式前向星

和樹的存儲?模?樣，只不過如果存在邊權的話，我們多創建?維數組，?來存儲邊的權值即可

#include <iostream>  
using namespace std;  
const int N = 1e5 + 10;  
// 鏈式前向星  
int h[N], e[N * 2], ne[N * 2], w[N * 2], id;  
int n, m;  
// 其實就是把 b 頭插到 a 所在的鏈表后?  
void add(int a, int b, int c)  
{  id++;  e[id] = b;  w[id] = c; // 多存?個權值信息  ne[id] = h[a];  h[a] = id;  
}  
int main()  
{  cin >> n >> m; // 讀?結點個數以及邊的個數  for(int i = 1; i <= m; i++)  {  int a, b, c; cin >> a >> b >> c;  // a 和 b 之間有?條邊，權值為 c  add(a, b, c); add(b, a, c);  }  return 0;  
}

DFS

和樹的遍歷?式?模?樣，?條路?到?

?鄰接矩陣的?式存儲

#include <iostream>  
#include <cstring>  
#include <queue>  
using namespace std;  
const int N = 1010;  
int n, m;  
int edges[N][N];  
bool st[N]; // 標記哪些點已經訪問過  
void dfs(int u)  
{  cout << u << endl;  st[u] = true;  // 遍歷所有孩?  for(int v = 1; v <= n; v++)  {  // 如果存在 u->v 的邊，并且沒有遍歷過  if(edges[u][v] != -1 && !st[v])  {  dfs(v);  }  }  
}  int main()  
{  memset(edges, -1, sizeof edges);  cin >> n >> m; // 讀?結點個數以及邊的個數  for(int i = 1; i <= m; i++)  {  int a, b, c; cin >> a >> b >> c;  // a - b 有?條邊，權值為 c  edges[a][b] = c;  // 如果是?向邊，需要反過來再存?下  edges[b][a] = c;  }return 0;  
}

?vector數組的?式存儲

#include <iostream>  
#include <vector>  
#include <queue>  
using namespace std;  
typedef pair<int, int> PII;  
const int N = 1e5 + 10;  
int n, m;  
vector<PII> edges[N];  
bool st[N]; // 標記哪些點已經訪問過  
void dfs(int u)  
{  cout << u << endl;  st[u] = true;  // 遍歷所有孩?  for(auto& t : edges[u])  {  // u->v 的?條邊，權值為 w  int v = t.first, w = t.second;  if(!st[v])  {  dfs(v);  }  }  
}  int main()  
{  cin >> n >> m; // 讀?結點個數以及邊的個數  for(int i = 1; i <= m; i++){  int a, b, c; cin >> a >> b >> c;  // a 和 b 之間有?條邊，權值為 c  edges[a].push_back({b, c});  // 如果是?向邊，需要反過來再存?下  edges[b].push_back({a, c});  }  return 0;  
}

?鏈式前向星的?式存儲

#include <iostream>  
#include <queue>  
using namespace std;  
const int N = 1e5 + 10;  
// 鏈式前向星  
int h[N], e[N * 2], ne[N * 2], w[N * 2], id;  
int n, m;  
// 其實就是把 b 頭插到 a 所在的鏈表后?  
void add(int a, int b, int c)  
{  id++;  e[id] = b;  w[id] = c; // 多存?個權值信息  ne[id] = h[a];  h[a] = id;  
}  bool st[N];  void dfs(int u)  
{  cout << u << endl;  st[u] = true;// 遍歷所有的孩?  for(int i = h[u]; i; i = ne[i])  {  // u->v 的?條邊  int v = e[i];  if(!st[v])  {  dfs(v);  }  }  
}  
int main()  
{  cin >> n >> m; // 讀?結點個數以及邊的個數  for(int i = 1; i <= m; i++)  {  int a, b, c; cin >> a >> b >> c;  // a 和 b 之間有?條邊，權值為 c  add(a, b, c); add(b, a, c);  }  return 0;  
}

BFS

?鄰接矩陣的?式存儲

#include <iostream>  
#include <cstring>  
#include <queue>  
using namespace std;  
const int N = 1010;  
int n, m;  
int edges[N][N];
bool st[N]; // 標記哪些點已經訪問過  
void bfs(int u)  
{  queue<int> q;  q.push(u);  st[u] = true;  while(q.size())  {  auto a = q.front(); q.pop();  cout << a << endl;  for(int b = 1; b <= n; b++)  {  if(edges[a][b] != -1 && !st[b])  {  q.push(b);  st[b] = true;  }  }  }  
}  int main()  
{  memset(edges, -1, sizeof edges);  cin >> n >> m; // 讀?結點個數以及邊的個數  for(int i = 1; i <= m; i++)  {  int a, b, c; cin >> a >> b >> c;  // a - b 有?條邊，權值為 c  edges[a][b] = c;  // 如果是?向邊，需要反過來再存?下  edges[b][a] = c;  }  return 0;  
}

?vector數組的?式存儲

#include <iostream>  
#include <vector>  
#include <queue>  
using namespace std;  
typedef pair<int, int> PII;  
const int N = 1e5 + 10;  
int n, m;  
vector<PII> edges[N];  
bool st[N]; // 標記哪些點已經訪問過  
void bfs(int u)  
{  queue<int> q;  q.push(u);  st[u] = true;  while(q.size())  {  auto a = q.front(); q.pop();  cout << a << endl;  for(auto& t : edges[a])  {  int b = t.first, c = t.second;  if(!st[b])  {  q.push(b);  st[b] = true;  }  }  }  
}  int main()  
{  cin >> n >> m; // 讀?結點個數以及邊的個數  for(int i = 1; i <= m; i++)  {  int a, b, c; cin >> a >> b >> c;// a 和 b 之間有?條邊，權值為 c  edges[a].push_back({b, c});  // 如果是?向邊，需要反過來再存?下  edges[b].push_back({a, c});  }  return 0;  
}

?鏈式前向星的?式存儲

#include <iostream>  
#include <queue>  
using namespace std;  
const int N = 1e5 + 10;  
// 鏈式前向星  
int h[N], e[N * 2], ne[N * 2], w[N * 2], id;  
int n, m;  
// 其實就是把 b 頭插到 a 所在的鏈表后?  
void add(int a, int b, int c)  
{  id++;  e[id] = b;  w[id] = c; // 多存?個權值信息  ne[id] = h[a];  h[a] = id;  
}  bool st[N];  void bfs(int u)  
{  queue<int> q;  q.push(u);  st[u] = true;  while(q.size(){  auto a = q.front(); q.pop();  cout << a << endl;  for(int i = h[a]; i; i = ne[i])  {  int b = e[i], c = w[i];  if(!st[b])  {  q.push(b);  st[b] = true;  }  }  }  
}  
int main()  
{  cin >> n >> m; // 讀?結點個數以及邊的個數  for(int i = 1; i <= m; i++)  {  int a, b, c; cin >> a >> b >> c;  // a 和 b 之間有?條邊，權值為 c  add(a, b, c); add(b, a, c);  }  return 0;  
}