圖
圖的基本概念
圖的基本概念
圖是由頂點(diǎn)集合和邊的集合組成的一種數(shù)據(jù)結(jié)構(gòu)，記作 G = ( V , E ) G=(V, E)G=(V,E) 。
有向圖和無(wú)向圖：
- 在有向圖中，頂點(diǎn)對(duì) < x , y >是有序的，頂點(diǎn)對(duì) < x , y > 稱(chēng)為頂點(diǎn) x 到頂點(diǎn) y 的一條邊，< x , y > 和 <y,x>是兩條不同的邊。
- 在無(wú)向圖中，頂點(diǎn)對(duì) ( x , y ) 是無(wú)序的，頂點(diǎn)對(duì) ( x , y ) 稱(chēng)為頂點(diǎn) x 和頂點(diǎn) y 相關(guān)聯(lián)的一條邊，這條邊沒(méi)有特定方向，( x , y ) 和 ( y , x ) 是同一條邊。
完全圖：
- 在有 n 個(gè)頂點(diǎn)的無(wú)向圖中，若有 n × ( n ? 1 ) ÷ 2 條邊，即任意兩個(gè)頂點(diǎn)之間都有直接相連的邊，則稱(chēng)此圖為無(wú)向完全圖。
- 在有 n 個(gè)頂點(diǎn)的有向圖中，若有 n × ( n ? 1 )條邊，即任意兩個(gè)頂點(diǎn)之間都有雙向的邊，則稱(chēng)此圖為有向完全圖。
如下圖：
鄰接頂點(diǎn)：
- 在無(wú)向圖中，若 ( u , v ) 是圖中的一條邊，則稱(chēng) u 和 v 互為鄰接頂點(diǎn)，并稱(chēng)邊 ( u , v ) 依附于頂點(diǎn) u 和頂點(diǎn)v 。
- 在有向圖中，若 < u , v > 是圖中的一條邊，則稱(chēng)頂點(diǎn) u 鄰接到頂點(diǎn) v ，頂點(diǎn) v 鄰接自頂點(diǎn) u ，并稱(chēng)邊 <u , v > 與頂點(diǎn) u 和頂點(diǎn) v 相關(guān)聯(lián)。
頂點(diǎn)的度：
- 在有向圖中，頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和，頂點(diǎn)的入度是以該頂點(diǎn)為終點(diǎn)的邊的條數(shù)，頂點(diǎn)的出度是以該頂點(diǎn)為起點(diǎn)的邊的條數(shù)。
- 在無(wú)向圖中，頂點(diǎn)的度等于與該頂點(diǎn)相關(guān)聯(lián)的邊的條數(shù)，同時(shí)也等于該頂點(diǎn)的入度和出度。
路徑與路徑長(zhǎng)度：
- 若從頂點(diǎn) vi 出發(fā)有一組邊使其可到達(dá)頂點(diǎn) vj ，則稱(chēng)頂點(diǎn) vi 到頂點(diǎn) vj 的頂點(diǎn)序列為從頂點(diǎn) vi 到頂點(diǎn) vj 的路徑。
- 對(duì)于不帶權(quán)的圖，一條路徑的長(zhǎng)度是指該路徑上的邊的條數(shù)；對(duì)于帶權(quán)的圖，一條路徑的長(zhǎng)度是指該路徑上各個(gè)邊權(quán)值的總和。
帶權(quán)圖示例：
簡(jiǎn)單路徑與回路：
- 若路徑上的各個(gè)頂點(diǎn)均不相同，則稱(chēng)這樣的路徑為簡(jiǎn)單路徑。
- 若路徑上第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)相同，則稱(chēng)這樣的路徑為回路或環(huán)。
如下圖：
子圖：
- 設(shè)圖G=(V,E) 和圖G1=(V1,E1)，若 V 1 ? V 且 E1?E ，則稱(chēng) G1 是 G 的子圖。
如下圖：
連通圖和強(qiáng)連通圖：
- 在無(wú)向圖中，若從頂點(diǎn) v1 到頂點(diǎn) v2 有路徑，則稱(chēng)頂點(diǎn) v1 與頂點(diǎn) v2 是連通的，如果圖中任意一對(duì)頂點(diǎn)都是連通的，則稱(chēng)此圖為連通圖。
- 在有向圖中，若每一對(duì)頂點(diǎn)vi 和 vj 之間都存在一條從vi到vj 的路，也存在一條從 vj 到 vi 的路，則稱(chēng)此圖是強(qiáng)連通圖。
生成樹(shù)與最小生成樹(shù)：
- 一個(gè)連通圖的最小連通子圖稱(chēng)為該圖的生成樹(shù)，有 n 個(gè)頂點(diǎn)的連通圖的生成樹(shù)有 n 個(gè)頂點(diǎn)和 n ? 1 條邊。
- 最小生成樹(shù)指的是一個(gè)圖的生成樹(shù)中，總權(quán)值最小的生成樹(shù)。
圖的相關(guān)應(yīng)用場(chǎng)景
圖常見(jiàn)的表示場(chǎng)景如下：
- 交通網(wǎng)絡(luò)：圖中的每個(gè)頂點(diǎn)表示一個(gè)地點(diǎn)，圖中的邊表示這兩個(gè)地點(diǎn)之間是否有直接相連的公路，邊的權(quán)值可以是這兩個(gè)地點(diǎn)之間的距離、高鐵時(shí)間等。
- 網(wǎng)絡(luò)設(shè)備拓?fù)洌簣D中的每個(gè)頂點(diǎn)表示網(wǎng)絡(luò)中的一個(gè)設(shè)備，圖中的邊表示這兩個(gè)設(shè)備之間是否可以互傳數(shù)據(jù)，邊的權(quán)值可以是這兩個(gè)設(shè)備之間傳輸數(shù)據(jù)所需的時(shí)間、丟包的概率等。
- 社交網(wǎng)絡(luò)：圖中的每個(gè)頂點(diǎn)表示一個(gè)人，圖中的邊表示這兩個(gè)人是否互相認(rèn)識(shí)，邊的權(quán)值可以是這兩個(gè)人之間的親密度、共同好友個(gè)數(shù)等。
關(guān)于有向圖和無(wú)向圖：
- 交通網(wǎng)絡(luò)對(duì)應(yīng)的圖可以是有向圖，也可以是無(wú)向圖，無(wú)向圖對(duì)應(yīng)就是雙向車(chē)道，有向圖對(duì)應(yīng)就是單向車(chē)道。
- 網(wǎng)絡(luò)設(shè)備拓?fù)鋵?duì)應(yīng)的圖通常是無(wú)向圖，兩個(gè)設(shè)備之間有邊表示這兩個(gè)設(shè)備之間可以互相收發(fā)數(shù)據(jù)。
- 社交網(wǎng)絡(luò)對(duì)應(yīng)的圖可以是有向圖，也可以是無(wú)向圖，無(wú)向圖通常表示一些強(qiáng)社交關(guān)系，比如QQ、微信等（一定互為好友），有向圖通常表示一些弱社交關(guān)系，比如微博、抖音（不一定互相關(guān)注）。
圖的其他相關(guān)作用：
- 在交通網(wǎng)絡(luò)中，根據(jù)最短路徑算法計(jì)算兩個(gè)地點(diǎn)之間的最短路徑，根據(jù)最小生成樹(shù)算法得到將各個(gè)地點(diǎn)連通起來(lái)所需的最小成本。
- 在社交網(wǎng)絡(luò)中，根據(jù)廣度優(yōu)先搜索得到兩個(gè)人之間的共同好友進(jìn)行好友推薦，根據(jù)入邊表和出邊表得知有哪些粉絲以及關(guān)注了哪些博主。
圖與樹(shù)的聯(lián)系與區(qū)別
圖與樹(shù)的主要聯(lián)系與區(qū)別如下：
- 樹(shù)是一種有向無(wú)環(huán)且連通的圖（空樹(shù)除外），但圖并不一定是樹(shù)。
- 有 n 個(gè)結(jié)點(diǎn)的樹(shù)必須有 n ? 1 條邊，而圖中邊的數(shù)量不取決于頂點(diǎn)的數(shù)量。
- 樹(shù)通常用于存儲(chǔ)數(shù)據(jù)，并快速查找目標(biāo)數(shù)據(jù)，而圖通常用于表示某種場(chǎng)景。
圖的存儲(chǔ)結(jié)構(gòu)
圖由頂點(diǎn)和邊組成，存儲(chǔ)圖本質(zhì)就是將圖中的頂點(diǎn)和邊存儲(chǔ)起來(lái)。
鄰接矩陣
鄰接矩陣
鄰接矩陣存儲(chǔ)圖的方式如下：
- 用一個(gè)數(shù)組存儲(chǔ)頂點(diǎn)集合，頂點(diǎn)所在位置的下標(biāo)作為該頂點(diǎn)的編號(hào)（所給頂點(diǎn)可能不是整型）。
- 用一個(gè)二維數(shù)組matrix存儲(chǔ)邊的集合，其中matrix[i][j] 表示編號(hào)為 i 和 j 的兩個(gè)頂點(diǎn)之間的關(guān)系。
如下圖：
說(shuō)明一下：
- 對(duì)于不帶權(quán)的圖，兩個(gè)頂點(diǎn)之間要么相連，要么不相連，可以用0和1表示，m a t r i x [ i ] [ jmatrix[i][j] 為1表示編號(hào)為 i 和 j 的兩個(gè)頂點(diǎn)相連，為0表示不相連。
- 對(duì)于帶權(quán)的圖，連接兩個(gè)頂點(diǎn)的邊會(huì)帶有一個(gè)權(quán)值，可以用這個(gè)權(quán)值來(lái)設(shè)置對(duì)應(yīng)matrix[i][j] 的值，如果兩個(gè)頂點(diǎn)不相連，則使用不會(huì)出現(xiàn)的權(quán)值進(jìn)行設(shè)置即可（圖中為無(wú)窮大）。
- 對(duì)于無(wú)向圖來(lái)說(shuō)，頂點(diǎn) i 和頂點(diǎn) j 相連，那么頂點(diǎn) j 就和頂點(diǎn) i 相連，因此無(wú)向圖對(duì)應(yīng)的鄰接矩陣是一個(gè)對(duì)稱(chēng)矩陣，即matrix[i][j] 的值等于 matrix[j][i] 的值。
- 在鄰接矩陣中，第 i 行元素中有效權(quán)值的個(gè)數(shù)就是編號(hào)為 i 的頂點(diǎn)的出度，第 i ii 列元素中有效元素的個(gè)數(shù)就是編號(hào)為 i 的頂點(diǎn)的入度。
鄰接矩陣的優(yōu)缺點(diǎn)
鄰接矩陣的優(yōu)點(diǎn)：
- 鄰接矩陣適合存儲(chǔ)稠密圖，因?yàn)榇鎯?chǔ)稠密圖和稀疏圖時(shí)所開(kāi)辟的二維數(shù)組大小是相同的，因此圖中的邊越多，鄰接矩陣的優(yōu)勢(shì)就越明顯。
- 鄰接矩陣能夠 O(1) 的判斷兩個(gè)頂點(diǎn)是否相連，并獲得相連邊的權(quán)值。
鄰接矩陣的缺點(diǎn)：
- 鄰接矩陣不適合查找一個(gè)頂點(diǎn)連接出去的所有邊，需要遍歷矩陣中對(duì)應(yīng)的一行，該過(guò)程的時(shí)間復(fù)雜度是O(N)，其中 N 表示的是頂點(diǎn)的個(gè)數(shù)。
鄰接矩陣的實(shí)現(xiàn)
鄰接矩陣所需成員變量：
- 數(shù)組 vertexs ：用于存儲(chǔ)頂點(diǎn)集合，頂點(diǎn)所在位置的下標(biāo)作為該頂點(diǎn)的編號(hào)。
- 映射關(guān)系vIndexMap ：用于建立頂點(diǎn)與其下標(biāo)的映射關(guān)系，便于根據(jù)頂點(diǎn)找到其對(duì)應(yīng)的下標(biāo)編號(hào)。
- 鄰接矩陣matrix ：用于存儲(chǔ)邊的集合，matrix[i][j] 表示編號(hào)為 i 和 j 的兩個(gè)頂點(diǎn)之間的關(guān)系。
鄰接矩陣的實(shí)現(xiàn)：
- 為了支持任意類(lèi)型的頂點(diǎn)類(lèi)型以及權(quán)值，可以將圖定義為模板類(lèi)，其中V 和W 分別表示頂點(diǎn)和權(quán)值的類(lèi)型，MAX_W 表示兩個(gè)頂點(diǎn)沒(méi)有連接時(shí)鄰接矩陣中存儲(chǔ)的值，將MAX_W 的缺省值設(shè)置為 INT_MAX （權(quán)值一般為整型），Direction 表示圖是否為有向圖，將Direction 的缺省值設(shè)置為false （無(wú)向圖居多）。
- 在構(gòu)造函數(shù)中完成頂點(diǎn)集合的設(shè)置，并建立各個(gè)頂點(diǎn)與其對(duì)應(yīng)下標(biāo)的映射關(guān)系，同時(shí)為鄰接矩陣開(kāi)辟空間，將矩陣中的值初始化為MAX_W ，表示剛開(kāi)始時(shí)各個(gè)頂點(diǎn)之間均不相連。
- 提供一個(gè)接口用于添加邊，在添加邊時(shí)先分別獲取源頂點(diǎn)和目標(biāo)頂點(diǎn)對(duì)應(yīng)的下標(biāo)編號(hào)，然后再將鄰接矩陣中對(duì)應(yīng)位置設(shè)置為邊的權(quán)值，如果圖為無(wú)向圖，則還需要在鄰接矩陣中添加目標(biāo)頂點(diǎn)到源頂點(diǎn)的邊。
- 在獲取頂點(diǎn)對(duì)應(yīng)的下標(biāo)時(shí)，先在vIndexMap 中進(jìn)行查找，如果找到了對(duì)應(yīng)的頂點(diǎn)，則返回該頂點(diǎn)對(duì)應(yīng)的下標(biāo)編號(hào)，如果沒(méi)有找到對(duì)應(yīng)的頂點(diǎn)，則說(shuō)明所給頂點(diǎn)不存在，此時(shí)可以拋出異常。
代碼如下：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-731303.html
//鄰接矩陣
namespace Matrix {
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph {
public:
//構(gòu)造函數(shù)
Graph(const V* vertexs, int n)
:_vertexs(vertexs, vertexs + n) //設(shè)置頂點(diǎn)集合
,_matrix(n, vector<int>(n, MAX_W)) { //開(kāi)辟二維數(shù)組空間
//建立頂點(diǎn)與下標(biāo)的映射關(guān)系
for (int i = 0; i < n; i++) {
_vIndexMap[vertexs[i]] = i;
}
}
//獲取頂點(diǎn)對(duì)應(yīng)的下標(biāo)
int getVertexIndex(const V& v) {
auto iter = _vIndexMap.find(v);
if (iter != _vIndexMap.end()) { //頂點(diǎn)存在
return iter->second;
}
else { //頂點(diǎn)不存在
throw invalid_argument("不存在的頂點(diǎn)");
return -1;
}
}
//添加邊
void addEdge(const V& src, const V& dst, const W& weight) {
int srci = getVertexIndex(src), dsti = getVertexIndex(dst); //獲取源頂點(diǎn)和目標(biāo)頂點(diǎn)的下標(biāo)
_matrix[srci][dsti] = weight; //設(shè)置鄰接矩陣中對(duì)應(yīng)的值
if (Direction == false) { //無(wú)向圖
_matrix[dsti][srci] = weight; //添加從目標(biāo)頂點(diǎn)到源頂點(diǎn)的邊
}
}
//打印頂點(diǎn)集合和鄰接矩陣
void print() {
int n = _vertexs.size();
//打印頂點(diǎn)集合
for (int i = 0; i < n; i++) {
cout << "[" << i << "]->" << _vertexs[i] << endl;
}
cout << endl;
//打印鄰接矩陣
//橫下標(biāo)
cout << " ";
for (int i = 0; i < n; i++) {
//cout << i << " ";
printf("%4d", i);
}
cout << endl;
for (int i = 0; i < n; i++) {
cout << i << " "; //豎下標(biāo)
for (int j = 0; j < n; j++) {
if (_matrix[i][j] == MAX_W) {
printf("%4c", '*');
}
else {
printf("%4d", _matrix[i][j]);
}
}
cout << endl;
}
cout << endl;
}
private:
vector<V> _vertexs; //頂點(diǎn)集合
unordered_map<V, int> _vIndexMap; //頂點(diǎn)映射下標(biāo)
vector<vector<W>> _matrix; //鄰接矩陣
};
}
說(shuō)明一下：
- 為了方便觀察，可以在類(lèi)中增加一個(gè) p r i n t printprint 接口，用于打印頂點(diǎn)集合和鄰接矩陣。
- 后續(xù)圖的相關(guān)算法都會(huì)以鄰接矩陣為例進(jìn)行講解，因?yàn)橐话阒挥斜容^稠密的圖才會(huì)存在最小生成樹(shù)和最短路徑的問(wèn)題。
鄰接表
鄰接表
鄰接表存儲(chǔ)圖的方式如下：
- 用一個(gè)數(shù)組存儲(chǔ)頂點(diǎn)集合，頂點(diǎn)所在的位置的下標(biāo)作為該頂點(diǎn)的編號(hào)（所給頂點(diǎn)可能不是整型）。
- 用一個(gè)出邊表存儲(chǔ)從各個(gè)頂點(diǎn)連接出去的邊，出邊表中下標(biāo)為 i ii 的位置存儲(chǔ)的是從編號(hào)為 i ii 的頂點(diǎn)連接出去的邊。
- 用一個(gè)入邊表存儲(chǔ)連接到各個(gè)頂點(diǎn)的邊，入邊表中下標(biāo)為 i ii 的位置存儲(chǔ)的是連接到編號(hào)為 i ii 的頂點(diǎn)的邊。
如下圖：
說(shuō)明一下：
- 出邊表和入邊表類(lèi)似于哈希桶，其中每個(gè)位置存儲(chǔ)的都是一個(gè)鏈表，出邊表中下標(biāo)為 i 的位置的鏈表中存儲(chǔ)的都是從編號(hào)為 i 的頂點(diǎn)連接出去的邊，入邊表中下標(biāo)為 i 的位置的鏈表中存儲(chǔ)的都是連接到編號(hào)為 i 的頂點(diǎn)的邊。
- 在鄰接表中，出邊表中下標(biāo)為 i ii 的位置的鏈表中元素的個(gè)數(shù)就是編號(hào)為 i 的頂點(diǎn)的出度，入邊表中下標(biāo)為 i 的的位置的鏈表中元素的個(gè)數(shù)就是編號(hào)為 i 的頂點(diǎn)的入度。
- 在實(shí)現(xiàn)鄰接表時(shí)，一般只需要用一個(gè)出邊表來(lái)存儲(chǔ)從各個(gè)頂點(diǎn)連接出去的邊即可，因?yàn)榇蠖鄶?shù)情況下都是需要從一個(gè)頂點(diǎn)出發(fā)找與其相連的其他頂點(diǎn)，所以一般不需要存儲(chǔ)入邊表。
鄰接表的優(yōu)缺點(diǎn)
鄰接表的優(yōu)點(diǎn)：
- 鄰接表適合存儲(chǔ)稀疏圖，因?yàn)猷徑颖泶鎯?chǔ)圖時(shí)開(kāi)辟的空間大小取決于邊的數(shù)量，圖中邊的數(shù)量越少，鄰接表存儲(chǔ)邊時(shí)所需的內(nèi)存空間就越少。
- 鄰接表適合查找一個(gè)頂點(diǎn)連接出去的所有邊，出邊表中下標(biāo)為 i ii 的位置的鏈表中存儲(chǔ)的就是從頂點(diǎn) i ii 連接出去的所有邊。
鄰接表的缺點(diǎn)：
- 鄰接表不適合確定兩個(gè)頂點(diǎn)是否相連，需要遍歷出邊表中源頂點(diǎn)對(duì)應(yīng)位置的鏈表，該過(guò)程的時(shí)間復(fù)雜度是 O(E) ，其中 E 表示從源頂點(diǎn)連接出去的邊的數(shù)量。
鄰接表的實(shí)現(xiàn)
鏈表結(jié)點(diǎn)所需成員變量：
- 源頂點(diǎn)下標(biāo) srci ：表示邊的源頂點(diǎn)。
- 目標(biāo)頂點(diǎn)下標(biāo) dsti ：表示邊的目標(biāo)頂點(diǎn)。
- 權(quán)值 weight ：表示邊的權(quán)值。
- 指針 next ：連接下一個(gè)結(jié)點(diǎn)。
代碼如下：
//鄰接表
namespace LinkTable {
//鏈表結(jié)點(diǎn)定義
template<class W>
struct Edge {
//int _srci; //源頂點(diǎn)的下標(biāo)（可選）
int _dsti; //目標(biāo)頂點(diǎn)的下標(biāo)
W _weight; //邊的權(quán)值
Edge<W>* _next; //連接指針
Edge(int dsti, const W& weight)
:_dsti(dsti)
,_weight(weight)
,_next(nullptr)
{}
};
}
說(shuō)明一下：
- 對(duì)于出邊表來(lái)說(shuō)，下標(biāo)為 i 的位置的鏈表中存儲(chǔ)的邊的源頂點(diǎn)都是頂點(diǎn) i ，所以鏈表結(jié)點(diǎn)中的源頂點(diǎn)成員可以不用存儲(chǔ)。
- 對(duì)于入邊表來(lái)說(shuō)，下標(biāo)為 i 的位置的鏈表中存儲(chǔ)的邊的目標(biāo)頂點(diǎn)都是頂點(diǎn) i ，所以鏈表結(jié)點(diǎn)中的目標(biāo)頂點(diǎn)成員可以不用存儲(chǔ)。
鄰接表所需成員變量：
- 數(shù)組vertexs ：用于存儲(chǔ)頂點(diǎn)集合，頂點(diǎn)所在位置的下標(biāo)作為該頂點(diǎn)的編號(hào)。
- 映射關(guān)系vIndexMap ：用于建立頂點(diǎn)與其下標(biāo)的映射關(guān)系，便于根據(jù)頂點(diǎn)找到其對(duì)應(yīng)的下標(biāo)編號(hào)。
- 鄰接表（出邊表）linkTable ：用于存儲(chǔ)邊的集合，linkTable[i] 鏈表中存儲(chǔ)的邊的源頂點(diǎn)都是頂點(diǎn) i 。
鄰接表的實(shí)現(xiàn)：
- 為了支持任意類(lèi)型的頂點(diǎn)類(lèi)型以及權(quán)值，可以將圖定義為模板，其中 V 和 W 分別表示頂點(diǎn)和權(quán)值的類(lèi)型， Direction表示圖是否為有向圖，將Direction 的缺省值設(shè)置為false （無(wú)向圖居多）。
- 在構(gòu)造函數(shù)中完成頂點(diǎn)集合的設(shè)置，并建立各個(gè)頂點(diǎn)與其對(duì)應(yīng)下標(biāo)的映射關(guān)系，同時(shí)為鄰接表開(kāi)辟空間，將鄰接表中的值初始化為空指針，表示剛開(kāi)始時(shí)各個(gè)頂點(diǎn)之間均不相連。
- 提供一個(gè)接口用于添加邊，在添加邊時(shí)先分別獲取源頂點(diǎn)和目標(biāo)頂點(diǎn)對(duì)應(yīng)的下標(biāo)編號(hào)，然后在源頂點(diǎn)對(duì)應(yīng)的鏈表中頭插一個(gè)邊結(jié)點(diǎn)，如果圖為無(wú)向圖，則還需要在目標(biāo)頂點(diǎn)對(duì)應(yīng)的鏈表中頭插一個(gè)邊結(jié)點(diǎn)。
代碼如下：
//鄰接表
namespace LinkTable {
template<class V, class W, bool Direction = false>
class Graph {
typedef Edge<W> Edge;
public:
//構(gòu)造函數(shù)
Graph(const V* vertexs, int n)
:_vertexs(vertexs, vertexs + n) //設(shè)置頂點(diǎn)集合
, _linkTable(n, nullptr) { //開(kāi)辟鄰接表的空間
//建立頂點(diǎn)與下標(biāo)的映射關(guān)系
for (int i = 0; i < n; i++) {
_vIndexMap[vertexs[i]] = i;
}
}
//獲取頂點(diǎn)對(duì)應(yīng)的下標(biāo)
int getVertexIndex(const V& v) {
auto iter = _vIndexMap.find(v);
if (iter != _vIndexMap.end()) { //頂點(diǎn)存在
return iter->second;
}
else { //頂點(diǎn)不存在
throw invalid_argument("不存在的頂點(diǎn)");
return -1;
}
}
//添加邊
void addEdge(const V& src, const V& dst, const W& weight) {
int srci = getVertexIndex(src), dsti = getVertexIndex(dst); //獲取源頂點(diǎn)和目標(biāo)頂點(diǎn)的下標(biāo)
//添加從源頂點(diǎn)到目標(biāo)頂點(diǎn)的邊
Edge* sdEdge = new Edge(dsti, weight);
sdEdge->_next = _linkTable[srci];
_linkTable[srci] = sdEdge;
if (Direction == false) { //無(wú)向圖
//添加從目標(biāo)頂點(diǎn)到源頂點(diǎn)的邊
Edge* dsEdge = new Edge(srci, weight);
dsEdge->_next = _linkTable[dsti];
_linkTable[dsti] = dsEdge;
}
}
//打印頂點(diǎn)集合和鄰接表
void print() {
int n = _vertexs.size();
//打印頂點(diǎn)集合
for (int i = 0; i < n; i++) {
cout << "[" << i << "]->" << _vertexs[i] << " ";
}
cout << endl << endl;
//打印鄰接表
for (int i = 0; i < n; i++) {
Edge* cur = _linkTable[i];
cout << "[" << i << ":" << _vertexs[i] << "]->";
while (cur) {
cout << "[" << cur->_dsti << ":" << _vertexs[cur->_dsti] << ":" << cur->_weight << "]->";
cur = cur->_next;
}
cout << "nullptr" << endl;
}
}
private:
vector<V> _vertexs; //頂點(diǎn)集合
unordered_map<V, int> _vIndexMap; //頂點(diǎn)映射下標(biāo)
vector<Edge*> _linkTable; //鄰接表（出邊表）
};
}
說(shuō)明一下：
為了方便觀察，可以在類(lèi)中增加一個(gè)print 接口，用于打印頂點(diǎn)集合和鄰接表。
圖的遍歷
圖的遍歷指的是遍歷圖中的頂點(diǎn)，主要有廣度優(yōu)先遍歷和深度優(yōu)先遍歷兩種方式。
廣度優(yōu)先遍歷
廣度優(yōu)先遍歷
廣度優(yōu)先遍歷又稱(chēng)BFS，其遍歷過(guò)程類(lèi)似于二叉樹(shù)的層序遍歷，從起始頂點(diǎn)開(kāi)始一層一層向外進(jìn)行遍歷。
如下圖：
廣度優(yōu)先遍歷的實(shí)現(xiàn)：
- 廣度優(yōu)先遍歷需要借助一個(gè)隊(duì)列和一個(gè)標(biāo)記數(shù)組，利用隊(duì)列先進(jìn)先出的特點(diǎn)實(shí)現(xiàn)一層一層向外遍歷，利用標(biāo)記數(shù)組來(lái)記錄各個(gè)頂點(diǎn)是否被訪問(wèn)過(guò)。
- 剛開(kāi)始時(shí)將起始頂點(diǎn)入隊(duì)列，并將起始頂點(diǎn)標(biāo)記為訪問(wèn)過(guò)，然后不斷從隊(duì)列中取出頂點(diǎn)進(jìn)行訪問(wèn)，并判斷該頂點(diǎn)是否有鄰接頂點(diǎn)，如果有鄰接頂點(diǎn)并且該鄰接頂點(diǎn)沒(méi)有被訪問(wèn)過(guò)，則將該鄰接頂點(diǎn)入隊(duì)列，并在入隊(duì)列后立即將該鄰接頂點(diǎn)標(biāo)記為訪問(wèn)過(guò)。
代碼如下：
//鄰接矩陣
namespace Matrix {
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph {
public:
//廣度優(yōu)先遍歷
void bfs(const V& src) {
int srci = getVertexIndex(src); //起始頂點(diǎn)的下標(biāo)
queue<int> q; //隊(duì)列
vector<bool> visited(_vertexs.size(), false); //標(biāo)記數(shù)組
q.push(srci); //起始頂點(diǎn)入隊(duì)列
visited[srci] = true; //起始頂點(diǎn)標(biāo)記為訪問(wèn)過(guò)
while (!q.empty()) {
int front = q.front();
q.pop();
cout << _vertexs[front] << " ";
for (int i = 0; i < _vertexs.size(); i++) { //找出從front連接出去的頂點(diǎn)
if (_matrix[front][i] != MAX_W && visited[i] == false) { //是鄰接頂點(diǎn)，并且沒(méi)有被訪問(wèn)過(guò)
q.push(i); //入隊(duì)列
visited[i] = true; //標(biāo)記為訪問(wèn)過(guò)
}
}
}
cout << endl;
}
private:
vector<V> _vertexs; //頂點(diǎn)集合
unordered_map<V, int> _vIndexMap; //頂點(diǎn)映射下標(biāo)
vector<vector<W>> _matrix; //鄰接矩陣
};
}
說(shuō)明一下：
- 為了防止頂點(diǎn)被重復(fù)加入隊(duì)列導(dǎo)致死循環(huán)，因此需要一個(gè)標(biāo)記數(shù)組，當(dāng)一個(gè)頂點(diǎn)被訪問(wèn)過(guò)后就不應(yīng)該再將其加入隊(duì)列了。
- 如果當(dāng)一個(gè)頂點(diǎn)從隊(duì)列中取出訪問(wèn)時(shí)才再將其標(biāo)記為訪問(wèn)過(guò)，也可能會(huì)存在頂點(diǎn)被重復(fù)加入隊(duì)列的情況，比如當(dāng)圖中的頂點(diǎn)B出隊(duì)列時(shí)，頂點(diǎn)C作為頂點(diǎn)B的鄰接頂點(diǎn)并且還沒(méi)有被訪問(wèn)過(guò)（頂點(diǎn)C還在隊(duì)列中），此時(shí)頂點(diǎn)C就會(huì)再次被加入隊(duì)列，因此最好在一個(gè)頂點(diǎn)被入隊(duì)列時(shí)就將其標(biāo)記為訪問(wèn)過(guò)。
- 如果所給圖不是一個(gè)連通圖，那么從一個(gè)頂點(diǎn)開(kāi)始進(jìn)行廣度優(yōu)先遍歷，無(wú)法遍歷完圖中的所有頂點(diǎn)，這時(shí)可以遍歷標(biāo)記數(shù)組，查看哪些頂點(diǎn)還沒(méi)有被訪問(wèn)過(guò)，對(duì)于沒(méi)有被訪問(wèn)過(guò)的頂點(diǎn)，則從該頂點(diǎn)處繼續(xù)進(jìn)行廣度優(yōu)先遍歷，直到圖中所有的頂點(diǎn)都被訪問(wèn)過(guò)。
深度優(yōu)先遍歷
深度優(yōu)先遍歷
深度優(yōu)先遍歷又稱(chēng)DFS，其遍歷過(guò)程類(lèi)似于二叉樹(shù)的先序遍歷，從起始頂點(diǎn)開(kāi)始不斷對(duì)頂點(diǎn)進(jìn)行深入遍歷。
如下圖：
深度優(yōu)先遍歷的實(shí)現(xiàn)：
- 深度優(yōu)先遍歷可以通過(guò)遞歸實(shí)現(xiàn)，同時(shí)也需要借助一個(gè)標(biāo)記數(shù)組來(lái)記錄各個(gè)頂點(diǎn)是否被訪問(wèn)過(guò)。
- 從起始頂點(diǎn)處開(kāi)始進(jìn)行遞歸遍歷，在遍歷過(guò)程中先對(duì)當(dāng)前頂點(diǎn)進(jìn)行訪問(wèn)，并將其標(biāo)記為訪問(wèn)過(guò)，然后判斷該頂點(diǎn)是否有鄰接頂點(diǎn)，如果有鄰接頂點(diǎn)并且該鄰接頂點(diǎn)沒(méi)有被訪問(wèn)過(guò)，則遞歸遍歷該鄰接頂點(diǎn)。
代碼如下：
//鄰接矩陣
namespace Matrix {
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph {
public:
//深度優(yōu)先遍歷（子函數(shù)）
void _dfs(int srci, vector<bool>& visited) {
cout << _vertexs[srci] << " "; //訪問(wèn)
visited[srci] = true; //標(biāo)記為訪問(wèn)過(guò)
for (int i = 0; i < _vertexs.size(); i++) { //找從srci連接出去的頂點(diǎn)
if (_matrix[srci][i] != MAX_W && visited[i] == false) { //是鄰接頂點(diǎn)，并且沒(méi)有被訪問(wèn)過(guò)
_dfs(i, visited); //遞歸遍歷
}
}
}
//深度優(yōu)先遍歷
void dfs(const V& src) {
int srci = getVertexIndex(src); //起始頂點(diǎn)的下標(biāo)
vector<bool> visited(_vertexs.size(), false); //標(biāo)記數(shù)組
_dfs(srci, visited); //遞歸遍歷
cout << endl;
}
private:
vector<V> _vertexs; //頂點(diǎn)集合
unordered_map<V, int> _vIndexMap; //頂點(diǎn)映射下標(biāo)
vector<vector<W>> _matrix; //鄰接矩陣
};
}
說(shuō)明一下：
- 如果所給圖不是一個(gè)連通圖，那么從一個(gè)頂點(diǎn)開(kāi)始進(jìn)行深度優(yōu)先遍歷，無(wú)法遍歷完圖中的所有頂點(diǎn)，這時(shí)可以遍歷標(biāo)記數(shù)組，查看哪些頂點(diǎn)還沒(méi)有被訪問(wèn)過(guò)，對(duì)于沒(méi)有被訪問(wèn)過(guò)的頂點(diǎn)，則從該頂點(diǎn)處繼續(xù)進(jìn)行深度優(yōu)先遍歷，直到圖中所有的頂點(diǎn)都被訪問(wèn)過(guò)。
最小生成樹(shù)
最小生成樹(shù)
關(guān)于最小生成樹(shù)：
- 一個(gè)連通圖的最小連通子圖稱(chēng)為該圖的生成樹(shù)，若連通圖由 n 個(gè)頂點(diǎn)組成，則其生成樹(shù)必含 n 個(gè)頂點(diǎn)和 n?1 條邊，最小生成樹(shù)指的是一個(gè)圖的生成樹(shù)中，總權(quán)值最小的生成樹(shù)。
- 連通圖中的每一棵生成樹(shù)都是原圖的一個(gè)極大無(wú)環(huán)子圖，從其中刪去任何一條邊，生成樹(shù)就不再連通，在其中引入任何一條新邊，都會(huì)形成一條回路。
說(shuō)明一下：
- 對(duì)于各個(gè)頂點(diǎn)來(lái)說(shuō)，除了第一個(gè)頂點(diǎn)之外，其他每個(gè)頂點(diǎn)想要連接到圖中，至少需要一條邊使其連接進(jìn)來(lái)，所以由 n 個(gè)頂點(diǎn)的連通圖的生成樹(shù)有 n個(gè)頂點(diǎn)和 n ? 1 條邊。
- 對(duì)于生成樹(shù)來(lái)說(shuō)，圖中的每個(gè)頂點(diǎn)已經(jīng)連通了，如果再引入一條新邊，那么必然會(huì)使得被新邊相連的兩個(gè)頂點(diǎn)之間存在一條直接路徑和一條間接路徑，即形成回路。
- 最小生成樹(shù)是圖的生成樹(shù)中總權(quán)值最小的生成樹(shù)，生成樹(shù)是圖的最小連通子圖，而連通圖是無(wú)向圖的概念，有向圖對(duì)應(yīng)的是強(qiáng)連通圖，所以最小生成樹(shù)算法的處理對(duì)象都是無(wú)向圖。
構(gòu)成最小生成樹(shù)的準(zhǔn)則
構(gòu)造最小生成樹(shù)的準(zhǔn)則如下：
- 只能使用圖中的邊來(lái)構(gòu)造最小生成樹(shù)。
- 只能使用恰好n?1 條邊來(lái)連接圖中的n 個(gè)頂點(diǎn)。
- 選用的n?1 條邊不能構(gòu)成回路。
- 構(gòu)造最小生成樹(shù)的算法有Kruskal算法和Prim算法，這兩個(gè)算法都采用了逐步求解的貪心策略。
Kruskal算法
Kruskal算法（克魯斯卡爾算法）
Kruskal算法的基本思想如下：
- 構(gòu)造一個(gè)含 n 個(gè)頂點(diǎn)、不含任何邊的圖作為最小生成樹(shù)，對(duì)原圖中的各個(gè)邊按權(quán)值進(jìn)行排序。
- 每次從原圖中選出一條最小權(quán)值的邊，將其加入到最小生成樹(shù)中，如果加入這條邊會(huì)使得最小生成樹(shù)中構(gòu)成回路，則重新選擇一條邊。
- 按照上述規(guī)則不斷選邊，當(dāng)選出n?1 條合法的邊時(shí)，則說(shuō)明最小生成樹(shù)構(gòu)造完畢，如果無(wú)法選出n?1 條合法的邊，則說(shuō)明原圖不存在最小生成樹(shù)。
動(dòng)圖演示：
Kruskal算法的實(shí)現(xiàn)：
- 根據(jù)原圖設(shè)置最小生成樹(shù)的頂點(diǎn)集合，以及頂點(diǎn)與下標(biāo)的映射關(guān)系，開(kāi)辟最小生成樹(shù)的鄰接矩陣空間，并將矩陣中的值初始化為 MAX_W ，表示剛開(kāi)始時(shí)最小生成樹(shù)中不含任何邊。
- 遍歷原圖的鄰接矩陣，按權(quán)值將原圖中的所有邊添加到優(yōu)先級(jí)隊(duì)列（小堆）中，為了避免重復(fù)添加相同的邊，在遍歷原圖的鄰接矩陣時(shí)只應(yīng)該遍歷矩陣的一半。
- 使用一個(gè)并查集來(lái)輔助判環(huán)操作，剛開(kāi)始時(shí)圖中的頂點(diǎn)各自為一個(gè)集合，當(dāng)兩個(gè)頂點(diǎn)相連時(shí)將這兩個(gè)頂點(diǎn)對(duì)應(yīng)的集合進(jìn)行合并，使得連通的頂點(diǎn)在同一個(gè)集合，這樣通過(guò)并查集就能判斷所選的邊是否會(huì)使得最小生成樹(shù)中構(gòu)成回路，如果所選邊連接的兩個(gè)頂點(diǎn)本就在同一個(gè)集合，那么加入這條邊就會(huì)構(gòu)成回路。
- 使用count 和totalWeight 分別記錄所選邊的數(shù)量和最小生成樹(shù)的總權(quán)值，當(dāng) count 的值等于n?1 時(shí)則停止選邊，此時(shí)可以將最小生成樹(shù)的總權(quán)值作為返回值進(jìn)行返回。
- 每次選邊時(shí)從優(yōu)先級(jí)隊(duì)列中獲取一個(gè)權(quán)值最小的邊，并通過(guò)并查集判斷這條邊連接的兩個(gè)頂點(diǎn)是否在同一個(gè)集合，如果在則重新選邊，如果不在則將這條邊添加到最小生成樹(shù)中，并將這條邊連接的兩個(gè)頂點(diǎn)對(duì)應(yīng)的集合進(jìn)行合并，同時(shí)更新count 和 totalWeight 的值。
- 當(dāng)選邊結(jié)束時(shí)，如果 count 的值等于 n?1 ，則說(shuō)明最小生成樹(shù)構(gòu)造成功，否則說(shuō)明原圖無(wú)法構(gòu)造出最小生成樹(shù)。
代碼如下：
//鄰接矩陣
namespace Matrix {
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph {
public:
//強(qiáng)制生成默認(rèn)構(gòu)造
Graph() = default;
void _addEdge(int srci, int dsti, const W& weight) {
_matrix[srci][dsti] = weight; //設(shè)置鄰接矩陣中對(duì)應(yīng)的值
if (Direction == false) { //無(wú)向圖
_matrix[dsti][srci] = weight; //添加從目標(biāo)頂點(diǎn)到源頂點(diǎn)的邊
}
}
//添加邊
void addEdge(const V& src, const V& dst, const W& weight) {
int srci = getVertexIndex(src), dsti = getVertexIndex(dst); //獲取源頂點(diǎn)和目標(biāo)頂點(diǎn)的下標(biāo)
_addEdge(srci, dsti, weight);
}
//邊
struct Edge {
int _srci; //源頂點(diǎn)的下標(biāo)
int _dsti; //目標(biāo)頂點(diǎn)的下標(biāo)
W _weight; //邊的權(quán)值
Edge(int srci, int dsti, const W& weight)
:_srci(srci)
, _dsti(dsti)
, _weight(weight)
{}
bool operator>(const Edge& edge) const{
return _weight > edge._weight;
}
};
//獲取當(dāng)前圖的最小生成樹(shù)（Kruskal算法）
W Kruskal(Graph<V, W, MAX_W, Direction>& minTree) {
int n = _vertexs.size();
//設(shè)置最小生成樹(shù)的各個(gè)成員變量
minTree._vertexs = _vertexs; //設(shè)置最小生成樹(shù)的頂點(diǎn)集合
minTree._vIndexMap = _vIndexMap; //設(shè)置最小生成樹(shù)頂點(diǎn)與下標(biāo)的映射
minTree._matrix.resize(n, vector<W>(n, MAX_W)); //開(kāi)辟最小生成樹(shù)的二維數(shù)組空間
priority_queue<Edge, vector<Edge>, greater<Edge>> minHeap; //優(yōu)先級(jí)隊(duì)列（小堆）
//將所有邊添加到優(yōu)先級(jí)隊(duì)列
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) { //只遍歷矩陣的一半，避免重復(fù)添加相同的邊
if (_matrix[i][j] != MAX_W)
minHeap.push(Edge(i, j, _matrix[i][j]));
}
}
UnionFindSet ufs(n); //n個(gè)頂點(diǎn)的并查集
int count = 0; //已選邊的數(shù)量
W totalWeight = W(); //最小生成樹(shù)的總權(quán)值
while (!minHeap.empty() && count < n - 1) {
//從優(yōu)先級(jí)隊(duì)列中獲取一個(gè)權(quán)值最小的邊
Edge minEdge = minHeap.top();
minHeap.pop();
int srci = minEdge._srci, dsti = minEdge._dsti;
W weight = minEdge._weight;
if (!ufs.inSameSet(srci, dsti)) { //邊的源頂點(diǎn)和目標(biāo)頂點(diǎn)不在同一個(gè)集合
minTree._addEdge(srci, dsti, weight); //在最小生成樹(shù)中添加邊
ufs.unionSet(srci, dsti); //合并源頂點(diǎn)和目標(biāo)頂點(diǎn)對(duì)應(yīng)的集合
count++;
totalWeight += weight;
cout << "選邊: " << _vertexs[srci] << "->" << _vertexs[dsti] << ":" << weight << endl;
}
else { //邊的源頂點(diǎn)和目標(biāo)頂點(diǎn)在同一個(gè)集合，加入這條邊會(huì)構(gòu)成環(huán)
cout << "成環(huán): " << _vertexs[srci] << "->" << _vertexs[dsti] << ":" << weight << endl;
}
}
if (count == n - 1) {
cout << "構(gòu)建最小生成樹(shù)成功" << endl;
return totalWeight;
}
else {
cout << "無(wú)法構(gòu)成最小生成樹(shù)" << endl;
return W();
}
}
private:
vector<V> _vertexs; //頂點(diǎn)集合
unordered_map<V, int> _vIndexMap; //頂點(diǎn)映射下標(biāo)
vector<vector<W>> _matrix; //鄰接矩陣
};
}
說(shuō)明一下：
- 在獲取圖的最小生成樹(shù)時(shí)，會(huì)以無(wú)參的方式定義一個(gè)最小生成樹(shù)對(duì)象，然后用原圖對(duì)象調(diào)用上述Kruskal函數(shù)，通過(guò)輸出型參數(shù)的方式獲取原圖的最小生成樹(shù)，由于我們定義了一個(gè)帶參的構(gòu)造函數(shù)，使得編譯器不再生成默認(rèn)構(gòu)造函數(shù)，因此需要通過(guò)default關(guān)鍵字強(qiáng)制生成Graph類(lèi)的默認(rèn)構(gòu)造函數(shù)。
- 一條邊包含兩個(gè)頂點(diǎn)和邊的權(quán)值，可以定義一個(gè)Edge結(jié)構(gòu)體來(lái)描述一條邊，結(jié)構(gòu)體內(nèi)包含邊的源頂點(diǎn)和目標(biāo)頂點(diǎn)的下標(biāo)以及邊的權(quán)值，在使用優(yōu)先級(jí)隊(duì)列構(gòu)造小堆結(jié)構(gòu)時(shí)，需要存儲(chǔ)的對(duì)象之間能夠支持 > 運(yùn)算符操作，因此需要對(duì)Edge結(jié)構(gòu)體的 > 運(yùn)算符進(jìn)行重載，將其重載為邊的權(quán)值的比較。
- 當(dāng)選出的邊不會(huì)構(gòu)成回路時(shí)，需要將這條邊插入到最小生成樹(shù)對(duì)應(yīng)的圖中，此時(shí)已經(jīng)知道了這條邊的源頂點(diǎn)和目標(biāo)頂點(diǎn)對(duì)應(yīng)的下標(biāo)，可以在Graph類(lèi)中新增一個(gè)_addEdge子函數(shù)，該函數(shù)支持通過(guò)源頂點(diǎn)和目標(biāo)頂點(diǎn)的下標(biāo)向圖中插入邊，而Graph類(lèi)中原有的addEdge函數(shù)可以復(fù)用這個(gè)_addEdge子函數(shù)。
- 最小生成樹(shù)不一定是唯一的，特別是當(dāng)原圖中存在很多權(quán)值相等的邊的時(shí)候，比如對(duì)于動(dòng)圖中的圖來(lái)說(shuō)，將最小生成樹(shù)中的bc 邊換成 ah 邊也是一棵最小生成樹(shù)。
- 上述代碼中通過(guò)優(yōu)先級(jí)隊(duì)列構(gòu)造小堆來(lái)依次獲取權(quán)值最小的邊，你也可以通過(guò)其他排序算法按權(quán)值對(duì)邊進(jìn)行排序，然后按權(quán)值從小到大依次遍歷各個(gè)邊進(jìn)行選邊操作。
Prim算法
Prim算法（普里姆算法）
Prim算法的基本思想如下：
- 構(gòu)造一個(gè)含 n 個(gè)頂點(diǎn)、不含任何邊的圖作為最小生成樹(shù)，將圖中的頂點(diǎn)分為兩個(gè)集合，forest 集合中的頂點(diǎn)是已經(jīng)連接到最小生成樹(shù)中的頂點(diǎn)，remain 集合中的頂點(diǎn)是還沒(méi)有連接到最小生成樹(shù)中的頂點(diǎn)，剛開(kāi)始時(shí) forest 集合中只包含給定的起始頂點(diǎn)。
- 每次從連接forest 集合與 remain 集合的所有邊中選出一條權(quán)值最小的邊，將其加入到最小生成樹(shù)中，由于選出來(lái)的邊對(duì)應(yīng)的兩個(gè)頂點(diǎn)一個(gè)屬于forest 集合，另一個(gè)屬于 remain 集合，因此是不會(huì)構(gòu)成回路的。
- 按照上述規(guī)則不斷選邊，當(dāng)選出 n?1 條邊時(shí)，所有的頂點(diǎn)都已經(jīng)加入到了 forest 集合，此時(shí)最小生成樹(shù)構(gòu)造完畢，如果無(wú)法選出 n?1 條邊，則說(shuō)明原圖不存在最小生成樹(shù)。
最短路徑
關(guān)于最短路徑：
- 最短路徑問(wèn)題：從帶權(quán)有向圖中的某一頂點(diǎn)出發(fā)，找出一條通往另一頂點(diǎn)的最短路徑，最短指的是路徑各邊的權(quán)值總和達(dá)到最小，最短路徑可分為單源最短路徑和多源最短路徑。
- 單源最短路徑指的是從圖中某一頂點(diǎn)出發(fā)，找出通往其他所有頂點(diǎn)的最短路徑，而多源最短路徑指的是，找出圖中任意兩個(gè)頂點(diǎn)之間的最短路徑。
Prim算法的實(shí)現(xiàn)：
- 根據(jù)原圖設(shè)置最小生成樹(shù)的頂點(diǎn)集合，以及頂點(diǎn)與下標(biāo)的映射關(guān)系，開(kāi)辟最小生成樹(shù)的鄰接矩陣空間，并將矩陣中的值初始化為 MAX_W ，表示剛開(kāi)始時(shí)最小生成樹(shù)中不含任何邊。
- 使用一個(gè)forest 數(shù)組來(lái)表示各個(gè)頂點(diǎn)是否在 forest 集合中，剛開(kāi)始時(shí)只有起始頂點(diǎn)在 forest 集合中，并將所有從起始頂點(diǎn)連接出去的邊加入優(yōu)先級(jí)隊(duì)列（小堆），這些邊就是剛開(kāi)始時(shí)連接 forest 集合與remain 集合的邊。
- 使用 count 和 totalWeight 分別記錄所選邊的數(shù)量和最小生成樹(shù)的總權(quán)值，當(dāng)count 的值等于 n?1 時(shí)則停止選邊，此時(shí)將最小生成樹(shù)的總權(quán)值作為返回值進(jìn)行返回。
- 每次選邊時(shí)從優(yōu)先級(jí)隊(duì)列中獲取一個(gè)權(quán)值最小的邊，將這條邊添加到最小生成樹(shù)中，并將這條邊的目標(biāo)頂點(diǎn)加入 forest 集合中，同時(shí)更新 count 和 totalWeight 的值。此外，還需要將從這條邊的目標(biāo)頂點(diǎn)連接出去的邊加入優(yōu)先級(jí)隊(duì)列，但是需要保證加入的邊的目標(biāo)頂點(diǎn)不能在 forest 集合，否則后續(xù)選出源頂點(diǎn)和目標(biāo)頂點(diǎn)都在forest 集合的邊就會(huì)構(gòu)成回路。
- 需要注意的是，每次從優(yōu)先級(jí)隊(duì)列中選出一個(gè)權(quán)值最小的邊時(shí)，還需要保證選出的這條邊的目標(biāo)頂點(diǎn)不在forest 集合中，避免構(gòu)成回路。雖然向優(yōu)先級(jí)隊(duì)列中加入邊時(shí)保證了加入的邊的目標(biāo)頂點(diǎn)不在forest 集合中，但經(jīng)過(guò)后續(xù)不斷的選邊，可能會(huì)導(dǎo)致之前加入優(yōu)先級(jí)隊(duì)列中的某些邊的目標(biāo)頂點(diǎn)也被加入到了forest 集合中。
- 當(dāng)選邊結(jié)束時(shí)，如果 count 的值等于 n?1 ，則說(shuō)明最小生成樹(shù)構(gòu)造成功，否則說(shuō)明原圖無(wú)法構(gòu)造出最小生成樹(shù)。
代碼如下：
//鄰接矩陣
namespace Matrix {
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph {
public:
//邊
struct Edge {
int _srci; //源頂點(diǎn)的下標(biāo)
int _dsti; //目標(biāo)頂點(diǎn)的下標(biāo)
W _weight; //邊的權(quán)值
Edge(int srci, int dsti, const W& weight)
:_srci(srci)
, _dsti(dsti)
, _weight(weight)
{}
bool operator>(const Edge& edge) const{
return _weight > edge._weight;
}
};
//獲取當(dāng)前圖的最小生成樹(shù)（Prim算法）
W Prim(Graph<V, W, MAX_W, Direction>& minTree, const V& start) {
int n = _vertexs.size();
//設(shè)置最小生成樹(shù)的各個(gè)成員變量
minTree._vertexs = _vertexs; //設(shè)置最小生成樹(shù)的頂點(diǎn)集合
minTree._vIndexMap = _vIndexMap; //設(shè)置最小生成樹(shù)頂點(diǎn)與下標(biāo)的映射
minTree._matrix.resize(n, vector<W>(n, MAX_W)); //開(kāi)辟最小生成樹(shù)的二維數(shù)組空間
int starti = getVertexIndex(start); //獲取起始頂點(diǎn)的下標(biāo)
vector<bool> forest(n, false);
forest[starti] = true;
priority_queue<Edge, vector<Edge>, greater<Edge>> minHeap; //優(yōu)先級(jí)隊(duì)列（小堆）
//將從起始頂點(diǎn)連接出去的邊加入優(yōu)先級(jí)隊(duì)列
for (int i = 0; i < n; i++) {
if (_matrix[starti][i] != MAX_W)
minHeap.push(Edge(starti, i, _matrix[starti][i]));
}
int count = 0; //已選邊的數(shù)量
W totalWeight = W(); //最小生成樹(shù)的總權(quán)值
while (!minHeap.empty() && count < n - 1) {
//從優(yōu)先級(jí)隊(duì)列中獲取一個(gè)權(quán)值最小的邊
Edge minEdge = minHeap.top();
minHeap.pop();
int srci = minEdge._srci, dsti = minEdge._dsti;
W weight = minEdge._weight;
if (forest[dsti] == false) { //邊的目標(biāo)頂點(diǎn)還沒(méi)有被加入到forest集合中
//將從目標(biāo)頂點(diǎn)連接出去的邊加入優(yōu)先級(jí)隊(duì)列
for (int i = 0; i < n; i++) {
if (_matrix[dsti][i] != MAX_W && forest[i] == false) //加入的邊的目標(biāo)頂點(diǎn)不能在forest集合中
minHeap.push(Edge(dsti, i, _matrix[dsti][i]));
}
minTree._addEdge(srci, dsti, weight); //在最小生成樹(shù)中添加邊
forest[dsti] = true; //將邊的目標(biāo)頂點(diǎn)加入forest集合
count++;
totalWeight += weight;
cout << "選邊: " << _vertexs[srci] << "->" << _vertexs[dsti] << ":" << weight << endl;
}
else { //邊的目標(biāo)頂點(diǎn)已經(jīng)在forest集合中，加入這條邊會(huì)構(gòu)成環(huán)
cout << "成環(huán): " << _vertexs[srci] << "->" << _vertexs[dsti] << ":" << weight << endl;
}
}
if (count == n - 1) {
cout << "構(gòu)建最小生成樹(shù)成功" << endl;
return totalWeight;
}
else {
cout << "無(wú)法構(gòu)成最小生成樹(shù)" << endl;
return W();
}
}
private:
vector<V> _vertexs; //頂點(diǎn)集合
unordered_map<V, int> _vIndexMap; //頂點(diǎn)映射下標(biāo)
vector<vector<W>> _matrix; //鄰接矩陣
};
}
說(shuō)明一下：
- Prim算法構(gòu)造最小生成樹(shù)的思想在選邊時(shí)是不需要判環(huán)，但上述利用優(yōu)先級(jí)隊(duì)列實(shí)現(xiàn)的過(guò)程中仍需判環(huán)，如果在每次選邊的時(shí)候能夠通過(guò)某種方式，從連接forest 集合和remain 集合的所有邊中選出權(quán)值最小的邊，那么就無(wú)需判環(huán)，但這兩個(gè)集合中的頂點(diǎn)是不斷在變化的，每次選邊時(shí)都遍歷連接兩個(gè)集合的所有邊，該過(guò)程的時(shí)間復(fù)雜度較高。
- Kruskal算法本質(zhì)是一種全局的貪心，每次選邊時(shí)都是在所有邊中選出權(quán)值最小的邊，而Prim算法本質(zhì)是一種局部的貪心，每次選邊時(shí)是從連接 forest 集合和 remain 集合的所有邊中選出權(quán)值最小的邊。
最短路徑
最短路徑
關(guān)于最短路徑：
- 最短路徑問(wèn)題：從帶權(quán)有向圖中的某一頂點(diǎn)出發(fā)，找出一條通往另一頂點(diǎn)的最短路徑，最短指的是路徑各邊的權(quán)值總和達(dá)到最小，最短路徑可分為單源最短路徑和多源最短路徑。
- 單源最短路徑指的是從圖中某一頂點(diǎn)出發(fā)，找出通往其他所有頂點(diǎn)的最短路徑，而多源最短路徑指的是，找出圖中任意兩個(gè)頂點(diǎn)之間的最短路徑。
單源最短路徑-Dijkstra算法
Dijkstra算法（迪杰斯特拉算法）
使用前提：圖中所有邊的權(quán)值非負(fù)。
Dijkstra算法的基本思想如下：
- 將圖中的頂點(diǎn)分為兩個(gè)集合，集合 S 中的頂點(diǎn)是已經(jīng)確定從源頂點(diǎn)到該頂點(diǎn)的最短路徑的頂點(diǎn)，集合 Q 中的頂點(diǎn)是尚未確定從源頂點(diǎn)到該頂點(diǎn)的最短路徑的頂點(diǎn)。
- 每個(gè)頂點(diǎn)都有一個(gè)估計(jì)值，表示從源頂點(diǎn)到該頂點(diǎn)的可能最短路徑長(zhǎng)度，每次從集合Q 中選出一個(gè)估計(jì)值最小的頂點(diǎn)，將其加入到集合 S 中，并對(duì)該頂點(diǎn)連接出去的頂點(diǎn)的估計(jì)值和前驅(qū)頂點(diǎn)進(jìn)行松弛更新。
- 按照上述步驟不斷從集合 Q 中選取估計(jì)值最小的頂點(diǎn)到集合 S 中，直到所有的頂點(diǎn)都被加入到集合 S 中，此時(shí)通過(guò)各個(gè)頂點(diǎn)的估計(jì)值就可以得知源頂點(diǎn)到該頂點(diǎn)的最短路徑長(zhǎng)度，通過(guò)各個(gè)頂點(diǎn)的前驅(qū)頂點(diǎn)就可以得知最短路徑的走向。
動(dòng)圖演示：
Dijkstra算法的實(shí)現(xiàn)：
- 使用一個(gè)dist 數(shù)組來(lái)記錄從源頂點(diǎn)到各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度估計(jì)值，初始時(shí)將源頂點(diǎn)的估計(jì)值設(shè)置為權(quán)值的缺省值（比如int就是0），表示從源頂點(diǎn)到源頂點(diǎn)的路徑長(zhǎng)度為0，將其余頂點(diǎn)的估計(jì)值設(shè)置為MAX_W，表示從源頂點(diǎn)暫時(shí)無(wú)法到達(dá)其他頂點(diǎn)。
- 使用一個(gè)PathparentPath 數(shù)組來(lái)記錄到達(dá)各個(gè)頂點(diǎn)路徑的前驅(qū)頂點(diǎn)，初始時(shí)將各個(gè)頂點(diǎn)的前驅(qū)頂點(diǎn)初始化為-1，表示各個(gè)頂點(diǎn)暫時(shí)只能自己到達(dá)自己，沒(méi)有前驅(qū)頂點(diǎn)。
- 使用一個(gè)bool 數(shù)組來(lái)記錄各個(gè)頂點(diǎn)是否在 S 集合中，初始時(shí)所有頂點(diǎn)均不在S 集合，表示各個(gè)頂點(diǎn)都還沒(méi)有確定最短路徑。
- 每次從 Q 集合中選出一個(gè)估計(jì)值最小的頂點(diǎn) u，將其加入到 S 集合，并對(duì)頂點(diǎn)u 連接出去的各個(gè)頂點(diǎn)v 進(jìn)行松弛更新，如果能夠?qū)㈨旤c(diǎn) v 更新出更小的估計(jì)值，則更新其估計(jì)值，并將被更新的頂點(diǎn) v 的前驅(qū)頂點(diǎn)改為頂點(diǎn) u ，因?yàn)閺捻旤c(diǎn) u 到頂點(diǎn) v 能夠得到更小的估計(jì)值，所以在當(dāng)前看來(lái)（后續(xù)可能還會(huì)更新）到達(dá)頂點(diǎn) v 的最短路徑的前驅(qū)頂點(diǎn)就應(yīng)該是頂點(diǎn) u ，如果不能將頂點(diǎn) v 更新出更小的估計(jì)值，則維持原樣。
- 當(dāng)所有的頂點(diǎn)都加入集合 S 后，dist 數(shù)組中存儲(chǔ)的就是從源頂點(diǎn)到各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度，parentPath 數(shù)組中存儲(chǔ)的就是從源頂點(diǎn)到各個(gè)頂點(diǎn)的最短路徑的前驅(qū)頂點(diǎn)，通過(guò)不斷查找各個(gè)頂點(diǎn)的前驅(qū)頂點(diǎn)，最終就能得到從源頂點(diǎn)到各個(gè)頂點(diǎn)的最短路徑。
代碼如下：
//鄰接矩陣
namespace Matrix {
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph {
public:
//獲取單源最短路徑（Dijkstra算法）
void Dijkstra(const V& src, vector<W>& dist, vector<int>& parentPath) {
int n = _vertexs.size();
int srci = getVertexIndex(src); //獲取源頂點(diǎn)的下標(biāo)
dist.resize(n, MAX_W); //各個(gè)頂點(diǎn)的估計(jì)值初始化為MAX_W
parentPath.resize(n, -1); //各個(gè)頂點(diǎn)的前驅(qū)頂點(diǎn)初始化為-1
dist[srci] = W(); //源頂點(diǎn)的估計(jì)值設(shè)置為權(quán)值的缺省值
vector<bool> S(n, false); //已經(jīng)確定最短路徑的頂點(diǎn)集合
for (int i = 0; i < n; i++) { //將Q集合中的n個(gè)頂點(diǎn)全部加入到S集合
//從集合Q中選出一個(gè)估計(jì)值最小的頂點(diǎn)
W minW = MAX_W; //最小估計(jì)值
int u = -1; //估計(jì)值最小的頂點(diǎn)
for (int j = 0; j < n; j++) {
if (S[j] == false && dist[j] < minW) {
minW = dist[j];
u = j;
}
}
S[u] = true; //將選出的頂點(diǎn)加入到S集合
//對(duì)u連接出去的頂點(diǎn)進(jìn)行松弛更新
for (int v = 0; v < n; v++) {
if (S[v] == false && _matrix[u][v] != MAX_W && dist[u] + _matrix[u][v] < dist[v]) { //松弛的頂點(diǎn)不能在S集合
dist[v] = dist[u] + _matrix[u][v]; //松弛更新出更小的估計(jì)值
parentPath[v] = u; //更新路徑的前驅(qū)頂點(diǎn)
}
}
}
}
//打印最短路徑及路徑權(quán)值
void printShortPath(const V& src, const vector<W>& dist, const vector<int>& parentPath) {
int n = _vertexs.size();
int srci = getVertexIndex(src); //獲取源頂點(diǎn)的下標(biāo)
for (int i = 0; i < n; i++) {
vector<int> path;
int cur = i;
while (cur != -1) { //源頂點(diǎn)的前驅(qū)頂點(diǎn)為-1
path.push_back(cur);
cur = parentPath[cur];
}
reverse(path.begin(), path.end()); //逆置
for (int j = 0; j < path.size(); j++) {
cout << _vertexs[path[j]] << "->";
}
cout << "路徑權(quán)值: " << dist[i] << "" << endl;
}
}
private:
vector<V> _vertexs; //頂點(diǎn)集合
unordered_map<V, int> _vIndexMap; //頂點(diǎn)映射下標(biāo)
vector<vector<W>> _matrix; //鄰接矩陣
};
}
說(shuō)明一下：
- 為了方便觀察，可以在類(lèi)中增加一個(gè) printShortPath 接口，用于根據(jù) dist 和 parentPath 數(shù)組來(lái)打印最短路徑及路徑權(quán)值。
- 對(duì)于從源頂點(diǎn) s 到目標(biāo)頂點(diǎn) j 的最短路徑來(lái)說(shuō)，如果最短路徑經(jīng)過(guò)了頂點(diǎn) i ，那么最短路徑中從源頂點(diǎn) s 到頂點(diǎn) i 的這條子路徑一定是源頂點(diǎn) s 到頂點(diǎn) i 的最短路徑，因此可以通過(guò)存儲(chǔ)前驅(qū)頂點(diǎn)的方式來(lái)表示從源頂點(diǎn)到各個(gè)頂點(diǎn)的最短路徑。
- Dijkstra算法每次需要選出一個(gè)頂點(diǎn)，并對(duì)其連接出去的頂點(diǎn)進(jìn)行松弛更新，因此其時(shí)間復(fù)雜度是 O (N2) 空間復(fù)雜度是O(N) 。
Dijkstra算法的原理
- Dijkstra算法每次從集合 Q 中選出一個(gè)估計(jì)值最小的頂點(diǎn) u ，將該頂點(diǎn)加入到集合 S 中，表示確定了從源頂點(diǎn)到頂點(diǎn) u 的最短路徑。
- 因?yàn)閳D中所有邊的權(quán)值非負(fù)（使用Dijkstra算法的前提），所以對(duì)于估計(jì)值最小的頂點(diǎn) u 來(lái)說(shuō)，其估計(jì)值不可能再被其他比它估計(jì)值更大的頂點(diǎn)松弛更新得更小，因此頂點(diǎn) u 的最短路徑就是當(dāng)前的估計(jì)值。
- 而對(duì)于集合 Q 中的其他頂點(diǎn)來(lái)說(shuō)，這些頂點(diǎn)的估計(jì)值比頂點(diǎn) u 的估計(jì)值大，因此頂點(diǎn) u 可能將它們的估計(jì)值松弛更新得更小，所以頂點(diǎn) u 在加入集合 S 后還需要嘗試對(duì)其連接出去的頂點(diǎn)進(jìn)行松弛更新。
單源最短路徑-Bellman-Ford算法
Bellman-Ford算法（貝爾曼福特算法）
Bellman-Ford算法的基本思想如下：
- Bellman-Ford算法本質(zhì)是暴力求解，對(duì)于從源頂點(diǎn) s 到目標(biāo)頂點(diǎn) j 的路徑來(lái)說(shuō)，如果存在從源頂點(diǎn)s 到頂點(diǎn) i 的路徑，還存在一條從頂點(diǎn) i 到頂點(diǎn) j 的邊，并且其權(quán)值之和小于當(dāng)前從源頂點(diǎn) s 到目標(biāo)頂點(diǎn) j 的路徑長(zhǎng)度，則可以對(duì)頂點(diǎn) j 的估計(jì)值和前驅(qū)頂點(diǎn)進(jìn)行松弛更新。
- Bellman-Ford算法根據(jù)路徑的終邊來(lái)進(jìn)行松弛更新，但是僅對(duì)圖中的邊進(jìn)行一次遍歷可能并不能正確更新出最短路徑，最壞的情況下需要對(duì)圖中的邊進(jìn)行 n?1 輪遍歷（n 表示圖中的頂點(diǎn)個(gè)數(shù)）。
Bellman-Ford算法的實(shí)現(xiàn)：
- 使用一個(gè)dist 數(shù)組來(lái)記錄從源頂點(diǎn)到各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度估計(jì)值，初始時(shí)將源頂點(diǎn)的估計(jì)值設(shè)置為權(quán)值的缺省值（比如int就是0），表示從源頂點(diǎn)到源頂點(diǎn)的路徑長(zhǎng)度為0，將其余頂點(diǎn)的估計(jì)值設(shè)置為MAX_W，表示從源頂點(diǎn)暫時(shí)無(wú)法到達(dá)其他頂點(diǎn)。
- 使用一個(gè) parentPath 數(shù)組來(lái)記錄到達(dá)各個(gè)頂點(diǎn)路徑的前驅(qū)頂點(diǎn)，初始時(shí)將各個(gè)頂點(diǎn)的前驅(qū)頂點(diǎn)初始化為-1，表示各個(gè)頂點(diǎn)暫時(shí)只能自己到達(dá)自己，沒(méi)有前驅(qū)頂點(diǎn)。
- 對(duì)圖中的邊進(jìn)行 n?1 輪遍歷，對(duì)于i?>j 的邊來(lái)說(shuō)，如果存在s?>i 的路徑，并且s?>i 的路徑權(quán)值與邊 i?>j 的權(quán)值之和小于當(dāng)前 s?>j 的路徑長(zhǎng)度，則將頂點(diǎn) j 的估計(jì)值進(jìn)行更新，并將頂點(diǎn)j 的前驅(qū)頂點(diǎn)改為頂點(diǎn) i ，因?yàn)?i?>j 是圖中的一條直接相連的邊，在這條路徑中頂點(diǎn) j 的上一個(gè)頂點(diǎn)就是頂點(diǎn) i 。
- 再對(duì)圖中的邊進(jìn)行一次遍歷，嘗試進(jìn)行松弛更新，如果還能更新則說(shuō)明圖中帶有負(fù)權(quán)回路，無(wú)法找到最短路徑
//鄰接矩陣
namespace Matrix {
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph {
public:
//獲取單源最短路徑（BellmanFord算法）
bool BellmanFord(const V& src, vector<W>& dist, vector<int>& parentPath) {
int n = _vertexs.size();
int srci = getVertexIndex(src); //獲取源頂點(diǎn)的下標(biāo)
dist.resize(n, MAX_W); //各個(gè)頂點(diǎn)的估計(jì)值初始化為MAX_W
parentPath.resize(n, -1); //各個(gè)頂點(diǎn)的前驅(qū)頂點(diǎn)初始化為-1
dist[srci] = W(); //源頂點(diǎn)的估計(jì)值設(shè)置為權(quán)值的缺省值
for (int k = 0; k < n - 1; k++) { //最多更新n-1輪
bool update = false; //記錄本輪是否更新過(guò)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (_matrix[i][j] != MAX_W && dist[i] != MAX_W && dist[i] + _matrix[i][j] < dist[j]) {
dist[j] = dist[i] + _matrix[i][j]; //松弛更新出更小的路徑權(quán)值
parentPath[j] = i; //更新路徑的前驅(qū)頂點(diǎn)
update = true;
}
}
}
if (update == false) { //本輪沒(méi)有更新過(guò)，不必進(jìn)行后續(xù)輪次的更新
break;
}
}
//更新n-1輪后如果還能更新，則說(shuō)明帶有負(fù)權(quán)回路
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]) {
return false; //帶有負(fù)權(quán)回路的圖無(wú)法求出最短路徑
}
}
}
return true;
}
private:
vector<V> _vertexs; //頂點(diǎn)集合
unordered_map<V, int> _vIndexMap; //頂點(diǎn)映射下標(biāo)
vector<vector<W>> _matrix; //鄰接矩陣
};
}
說(shuō)明一下：
- Bellman-Ford算法是暴力求解，可以解決帶有負(fù)權(quán)邊的單源最短路徑問(wèn)題。
- 負(fù)權(quán)回路指的是在圖中形成回路的各個(gè)邊的權(quán)值之和為負(fù)數(shù)，路徑每繞一圈回路其權(quán)值都會(huì)減少，導(dǎo)致無(wú)法找到最短路徑，由于最多需要進(jìn)行n?1 輪松弛更新，因此可以在 n?1 輪松弛更新后再進(jìn)行一輪松弛更新，如果還能進(jìn)行更新則說(shuō)明帶有負(fù)權(quán)回路。
- Bellman-Ford算法需要對(duì)圖中的邊進(jìn)行 n 輪遍歷，因此其時(shí)間復(fù)雜度是 O(N×E)，由于這里是用鄰接矩陣實(shí)現(xiàn)的，遍歷圖中的所有邊的時(shí)間復(fù)雜度是O(N2)所以上述代碼的時(shí)間復(fù)雜度是O(N3)空間復(fù)雜度是O(N)。
為什么最多進(jìn)行n?1 輪松弛更新？
從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的最短路徑中不能包含回路：
- 如果形成回路的各個(gè)邊的權(quán)值之和為負(fù)數(shù)，則該回路為負(fù)權(quán)回路，找不到最短路徑。
- 如果形成回路的各個(gè)邊的權(quán)值之和為非負(fù)數(shù)，則多走這個(gè)回路是“徒勞”的，可能會(huì)使得路徑長(zhǎng)度變長(zhǎng)。
在每一輪松弛過(guò)程中，后面路徑的更新可能會(huì)影響到前面已經(jīng)更新過(guò)的路徑，比如使得前面已經(jīng)更新過(guò)的路徑的長(zhǎng)度可以變得更短，或者使得某些源頂點(diǎn)之前不可達(dá)的頂點(diǎn)變得可達(dá)，但每一輪松弛至少能確定最短路徑中的一條邊，如果圖中有n 個(gè)頂點(diǎn)，那么兩個(gè)頂點(diǎn)之間的最短路徑最多有n?1 條邊，因此最多需要進(jìn)行n?1 次松弛更新。
例如下圖中，頂點(diǎn)A、B、C、D、E 的下標(biāo)分別是0、1、2、3、4，現(xiàn)在要計(jì)算以頂點(diǎn) E 為源頂點(diǎn)的單源最短路徑。
對(duì)于上述圖來(lái)說(shuō)，Bellman-Ford算法在第一輪松弛的時(shí)候只能更新出E?>D 這條邊，在第二輪的時(shí)候只能更新出 D?>C ，以此類(lèi)推，最終就會(huì)進(jìn)行4輪松弛更新（建議通過(guò)代碼調(diào)試觀察）。
說(shuō)明一下：
- 由于只有當(dāng)前輪次進(jìn)行過(guò)更新，才有可能會(huì)影響其他路徑，因此在代碼中使用update 標(biāo)記每輪松弛算法是否進(jìn)行過(guò)更新，如果沒(méi)有進(jìn)行過(guò)更新，則無(wú)需進(jìn)行后面輪次的更新。
- Bellman-Ford算法還有一個(gè)優(yōu)化方案叫做SPFA（Shortest Path Faster Algorithm），其用一個(gè)隊(duì)列來(lái)維護(hù)可能需要松弛更新的頂點(diǎn)，避免了不必要的冗余計(jì)算，大家可以自行了解。
多源最短路徑-Floyd-Warshall算法
Floyd-Warshall算法（弗洛伊德算法）
Floyd-Warshall算法的基本思想如下：
- Floyd-Warshall算法解決的是任意兩點(diǎn)間的最短路徑的算法，其考慮的是路徑的中間頂點(diǎn)，對(duì)于從頂點(diǎn) i ii 到頂點(diǎn) j jj 的路徑來(lái)說(shuō)，如果存在從頂點(diǎn) i 到頂點(diǎn) k 的路徑，還存在從頂點(diǎn) k 到頂點(diǎn) j 的路徑，并且這兩條路徑的權(quán)值之和小于當(dāng)前從頂點(diǎn) i 到頂點(diǎn) j 的路徑長(zhǎng)度，則可以對(duì)頂點(diǎn) j 的估計(jì)值和前驅(qū)頂點(diǎn)進(jìn)行松弛更新。
- Floyd-Warshall算法本質(zhì)是一個(gè)簡(jiǎn)單的動(dòng)態(tài)規(guī)劃，就是判斷從頂點(diǎn) i 到頂點(diǎn) j 的這條路徑是否經(jīng)過(guò)頂點(diǎn) k ，如果經(jīng)過(guò)頂點(diǎn) k 可以讓這條路徑的權(quán)值變得更小，則經(jīng)過(guò)，否則則不經(jīng)過(guò)。
Floyd-Warshall算法的實(shí)現(xiàn)：
- 使用一個(gè) vvDist 二維數(shù)組來(lái)記錄從各個(gè)源頂點(diǎn)到各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度的估計(jì)值，vvDist[i][j] 表示從頂點(diǎn) i ii 到頂點(diǎn) j 的最短路徑長(zhǎng)度的估計(jì)值，初始時(shí)將二維數(shù)組中的值全部初始化為MAX_W，表示各個(gè)頂點(diǎn)之間暫時(shí)無(wú)法互通。
- 使用一個(gè)vvParentPath 二維數(shù)組來(lái)記錄從各個(gè)源頂點(diǎn)到達(dá)各個(gè)頂點(diǎn)路徑的前驅(qū)頂點(diǎn)，初始時(shí)將二維數(shù)組中的值全部初始化為-1，表示各個(gè)頂點(diǎn)暫時(shí)只能自己到自己，沒(méi)有前驅(qū)頂點(diǎn)。
- 根據(jù)鄰接矩陣對(duì)vvDist 和vvParentPath 進(jìn)行初始化，如果從頂點(diǎn) i 到頂點(diǎn) j 有直接相連的邊，則將 vvDist[i][j] 初始化為這條邊的權(quán)值，并將 vvParentPath[i][j] 初始化為 i ，表示在i?>j 這條路徑中頂點(diǎn) j 前驅(qū)頂點(diǎn)是 i ，將 vvDist[i][i] 的值設(shè)置為權(quán)值的缺省值（比如int就是0），表示自己到自己的路徑長(zhǎng)度為0。
- 依次取各個(gè)頂點(diǎn) k 作為 i?>j 路徑的中間頂點(diǎn)，如果同時(shí)存在i?>k 的路徑和k?>j 的路徑，并且這兩條路徑的權(quán)值之和小于當(dāng)前i?>j 路徑的權(quán)值，則更新vvDist[i][j] 的值，并將vvParentPath[i][j] 的值更新為vvParentPath[k][j] 的值。
代碼如下：
//鄰接矩陣
namespace Matrix {
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph {
public:
//獲取多源最短路徑（FloydWarshall算法）
void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvParentPath) {
int n = _vertexs.size();
vvDist.resize(n, vector<W>(n, MAX_W)); //任意兩個(gè)頂點(diǎn)直接的路徑權(quán)值初始化為MAX_W
vvParentPath.resize(n, vector<int>(n, -1)); //各個(gè)頂點(diǎn)的前驅(qū)頂點(diǎn)初始化為-1
//根據(jù)鄰接矩陣初始化直接相連的頂點(diǎn)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (_matrix[i][j] != MAX_W) { //i->j有邊
vvDist[i][j] = _matrix[i][j]; //i->j的路徑權(quán)值
vvParentPath[i][j] = i; //i->j路徑的前驅(qū)頂點(diǎn)為i
}
if (i == j) { //i->i
vvDist[i][j] = W(); //i->i的路徑權(quán)值設(shè)置為權(quán)值的缺省值
}
}
}
for (int k = 0; k < n; k++) { //依次取各個(gè)頂點(diǎn)作為i->j路徑的中間頂點(diǎn)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W &&
vvDist[i][k] + vvDist[k][j] < vvDist[i][j]) { //存在i->k和k->j的路徑，并且這兩條路徑的權(quán)值之和小于當(dāng)前i->j路徑的權(quán)值
vvDist[i][j] = vvDist[i][k] + vvDist[k][j]; //松弛更新出更小的路徑權(quán)值
vvParentPath[i][j] = vvParentPath[k][j]; //更小路徑的前驅(qū)頂點(diǎn)
}
}
}
}
}
private:
vector<V> _vertexs; //頂點(diǎn)集合
unordered_map<V, int> _vIndexMap; //頂點(diǎn)映射下標(biāo)
vector<vector<W>> _matrix; //鄰接矩陣
};
}
說(shuō)明一下：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-731303.html
- Bellman-Ford算法是根據(jù)路徑的終邊來(lái)進(jìn)行松弛更新的，而Floyd-Warshall算法是根據(jù)路徑經(jīng)過(guò)的中間頂點(diǎn)來(lái)進(jìn)行松弛更新的，因?yàn)楦鶕?jù)Bellman-Ford算法中的dist 只能得知從指定源頂點(diǎn)到某一頂點(diǎn)的路徑權(quán)值，而根據(jù)Floyd-Warshall算法中的vvDist 可以得知任意兩個(gè)頂點(diǎn)之間的路徑權(quán)值。
- Floyd-Warshall算法的時(shí)間復(fù)雜度是O(N3)空間復(fù)雜度是O(N2)雖然求解多源最短路徑也可以以圖中不同的頂點(diǎn)作為源頂點(diǎn)，去調(diào)用Dijkstra算法或Bellman-Ford算法，但Dijkstra算法不能解決帶負(fù)權(quán)的圖，Bellman-Ford算法調(diào)用 N 次的時(shí)間復(fù)雜度又太高。
到了這里，關(guān)于高階數(shù)據(jù)結(jié)構(gòu)——圖的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
