1.圖的基本概念
概念多，但是不難理解，難的算法部分基本都是圖解。
圖是由頂點(diǎn)集合及頂點(diǎn)間的關(guān)系組成的一種數(shù)據(jù)結(jié)構(gòu)：G = (V， E)，其中V為頂點(diǎn)集合，E為邊集合。
頂點(diǎn)和邊：圖中結(jié)點(diǎn)稱為頂點(diǎn)，第i個(gè)頂點(diǎn)記作vi。兩個(gè)頂點(diǎn)vi和vj相關(guān)聯(lián)稱作頂點(diǎn)vi和頂點(diǎn)vj之間有一條邊，圖中的第k條邊記作ek，ek = (vi，vj)或<vi，vj>
有向圖：在有向圖中，頂點(diǎn)對<x, y>是有序的，頂點(diǎn)對<x，y>稱為頂點(diǎn)x到頂點(diǎn)y的一條邊(弧)，<x, y>和<y, x>是兩條不同的邊，比如下圖G3和G4為有向圖。
無向圖：頂點(diǎn)對(x, y)是無序的，頂點(diǎn)對(x,y)稱為頂點(diǎn)x和頂點(diǎn)y相關(guān)聯(lián)的一條邊，這條邊沒有特定方向，(x, y)和(y，x)是同一條邊，比如下圖G1和G2為無向圖。
無向完全圖：在有n個(gè)頂點(diǎn)的無向圖中，若有n * (n-1)/2條邊，即任意兩個(gè)頂點(diǎn)之間有且僅有一條邊，則稱此圖為無向完全圖，比如上圖G1；
有向完全圖：在n個(gè)頂點(diǎn)的有向圖中，若有n * (n-1)條邊，即任意兩個(gè)頂點(diǎn)之間有且僅有方向相反的邊，則稱此圖為有向完全圖，比如上圖G4。
鄰接頂點(diǎn)：在無向圖G中，若 (u, v)是E(G)中的一條邊，則稱u和v互為鄰接頂點(diǎn)，并稱邊(u,v)依附于頂點(diǎn)u和v；在有向圖G中，若 <u, v>是E(G)中的一條邊，則稱頂點(diǎn)u鄰接到v，頂點(diǎn)v鄰接自頂點(diǎn)u，并稱邊<u, v>與頂點(diǎn)u和頂點(diǎn)v相關(guān)聯(lián)。
頂點(diǎn)的度：頂點(diǎn)v的度是指與它相關(guān)聯(lián)的邊的條數(shù)，記作deg(v)。在有向圖中，頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和，其中頂點(diǎn)v的入度是以v為終點(diǎn)的有向邊的條數(shù)，記作indev(v);頂點(diǎn)v的出度是以v為起始點(diǎn)的有向邊的條數(shù)，記作outdev(v)。因此：dev(v) = indev(v) + outdev(v)。注意：對于無向圖，頂點(diǎn)的度等于該頂點(diǎn)的入度和出度，即dev(v) = indev(v) = outdev(v)。
權(quán)值：邊附帶的數(shù)據(jù)信息。
路徑：在圖G = (V， E)中，若從頂點(diǎn)vi出發(fā)有一組邊使其可到達(dá)頂點(diǎn)vj，則稱頂點(diǎn)vi到頂點(diǎn)vj的頂點(diǎn)序列為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。
路徑長度：對于不帶權(quán)的圖，一條路徑的路徑長度是指該路徑上的邊的條數(shù)；
對于帶權(quán)的圖，一條路徑的路徑長度是指該路徑上各個(gè)邊權(quán)值的總和。
簡單路徑與回路：若路徑上各頂點(diǎn)v1，v2，v3，…，vm均不重復(fù)，則稱這樣的路徑為簡單路徑。若路徑上第一個(gè)頂點(diǎn)v1和最后一個(gè)頂點(diǎn)vm重合，則稱這樣的路徑為回路或環(huán)。
子圖：設(shè)圖G = {V, E}和圖G1 = {V1，E1}，若V1屬于V且E1屬于E，則稱G1是G的子圖。
連通圖：在無向圖中，若從頂點(diǎn)v1到頂點(diǎn)v2有路徑，則稱頂點(diǎn)v1與頂點(diǎn)v2是連通的。如果圖中任意一對頂點(diǎn)都是連通的，則稱此圖為連通圖
強(qiáng)連通圖：在有向圖中，若在每一對頂點(diǎn)vi和vj之間都存在一條從vi到vj的路徑，也存在一條從vj到vi的路徑，則稱此圖是強(qiáng)連通圖。
生成樹：一個(gè)連通圖的最小連通子圖稱作該圖的生成樹（形成連通圖并且使用的邊數(shù)量少）。有n個(gè)頂點(diǎn)的連通圖的生成樹有n個(gè)頂點(diǎn)和n-1條邊。
圖與樹的關(guān)系：
- 樹是一種特殊的無環(huán)連通圖。
- 樹關(guān)注的節(jié)點(diǎn)（頂點(diǎn)）存儲(chǔ)的值。
- 圖關(guān)注的是頂點(diǎn)關(guān)系以及邊的權(quán)值。
2. 圖的存儲(chǔ)結(jié)構(gòu)
因?yàn)閳D中既有節(jié)點(diǎn)，又有邊(節(jié)點(diǎn)與節(jié)點(diǎn)之間的關(guān)系)，因此，在圖的存儲(chǔ)中，只需要保存：節(jié)點(diǎn)和邊關(guān)系即可。節(jié)點(diǎn)保存比較簡單，只需要一段連續(xù)空間即可，那邊關(guān)系該怎么保存呢？
2.1鄰接矩陣
因?yàn)楣?jié)點(diǎn)與節(jié)點(diǎn)之間的關(guān)系就是連通與否，即為0或者1，因此鄰接矩陣(二維數(shù)組)即是：先用一個(gè)數(shù)組將定點(diǎn)保存，然后采用矩陣來表示節(jié)點(diǎn)與節(jié)點(diǎn)之間的關(guān)系。
注意：
- 無向圖的鄰接矩陣是對稱的，第i行(列)元素之和，就是頂點(diǎn)i的度。有向圖的鄰接矩陣則不一定是對稱的，第i行(列)元素之后就是頂點(diǎn)i 的出(入)度。
- 如果邊帶有權(quán)值，并且兩個(gè)節(jié)點(diǎn)之間是連通的，上圖中的邊的關(guān)系就用權(quán)值代替，如果兩個(gè)頂點(diǎn)不通，則使用無窮大（自己設(shè)定值表示無窮）代替。
代碼實(shí)現(xiàn)：
namespace maritx
{
//V為頂點(diǎn)類型，無論什么類型都可以轉(zhuǎn)換位對于的下標(biāo)，訪問時(shí)使用哈希表轉(zhuǎn)換出下標(biāo)
//W為邊類型，一般為數(shù)值類型，MAX_W代表邊不存在
//Direction表示方向，默認(rèn)無向
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false> //默認(rèn)無向
class Graph
{
private:
vector<V> _vertexs; //頂點(diǎn)
map<V, size_t> _VIndexMap; //頂點(diǎn) ：下標(biāo)
vector<vector<W>> _matrix; //鄰接矩陣
public:
typedef Graph<V, W, MAX_W, Direction> self;
Graph() = default;
Graph(const V* vertexs, size_t n)
{
_vertexs.resize(n);
for (size_t i = 0; i < n; i++)
{
_vertexs[i] = vertexs[i];
_VIndexMap[vertexs[i]] = i;
}
//初始化鄰接矩陣
_matrix.resize(n);
for (int i = 0; i < n; i++)
{
_matrix[i].resize(n, MAX_W);
}
}
size_t GetVIndex(const V& v)
{
if (_VIndexMap.count(v))
{
return _VIndexMap[v];
}
else //如果沒有這個(gè)頂點(diǎn)
{
throw invalid_argument("不存在的頂點(diǎn)");
//assert(false);
return -1;
}
}
void AddEdge(const V& src, const V& dst, const W& w)
{
size_t srci = GetVIndex(src);
size_t dsti = GetVIndex(dst);
_AddEdge(srci, dsti, w);
}
void _AddEdge(int srci, int dsti, const W& w)
{
_matrix[srci][dsti] = w; //有向圖只需添加一邊
if (Direction == false)
{
_matrix[dsti][srci] = w;
}
}
};
}
2.2鄰接表
鄰接表：使用數(shù)組表示頂點(diǎn)的集合，使用鏈表表示邊的關(guān)系。
-
無向圖鄰接表存儲(chǔ)
-
有向圖鄰接表存儲(chǔ)
代碼實(shí)現(xiàn)：
namespace link_table
{
template<class W>
struct Edge
{
W _w; //權(quán)值
int _dsti;
Edge<W>* _next;
Edge(int dsti,const W& w)
:_dsti(dsti)
,_w(w)
,_next(nullptr)
{}
};
template<class V, class W, bool Direction = false> //默認(rèn)無向
class Graph
{
public:
typedef Edge<W> Edge;
Graph(const V* vertexs, size_t n)
{
_vertexs.resize(n);
for (size_t i = 0; i < n; i++)
{
_vertexs[i] = vertexs[i];
_VIndexMap[vertexs[i]] = i;
}
//初始化鄰接矩陣
_tables.resize(n, nullptr);
}
size_t GetVIndex(const V& v)
{
if (_VIndexMap.count(v))
{
return _VIndexMap[v];
}
else //如果沒有這個(gè)頂點(diǎn)
{
throw invalid_argument("不存在的頂點(diǎn)");
//assert(false);
return -1;
}
}
void AddEdge(const V& src, const V& dst, const W& w)
{
size_t srci = GetVIndex(src);
size_t dsti = GetVIndex(dst);
Edge* newnode = new Edge(dsti, w);
newnode->_next = _tables[srci];
_tables[srci] = newnode; //有向圖只需添加一邊
if (Direction == false)
{
Edge* newnode = new Edge(srci, w);
newnode->_next = _tables[dsti];
_tables[dsti] = newnode;
}
}
void Print()
{
// 打印頂點(diǎn)和下標(biāo)映射關(guān)系
for (size_t i = 0; i < _vertexs.size(); ++i)
{
cout << _vertexs[i] << "-" << i << " ";
}
cout << endl << endl;
for (int i = 0; i < _tables.size(); i++)
{
Edge* cur = _tables[i];
if(cur) cout << i;
while (cur)
{
cout << "->" << cur->_dsti ;
cur = cur->_next;
}
cout << endl;
}
}
private:
vector<V> _vertexs; //頂點(diǎn)
map<V, int> _VIndexMap; //頂點(diǎn)：下標(biāo)
vector<Edge*> _tables; //鄰接表
};
}
2.3兩種實(shí)現(xiàn)的比較
- 對于鄰接矩陣，優(yōu)點(diǎn)是確定AB兩點(diǎn)間關(guān)系時(shí)方便。缺點(diǎn)是對于邊數(shù)量少的情況，想遍歷與某點(diǎn)的出(入)邊，需要遍歷矩陣的一行（N），空間也會(huì)很浪費(fèi)。
- 對于鄰接表，優(yōu)點(diǎn)是邊少時(shí)遍歷點(diǎn)的出(入)邊，有幾條邊就走幾次。缺點(diǎn)是想確定AB兩點(diǎn)間關(guān)系時(shí)需要遍歷一次鄰接表。
- 推薦關(guān)系復(fù)雜，邊多時(shí)使用鄰接矩陣。 關(guān)系簡單，邊少時(shí)使用鄰接表。
- 兩種存儲(chǔ)實(shí)現(xiàn)圖相關(guān)算法差別不大，后面的算法都是基于鄰接矩陣的。
3.圖的遍歷
給定一個(gè)圖G和其中任意一個(gè)頂點(diǎn)v0，從v0出發(fā)，沿著圖中各邊訪問圖中的所有頂點(diǎn)，且每個(gè)頂點(diǎn)僅被遍歷一次。"遍歷"即對結(jié)點(diǎn)進(jìn)行某種操作的意思。
樹的遍歷是自頂點(diǎn)向下，圖的遍歷是選定一個(gè)頂點(diǎn)作為起點(diǎn)。
3.1 圖的廣度優(yōu)先遍歷
//遍歷
void BFS(const V& v)
{
size_t n = _vertexs.size();
size_t srci = GetVIndex(v);
vector<bool> visited(n);
queue<size_t> q;
q.push(srci);
visited[srci] = true;
while (!q.empty())
{
size_t sz = q.size();
for (size_t i = 0; i < sz; i++)
{
size_t top = q.front(); q.pop();
cout << _vertexs[top] << " ";
for (size_t j = 0; j < n; j++)
{
if (_matrix[top][j] != MAX_W && visited[j] != true) //存在并且沒有訪問過
{
q.push(j);
visited[j] = true;
}
}
}
}
//有可能存在從v點(diǎn)出發(fā)到不了某些點(diǎn)的情況，這時(shí)可遍歷vis數(shù)組
for (int i = 0; i < n; i++)
{
if (visited[i] == false)
{
cout << _vertexs[i] << " ";
}
}
cout << endl;
}
3.2 圖的深度優(yōu)先遍歷
void DFS(const V& v)
{
size_t srci = GetVIndex(v);
vector<bool> visited(_vertexs.size());
dfs(srci, visited);
//有可能存在從v點(diǎn)出發(fā)到不了某些點(diǎn)的情況，這時(shí)可遍歷vis數(shù)組
for (int i = 0; i < n; i++)
{
if (visited[i] == false)
{
cout << _vertexs[i] << " ";
}
}
}
void dfs(size_t srci, vector<bool>& visited)
{
cout << _vertexs[srci] << " ";
visited[srci] = true;
for (int i = 0; i < _vertexs.size(); i++)
{
if (_matrix[srci][i] != MAX_W && visited[i] != true)
{
dfs(i, visited);
}
}
}
4.最小生成樹
連通圖中的每一棵生成樹，都是原圖的一個(gè)極大無環(huán)子圖，即：從其中刪去任何一條邊，生成樹就不在連通；反之，在其中引入任何一條新邊，都會(huì)形成一條回路。
若連通圖由n個(gè)頂點(diǎn)組成，則其生成樹必含n個(gè)頂點(diǎn)和n-1條邊。因此構(gòu)造最小生成樹的準(zhǔn)則有三條：
- 只能使用圖中的邊來構(gòu)造最小生成樹
- 只能使用恰好n-1條邊來連接圖中的n個(gè)頂點(diǎn)
- 選用的n-1條邊不能構(gòu)成回路
構(gòu)造最小生成樹的方法：Kruskal算法和Prim算法。這兩個(gè)算法都采用了逐步求解的貪心策略。
貪心算法：是指在問題求解時(shí)，總是做出當(dāng)前看起來最好的選擇。也就是說貪心算法做出的不是整體最優(yōu)的的選擇，而是某種意義上的局部最優(yōu)解。貪心算法不是對所有的問題都能得到整體最優(yōu)解，Kruskal算法和Prim算法都可保證最優(yōu)，兩種策略相當(dāng)容易記憶，證明難度較大，本文不做證明。
4.1 Kruskal算法
- 每次都選用圖中權(quán)值最小的邊來構(gòu)造，可以使用堆實(shí)現(xiàn)。
- 只能選n - 1條邊。
-
選用的邊不可構(gòu)成回路，可以使用并查集來判斷環(huán)是否存在。
不了解并查集的可以看這篇文章（很簡單的）：并查集
不了解堆的可以看這篇文章：堆
struct Edge //存儲(chǔ)邊信息
{
int _srci;
int _dsti;
W _w;
Edge(int srci, int dsti, W w)
:_srci(srci)
,_dsti(dsti)
,_w(w)
{}
bool operator>(const Edge& edge) const
{
return _w > edge._w;
}
};
//Kruskal(克魯斯卡爾),生成的了返回權(quán)值，生成不了返回W默認(rèn)值
W Kruskal(self& minTree)
{
//初始化一下最小生成樹
size_t n = _vertexs.size();
minTree._vertexs = _vertexs;
minTree._VIndexMap = _VIndexMap;
minTree._matrix.resize(n);
for (auto& e : minTree._matrix)
{
e.resize(_vertexs.size(), MAX_W);
}
UnionFindSet ufs(n); //并查集
priority_queue<Edge, vector<Edge>, greater<Edge>> pq; //堆
//入邊
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++) //無向圖只需要一半即可
{
if(_matrix[i][j] != MAX_W)
pq.push(Edge(i, j, _matrix[i][j]));
}
}
//依次選最小邊，選n - 1
size_t esum = 0;
W ret = 0;
//不斷選最小邊即可
while (!pq.empty())
{
Edge e = pq.top(); pq.pop();
if (!ufs.InSet(e._srci, e._dsti)) //不在一個(gè)集合(不構(gòu)成回路)，當(dāng)前邊可選
{
minTree.AddEdge(e._srci, e._dsti, e._w);
esum++;
ret += e._w;
ufs.Union(e._srci, e._dsti);
}
}
//判斷可否形成最小生成樹
if (esum == n - 1)
{
return ret;
}
else
{
return W();
}
}
4.2 Prim算法
- Kruskal算法側(cè)重邊，Prim算法側(cè)重點(diǎn)。
- 設(shè)有X，Y兩個(gè)點(diǎn)集合，X表示已在最小生成樹中的點(diǎn)，Y表示還未在最小生成樹中的點(diǎn)。故選邊時(shí)選的是X->Y所有邊中的最小權(quán)值。
- 只能選n - 1條邊。
-
選用的邊不可構(gòu)成回路，只需選的邊起點(diǎn)在X，終點(diǎn)在Y即可。
//prim(普利姆算法)
W Prim(self& minTree, const V& src)
{
//初始化一下最小生成樹
size_t n = _vertexs.size();
minTree._vertexs = _vertexs;
minTree._VIndexMap = _VIndexMap;
minTree._matrix.resize(n);
for (auto& e : minTree._matrix)
{
e.resize(_vertexs.size(), MAX_W);
}
size_t srci = GetVIndex(src); //起點(diǎn)
//存儲(chǔ)邊的堆
priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
//X和Y集合（不在X就在Y）
vector<bool> X(n, false);
X[srci] = true;
//把X初始點(diǎn)的邊入進(jìn)去
for (size_t i = 0; i < n; i++)
{
if (_matrix[srci][i] != MAX_W)
{
pq.push(Edge(srci, i, _matrix[srci][i]));
}
}
//選出邊的條數(shù)
size_t esum = 0;
W ret = 0;
while (!pq.empty())
{
Edge e = pq.top(); pq.pop();
if (X[e._dsti] != true) //終點(diǎn)在Y，選了不成環(huán)
{
minTree.AddEdge(e._srci, e._dsti, e._w);
esum++;
ret += e._w;
X[e._dsti] = true;
for (int i = 0; i < n; i++)
{
//入邊為X-Y，X-X的邊沒必要入
if (_matrix[e._dsti][i] != MAX_W && X[i] != true)
{
pq.push(Edge(e._dsti, i, _matrix[e._dsti][i]));
}
}
}
}
//判斷可否形成最小生成樹
if (esum == n - 1)
{
return ret;
}
else
{
return W();
}
}
4.3 兩個(gè)算法比較
- Kruskal算法適用于稀疏圖，即邊少的圖，因?yàn)樵撍惴ㄐ枰?strong>堆維護(hù)所有的邊。
- Prim算法適用于稠密圖，即邊多的圖，因?yàn)樵撍惴ǖ囊c(diǎn)在點(diǎn)，并不需要維護(hù)所有的邊(X-X的邊無需維護(hù))。
5.最短路徑
5.1兩個(gè)抽象存儲(chǔ)
基于這兩個(gè)抽象數(shù)據(jù)結(jié)構(gòu)還原最短路徑：
//打印最短路徑的算法
void PrinrtShotPath(const V& src, const vector<W>& dist, const vector<int>& pPath)
{
size_t n = _vertexs.size();
size_t srci = GetVIndex(src);
for (size_t i = 0; i < n; i++)
{
if (i != srci) //源到源不打印
{
size_t par = i;
vector<size_t> path; //先從結(jié)尾開始添加
while (par != srci)
{
path.push_back(par);
par = pPath[par];
}
path.push_back(srci);
reverse(path.begin(), path.end()); //翻轉(zhuǎn)過來
for (auto pos : path)
{
cout << _vertexs[pos] << "->";
}
cout << dist[i] << endl; //打印長度
}
}
}
5.2單源最短路徑–Dijkstra算法
- 貪心，分為兩個(gè)集合Q和S，其中Q表示已經(jīng)確定最短路徑的頂點(diǎn)集合，S表示未確定最短路徑的頂點(diǎn)集合。
- 在已有最短路徑的基礎(chǔ)上更新到其他頂點(diǎn)的路徑，如果更短就更新，這個(gè)操作稱為松弛頂點(diǎn)。（建議配合圖解看）
- Dijkstra算法不適用于帶負(fù)權(quán)的最短路徑問題（后面解釋）。
圖解：
正確性證明：
- 圖邊權(quán)沒有負(fù)數(shù)
（1）如果現(xiàn)在遍歷 起點(diǎn)->S(未確定最短路徑點(diǎn)集合)的邊，找到一條s->x(記和為len)的最短，那就可以確定這條是s->x的最短。
（2）因?yàn)槿绻嬖趕->……(和一定小于len)->x的一條更短路徑，那遍歷時(shí)就會(huì)先選中s->……中的頂點(diǎn)進(jìn)行松弛，而不是選中x進(jìn)行松弛。 - 圖邊權(quán)有負(fù)數(shù)
（1）遍歷 起點(diǎn)->S(未確定最短路徑點(diǎn)集合)的邊，找到一條s->x(記和為len)的最短，不能確定這條是s->x的最短。
（2）因?yàn)榭赡艽嬖趕->……（大于len）->負(fù)權(quán)->x(小于len)，這時(shí)候就會(huì)更新不到這條真正的最短
//單源最短路徑：dijkstra算法（不帶負(fù)權(quán)）
//每次都可以確定一個(gè)點(diǎn)的最短路徑，然后圍繞這個(gè)點(diǎn)松弛
//準(zhǔn)確性：如果當(dāng)前選的不是最短，那就不會(huì)選中當(dāng)前，而是其他的點(diǎn)，在松弛操作中更新出最短
//兩個(gè)輸出型參數(shù),dist為路徑長，pPath記錄路徑
void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
{
size_t n = _vertexs.size();
size_t srci = GetVIndex(src);
//初始化
dist.resize(n, MAX_W);
pPath.resize(n, -1);
dist[srci] = W();
//Q中為true，說明已經(jīng)確認(rèn)最短路徑
vector<bool> Q(n, false);
//要確定N個(gè)頂點(diǎn)的最短，循環(huán)N次（其實(shí)只要N-1次即可，但為了邏輯就多循環(huán)一次）
for (size_t i = 0; i < n; i++)
{
size_t u = srci;
W min = MAX_W;
//找到最短的路徑，該路徑已經(jīng)可確認(rèn)為最短
for (size_t j = 0; j < n; j++)
{
if (Q[j] == false && dist[j] < min)
{
u = j;
min = dist[j];
}
}
Q[u] = true;
//松弛頂點(diǎn) srci-u u-v -> srci-v
for (size_t v = 0; v < n; v++)
{
if (_matrix[u][v] != MAX_W && dist[u] + _matrix[u][v] < dist[v])
{
dist[v] = dist[u] + _matrix[u][v];
pPath[v] = u;
}
}
}
}
5.3單源最短路徑–Bellman-Ford算法
- Bellman-Ford算法本質(zhì)是暴力算法。
- Bellman-Ford算法可以解決帶負(fù)權(quán)的問題。
- Bellman-Ford算法的核心在于松弛頂點(diǎn)。
圖解：
負(fù)權(quán)回路：
//單源最短路徑：BellmanFord算法（帶負(fù)權(quán)，注意負(fù)權(quán)成環(huán)）
bool BellmanFord(const V& src, vector<W>& dist, vector<int>& pPath)
{
size_t n = _vertexs.size();
size_t srci = GetVIndex(src);
//初始化
dist.resize(n, MAX_W);
pPath.resize(n, -1);
dist[srci] = W();
//最多更新n - 1
for (size_t k = 0; k < n - 1; k++)
{
//優(yōu)化的標(biāo)志位，如果沒有松弛更短，說明所有頂點(diǎn)最短路徑都找到了
bool flag = true;
//所有頂點(diǎn)做一次松弛
for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j < n; j++)
{
//src - i - j
if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]) //更新出更短
{
dist[j] = dist[i] + _matrix[i][j];
pPath[j] = i;
flag = false;
}
}
}
if (flag)
{
break;
}
}
for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j < n; j++)
{
//還能更新說明存在負(fù)權(quán)回路問題
if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]) //更新出更短
{
return false;
}
}
}
return true;
}
5.4 多源最短路徑–Floyd-Warshall算法
- 多源最短，即求任意兩點(diǎn)的最短路徑。
- 適用于帶負(fù)權(quán)的圖。
- Floyd-Warshall算法的核心是動(dòng)態(tài)規(guī)劃。
圖解：
文章來源：http://www.zghlxwxcb.cn/news/detail-838964.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-838964.html
//多源最短路徑：FloydWarshall
//vvDist和vvPPath是二維的，vvDist[x]和vvPPath[x]表示以x為起點(diǎn)到各點(diǎn)的最短路徑情況
void FloydWarShall(vector<vector<W>>& vvDist, vector<vector<int>>& vvPPath)
{
size_t n = _vertexs.size();
vvDist.resize(n);
vvPPath.resize(n);
// 初始化權(quán)值和路徑矩陣
for (size_t i = 0; i < n; ++i)
{
vvDist[i].resize(n, MAX_W);
vvPPath[i].resize(n, -1);
}
//把直接相連的邊入進(jìn)來
for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j < n; j++)
{
if (_matrix[i][j] != MAX_W)
{
vvDist[i][j] = _matrix[i][j];
vvPPath[i][j] = i;
}
//i == j,即自己到自己
if (i == j)
{
vvDist[i][j] = W();
}
}
}
//中間經(jīng)過了(0, k)這些頂點(diǎn)
for (size_t k = 0; k < n; ++k)
{
for (size_t i = 0; i < n; i++)
{
for (size_t 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])
{
vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
vvPPath[i][j] = vvPPath[k][j];
}
}
}
}
}
5.5 幾個(gè)算法的比較
- 假設(shè)圖是稠密圖，我們使用矩陣存儲(chǔ)。 對這些算法的時(shí)間復(fù)雜度分析：
Dijkstra算法：O（N ^ 2）。
Bellman-Ford算法：O（N ^ 3）。
Floyd-Warshall算法：O（N ^ 3）。 - Dijkstra算法適用于不帶負(fù)權(quán)的圖，如果想對不帶負(fù)權(quán)的圖找多源最短路徑，也可以循環(huán)N次Dijkstra算法，效率和Floyd-Warshall差不多。
- Bellman-Ford算法和Floyd-Warshall算法都可以解決帶負(fù)權(quán)的問題。
- Bellman-Ford算法大多數(shù)情況是快于Floyd-Warshall算法的，只是要單源最短且?guī)ж?fù)權(quán)用Bellman-Ford即可。而且針對Bellman-Ford算法可以用SPFA隊(duì)列優(yōu)化。（SPFA優(yōu)化本文不講，SPFA優(yōu)化后時(shí)間復(fù)雜度不變，最壞的情況和樸素Bellman-Ford算法一致）
- Floyd-Warshall算法用于解決多源最短路徑是效果較好，而且可解決帶負(fù)權(quán)問題。
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：圖及相關(guān)算法講解的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
