圖
by.Qin3Yu
請注意：嚴格來說，圖不是一種數(shù)據(jù)結(jié)構(gòu)，而是一種抽象數(shù)據(jù)類型。但為了保證知識點之間的相關(guān)性，也將其列入數(shù)據(jù)結(jié)構(gòu)專欄。
本文需要讀者掌握順序表和單鏈表的操作基礎(chǔ)，若需學(xué)習(xí)，可參閱我的往期文章：
【C++數(shù)據(jù)結(jié)構(gòu) | 順序表速通】使用順序表完成簡單的成績管理系統(tǒng).by.Qin3Yu
【C++數(shù)據(jù)結(jié)構(gòu) | 單鏈表速通】使用單鏈表完成數(shù)據(jù)的輸入和返回元素之和.by.Qin3Yu
本文將不會涉及圖的具體操作案例，若需閱讀案例，可參閱我的往期文章：
【經(jīng)典案例 | 騎士之旅】回溯算法解決經(jīng)典國際象棋騎士之旅問題 | 詳解Knight’s Tour Problem數(shù)學(xué)問題.by.Qin3Yu
【算法詳解 | 最小生成樹 I 】詳解最小生成樹prim算法（拓展kruskal算法） | 電力網(wǎng)絡(luò)最短路徑覆蓋問題.by.Qin3Yu
文中所有代碼默認已使用std命名空間且已導(dǎo)入部分頭文件：
#include <iostream>
#include <vector>
using namespace std;
概念速覽
圖的基本概念及定義
- 圖（Graph） 是由一組頂點和連接這些節(jié)點的邊組成的數(shù)據(jù)類型，可以將圖抽象的看作為一些島嶼和連接這些島嶼的小橋，頂點就是島嶼，邊就是橋。點和邊是構(gòu)成圖的基本元素，如下所示就是一個圖：
- 注意：大多數(shù)數(shù)據(jù)結(jié)構(gòu)和類型都可以為空，但是 圖不可以為空 。
向性與連通性
- 在圖中，如果 所有的邊 都沒有方向限制，均可以雙向通行，則稱為無向圖。相反，如果 所有的邊 都具有方向限制，每條邊只提供單向通行，則稱為無向圖。
- 在 無向圖 中，如果圖上任意一對點都有路徑連通（可以穿過其他點），則稱為 連通圖 。如果在 有向圖 中，如果圖上任意一對點都有路徑連通且 雙向連通 ，則稱為 強連通圖 。
特別注意：有向圖需雙向連通才算作強連通圖！
加權(quán)圖與邊權(quán)
- 在很多圖中，每條邊都有指定的長度，且長度各不相同。在圖論中，邊的長度叫做 邊權(quán) ，每條邊都有權(quán)值的圖叫做 加權(quán)圖 ，例如在下圖中，圖書館到體育室的邊的長度為1200m，則我們可以說圖書館-體育室的 邊權(quán) 為1200：
稀疏圖與稠密圖
- 在圖中，邊數(shù)明顯少于點數(shù) 的圖叫做稀疏圖，相反，點數(shù)明顯少于邊數(shù) 的圖叫做稠密圖。需要注意，稀疏圖與稠密圖只是一個相對而言的概念，沒有明確的數(shù)值指明邊和點之間的數(shù)量界限。
度與入度出度
- 在無向圖中，某個點的 度指的是與這個點相連的邊的數(shù)量。如圖所示，我們可以說 A點 的度為 2，B點 的度為 1：
- 在有向圖中，某個點的 入度是指與該點相連，且終點為該點 的邊的數(shù)量。相反，某個點的 出度是指與該點相連，且起點為該點 的邊的數(shù)量。如圖所示，我們可以說 A點 的出度為 2，入度為 1：
一個明確的圖應(yīng)具有以下特征：
1. 無重復(fù)邊： 在無向圖中，每對點之間只有唯一的一條邊連接，不存在一對點之間有兩條邊的情況；
2. 明確向性： 大多數(shù)情況下的圖要么是有向圖，要么是無向圖，很少存在同一張圖中某些邊有向同時某些邊無相（混合圖）的情況；
3. 無自環(huán)： 在圖中不存在連接一個節(jié)點到其自身的邊。
圖的存儲與表示
圖根據(jù)稀疏和稠密的特征有兩種常用的存儲方式，分別是鄰接矩陣和鄰接表。
鄰接矩陣
- 在鄰接矩陣中，我們使用一個二維數(shù)組（矩陣）來表示圖，如下圖中有6個點，則我們需要畫一個6×6的矩陣，且默認表內(nèi)元素全部為0：
int n = 6; // 點數(shù)
vector<vector<int>> Graph(n, vector<int>(n, 0)); // 初始化一個n×n的矩陣，默認為0
- 如圖，點1 和 點0 之間有一條邊連接，則我們在 (1,0) 位置填入 1 ，表示 點1 和 點0 之間有邊：
- 同理，點1 和 點2 之間有一條邊連接，則我們在 (2,1) 位置填入 1 ，表示 點2 和 點1 之間有邊：
- 一直重復(fù)這個過程，我們便可以得出以下結(jié)果：
- 但同時根據(jù)無向表雙向通行的特性，點0 到 點1 有邊，那么反過來 點1 到 點0 也有邊，所以我們還需要反過來再重復(fù)一次，將剩下的半部分補齊。如下圖所示，可以看到 無向圖的鄰接矩陣呈對角線對稱 ，所以我們在使用程序輸入時可以直接 對稱輸入 ：
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
Graph[x][y] = 1;
Graph[y][x] = 1; // 對稱輸入
}
- 但如果圖是有向圖，則只能逐個輸入：
int m = ... // 邊數(shù)
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
Graph[x][y] = 1;
}
- 從上面的案例可以看出鄰接矩陣需要維護一個n×n的二維數(shù)組，且使用1來標記邊的位置，所以不難看出，假如圖是點很多而邊很少的稀疏圖，則會浪費大量的內(nèi)存。所以，鄰接矩陣更適合表示稠密圖和無向圖 。
鄰接表
- 除了用矩陣外，我們還可以用多鏈表來表示圖。在鏈表中，每個節(jié)點具有兩個成員，一個為該節(jié)點的值，另一個為指向下一個節(jié)點的指針，我們先初始化一些鏈表，讓每個點都有一串對應(yīng)的鏈表來表示自己與其他點的相連關(guān)系：
//定義單鏈表
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
const int n = 6; // 節(jié)點數(shù)
const int m = 7; // 邊數(shù)
ListNode* Graph[n]; // 聲明多個鏈表
- 如圖，點0 與 點1 相連，則我們在 0號鏈表 上增加節(jié)點，節(jié)點值為 1，代表 點1：
- 然后再看 點1，點1 與 點2 相連，則我們在 1號鏈表 上增加節(jié)點，節(jié)點值為 2，代表 點2：
- 不斷重復(fù)此過程，我們便可以得出如下的結(jié)果，這便是圖的鄰接表，與鄰接矩陣相比，鄰接表不需要維護一個很大的矩陣來表示邊與邊的關(guān)系，但是構(gòu)造起來也相對復(fù)雜。因此，鄰接表更適合表示稀疏圖和有向圖：
- 在具體的代碼實現(xiàn)中，我們只需要將節(jié)點鏈接到鏈表后面即可，具體操作請參閱我的往期單鏈表教程，本文不再贅述：
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
ListNode* newNode = new ListNode(v);
newNode->next = Graph[u];
Graph[u] = newNode;
}
- 但要注意，在無向圖中邊是雙向互通的，只要 u 有一條路徑指向 v，那么相反 v 也有一條路徑指向 u。因此，對于無向圖，我們需要對稱輸入：
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
ListNode* newNode1 = new ListNode(v);
newNode1->next = Graph[u];
Graph[u] = newNode1;
ListNode* newNode2 = new ListNode(u);
newNode2->next = Graph[v];
Graph[v] = newNode2;
}
至此圖的相關(guān)內(nèi)容已講解完畢，具體案例可以參閱我的往期文章（如文章開頭所示）（=
如需提問，可以在評論區(qū)留言或私信（=
完整代碼展示
無向圖鄰接矩陣
代碼
#include <iostream>
#include <vector>
using namespace std;
int n = 6; // 點數(shù)
int m = 7; // 邊數(shù)
vector<vector<int>> Graph(n, vector<int>(n, 0));
int main() {
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
Graph[u][v] = 1;
Graph[v][u] = 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
cout << Graph[i][j] << " ";
cout << endl;
}
return 0;
}
參考輸入
0 1
1 2
2 3
3 4
4 0
2 5
3 5
參考輸出
0 1 0 0 1 0
1 0 1 0 0 0
0 1 0 1 0 1
0 0 1 0 1 1
1 0 0 1 0 0
0 0 1 1 0 0
有向圖鄰接矩陣
代碼
#include <iostream>
#include <vector>
using namespace std;
int n = 6; // 點數(shù)
int m = 7; // 邊數(shù)
vector<vector<int>> Graph(n, vector<int>(n, 0));
int main() {
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
Graph[u][v] = 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
cout << Graph[i][j] << " ";
cout << endl;
}
return 0;
}
參考輸入
0 1
1 2
2 3
3 4
4 0
3 5
5 3
參考輸出文章來源：http://www.zghlxwxcb.cn/news/detail-755385.html
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 1
1 0 0 0 0 0
0 0 0 1 0 0
無向圖鄰接表
代碼
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
const int n = 6; // 節(jié)點數(shù)
const int m = 7; // 邊數(shù)
ListNode* Graph[n];
int main() {
for (int i = 0; i < n; i++)
Graph[i] = nullptr;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
ListNode* newNode1 = new ListNode(v);
newNode1->next = Graph[u];
Graph[u] = newNode1;
ListNode* newNode2 = new ListNode(u);
newNode2->next = Graph[v];
Graph[v] = newNode2;
}
for (int i = 0; i < n; i++) {
cout << i << ": ";
ListNode* curr = Graph[i];
while (curr != nullptr) {
cout << curr->val << " ";
curr = curr->next;
}
cout << endl;
}
return 0;
}
參考輸入
0 1
1 2
2 3
3 4
4 0
2 5
3 5
參考輸出
0: 4 1
1: 2 0
2: 5 3 1
3: 5 4 2
4: 0 3
5: 3 2
有向圖鄰接表
代碼
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
const int n = 6; // 節(jié)點數(shù)
const int m = 7; // 邊數(shù)
ListNode* Graph[n];
int main() {
for (int i = 0; i < n; i++)
Graph[i] = nullptr;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
ListNode* newNode = new ListNode(v);
newNode->next = Graph[u];
Graph[u] = newNode;
}
for (int i = 0; i < n; i++) {
cout << i << ": ";
ListNode* curr = Graph[i];
while (curr != nullptr) {
cout << curr->val << " ";
curr = curr->next;
}
cout << endl;
}
return 0;
}
參考輸入
0 1
1 2
2 3
3 4
4 0
3 5
5 3
參考輸出
0: 1
1: 2
2: 3
3: 5 4
4: 0
5: 3
感謝您的觀看（=
by.Qin3Yu文章來源地址http://www.zghlxwxcb.cn/news/detail-755385.html
到了這里，關(guān)于【C++數(shù)據(jù)結(jié)構(gòu) | 圖速通】10分鐘掌握鄰接矩陣 & 鄰接表 | 快速掌握圖論基礎(chǔ) | 快速上手抽象數(shù)據(jù)類型圖的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
