一、圖的基本概念

1. 圖是由頂點(diǎn)集合及頂點(diǎn)間的關(guān)系組成的一種數(shù)據(jù)結(jié)構(gòu)：G = (V， E)，其中： 頂點(diǎn)集合V = {x|x屬于某個(gè)數(shù)據(jù)對象集}是有窮非空集合； E {(x,y)|x,y屬于V}或者E = {<x, y>|x,y屬于V && Path(x, y)}是頂點(diǎn)間關(guān)系的有窮集合，也叫做邊的集合。 (x, y)表示x到y(tǒng)的一條雙向通路，即(x, y)是無方向的；Path(x, y)表示從x到y(tǒng)的一條單向通路，即 Path(x, y)是有方向的。
2. 頂點(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>。
3. 有向圖和無向圖：在有向圖中，頂點(diǎn)對<x, y>是有序的，頂點(diǎn)對<x，y>稱為頂點(diǎn)x到頂點(diǎn)y的一條邊(弧)，<x, y>和<y, x>是兩條不同的邊，比如。在無向圖中，頂點(diǎn)對(x, y)是無序的，頂點(diǎn)對(x,y)稱為頂點(diǎn)x和頂點(diǎn)y相關(guān)聯(lián)的一條邊，這條邊沒有特定方向，(x, y)和(y，x)是同一條邊。注意：無向邊(x, y)等于有向<x, y>和<y, x>。
4. 完全圖：在有n個(gè)頂點(diǎn)的無向圖中，若有n * (n-1)/2條邊，即任意兩個(gè)頂點(diǎn)之間有且僅有一條邊，則稱此圖為無向完全圖；在n個(gè)頂點(diǎn)的有向圖中，若有n * (n-1)條邊，即任意兩個(gè)頂點(diǎn)之間有且僅有方向相反的邊，則稱此圖為有向完全圖。
5. 鄰接頂點(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)。
6. 頂點(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)。
7. 路徑：在圖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的路徑。
8. 路徑長度：對于不帶權(quán)的圖，一條路徑的路徑長度是指該路徑上的邊的條數(shù)；對于帶權(quán)的圖，一條路徑的路徑長度是指該路徑上各個(gè)邊權(quán)值的總和。
9. 簡單路徑與回路：若路徑上各頂點(diǎn)v1，v2，v3，…，vm均不重復(fù)，則稱這樣的路徑為簡單路徑。若路徑上第一個(gè)頂點(diǎn)v1和最后一個(gè)頂點(diǎn)vm重合，則稱這樣的路徑為回路或環(huán)。
10. 子圖：設(shè)圖G = {V, E}和圖G1 = {V1，E1}，若V1屬于V且E1屬于E，則稱G1是G的子圖。
11. 連通圖：在無向圖中，若從頂點(diǎn)v1到頂點(diǎn)v2有路徑，則稱頂點(diǎn)v1與頂點(diǎn)v2是連通的。如果圖中任意一對頂點(diǎn)都是連通的，則稱此圖為連通圖。
12. 強(qiáng)連通圖：在有向圖中，若在每一對頂點(diǎn)vi和vj之間都存在一條從vi到vj的路徑，也存在一條從vj到vi的路徑，則稱此圖是強(qiáng)連通圖。
13. 生成樹：一個(gè)連通圖的最小連通子圖稱作該圖的生成樹。有n個(gè)頂點(diǎn)的連通圖的生成樹有n個(gè)頂點(diǎn)和n-1條邊

二、圖的儲(chǔ)存結(jié)構(gòu)

因?yàn)閳D中既有節(jié)點(diǎn)，又有邊(節(jié)點(diǎn)與節(jié)點(diǎn)之間的關(guān)系)，因此，在圖的存儲(chǔ)中，只需要保存：節(jié)點(diǎn)和邊關(guān)系即可。

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)系。

注意：
（1）如果有權(quán)值的話，相連的邊數(shù)組保存邊的權(quán)值，不相連的邊一般用無窮大表示。
（2）無向圖的鄰接矩陣是對稱的，有向圖則不是。
（3）鄰接矩陣的優(yōu)點(diǎn)是可以快速查找兩個(gè)頂點(diǎn)是否相連，缺點(diǎn)是如果頂點(diǎn)多而邊少，就會(huì)造成空間浪費(fèi)。
代碼實(shí)現(xiàn)：

// V - 頂點(diǎn)類型，W - 權(quán)值類型, MAX_W - 權(quán)值最大值， 
// Direction - 是否有向 true - 無向 false - 無向
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph
{typedef Graph<V, W, MAX_W, Direction>  Self;public:Graph() = default;Graph(const V* vertexs, size_t n){//初始化_vertexs.resize(n);_matrix.resize(n);for (int i = 0; i < n; i++){//初始化矩陣_matrix[i].resize(n, MAX_W);//初始化映射關(guān)系_vertexs[i] = vertexs[i];_vIndexMap[vertexs[i]] = i;}}//獲取映射下標(biāo)size_t GetVertexIndex(const V& v){//查找是否存在auto ret = _vIndexMap.find(v);//存在返回索引否則返回-1if (ret != _vIndexMap.end())return ret->second;else cout<<"不存在頂點(diǎn)"<<endl;return -1;}void _AddEdge(size_t srci, size_t dsti, const W& w){//默認(rèn)有向_matrix[srci][dsti] = w;//無向if (Direction){_matrix[dsti][srci] = w;}}//添加邊void AddEdge(const V& src, const V& dst, const W& w){//獲取下標(biāo)int srci = GetVertexIndex(src);int dsti = GetVertexIndex(dst);//判斷是否存在if (srci >= 0 && dsti >= 0)_AddEdge(srci, dsti, w);}private:map<V, size_t> _vIndexMap;//元素與下標(biāo)的映射vector<V> _vertexs; // 頂點(diǎn)集合vector<vector<W>> _matrix; //矩陣
}

下面其他算法均使用鄰接矩陣實(shí)現(xiàn)。

2、鄰接表

鄰接表：使用數(shù)組表示頂點(diǎn)的集合，使用鏈表表示邊的關(guān)系。
無向圖鄰接表存儲(chǔ)：

注意：無向圖中同一條邊在鄰接表中出現(xiàn)了兩次。如果想知道頂點(diǎn)vi的度，只需要知道頂點(diǎn)vi邊鏈表集合中結(jié)點(diǎn)的數(shù)目即可。

有向圖鄰接表存儲(chǔ)：

注意：有向圖中每條邊在鄰接表中只出現(xiàn)一次，與頂點(diǎn)vi對應(yīng)的鄰接表所含結(jié)點(diǎn)的個(gè)數(shù)，就是該頂點(diǎn)的出度，也稱出度表，要得到vi頂點(diǎn)的入度，必須檢測其他所有頂點(diǎn)對應(yīng)的邊鏈表，看有多少邊頂點(diǎn)的dst取值是i。

實(shí)現(xiàn)：
只實(shí)現(xiàn)出邊表（一般只會(huì)用到）。

//頂點(diǎn)集合//W - 權(quán)值類型template<class W>struct LinkEdge{int _srcIndex;int _dstIndex;W _w;LinkEdge<W>* _next;LinkEdge(int srcIndex , int dstIndex , const W& w): _srcIndex(srcIndex), _dstIndex(dstIndex), _w(w), _next(nullptr){}};//V - 頂點(diǎn)類型，W - 權(quán)值類型// Direction - 是否有向 true - 無向 false - 無向template<class V, class W, bool Direction = false>class Graph{typedef LinkEdge<W> Edge;public:Graph() = default;//初始化Graph(const V* vertexs, size_t n){//初始化_linkTable.resize(n,nullptr);_vertexs.resize(n);for (int i = 0; i < n; i++){//初始化映射關(guān)系_vertexs[i] = vertexs[i];_vIndexMap[vertexs[i]] = i;}}//獲取下表size_t GetVertexIndex(const V& v){//查找是否存在auto ret = _vIndexMap.find(v);//存在返回索引否則返回-1if (ret != _vIndexMap.end())return ret->second;elsecout << "不存在該頂點(diǎn)" << endl;return -1;}//添加邊void AddEdge(const V& src, const V& dst,  const W& w){//獲取映射下標(biāo)int srci = GetVertexIndex(src);int dsti = GetVertexIndex(dst);if (srci == -1 || dsti == -1)return;//使用頭插法//有向圖Edge* srceg = new Edge(srci, dsti, w);srceg->_next = _linkTable[srci];_linkTable[srci] = srceg;//無向圖if (Direction){Edge* dsteg = new Edge(dsti, srci, w);dsteg->_next =  _linkTable[dsti];_linkTable[dsti] = dsteg;}}private:map<string, int> _vIndexMap;	//頂點(diǎn)與下標(biāo)的映射關(guān)系vector<V> _vertexs; // 頂點(diǎn)集合vector<Edge*> _linkTable;	//鄰接表};

三、圖的遍歷

1、廣度優(yōu)先遍歷

通過一個(gè)頂點(diǎn)一層層不斷往外擴(kuò)。

怎么實(shí)現(xiàn)？
（1）通過一個(gè)數(shù)組記錄頂點(diǎn)是否被遍歷到。
（2）通過隊(duì)列，每次將隊(duì)列的頂點(diǎn)拿出，并將其指向的頂點(diǎn)入隊(duì)，循環(huán)上述操作。

//廣度優(yōu)先遍歷
void BFS(const V& src)
{//獲取索引int srci = GetVertexIndex(src);//節(jié)點(diǎn)數(shù)int n = _vertexs.size();//標(biāo)記數(shù)組vector<bool> vis(n);//通過隊(duì)列遍歷訪問queue<int> q;q.push(srci);vis[srci] = true;while (!q.empty()){//一層一層遍歷int sz = q.size();for (int i = 0; i < sz; i++){//取隊(duì)頭元素int index = q.front();q.pop();cout << index << ": " << _vertexs[index]<<" | ";//將與隊(duì)頭元素連接且滅訪問過的點(diǎn)進(jìn)隊(duì)并做標(biāo)記for (int j = 0; j < n; j++){if (vis[j] == false && _matrix[index][j] != MAX_W){vis[j] = true;q.push(j);}}}cout << endl;}
}

2、深度優(yōu)先遍歷

怎么實(shí)現(xiàn)？
從一個(gè)頂點(diǎn)出發(fā)，找到下一個(gè)頂點(diǎn)，再次以這個(gè)頂點(diǎn)出發(fā)，重復(fù)上述操作，直到找不到下一個(gè)頂點(diǎn)就進(jìn)行回溯。

void _DFS(int index, vector<bool>& vis)
{cout << index << ": " << _vertexs[index] << endl;//將index指向且沒有訪問過的節(jié)點(diǎn)進(jìn)行標(biāo)配并遞歸搜索for (int i = 0; i < _vertexs.size(); i++){if (vis[i] == false && _matrix[index][i] != MAX_W){vis[i] = true;_DFS(i, vis);}}
}//深度優(yōu)先搜索
void DFS(const V& v)
{	//標(biāo)記數(shù)組vector<bool> vis(_vertexs.size());//獲取v的索引int srci = GetVertexIndex(v);//進(jìn)行遍歷_DFS(srci, vis);//將剩下沒有遍歷到的節(jié)點(diǎn)遍歷for (int i = 0; i < _vertexs.size(); i++){if (vis[i] == false)_DFS(i, vis);}
}

四、最小生成樹

1、概念

連通圖中的每一棵生成樹，都是原圖的一個(gè)極大無環(huán)子圖，即：從其中刪去任何一條邊，生成樹就不在連通；反之，在其中引入任何一條新邊，都會(huì)形成一條回路。
若連通圖由n個(gè)頂點(diǎn)組成，則其生成樹必含n個(gè)頂點(diǎn)和n-1條邊。因此構(gòu)造最小生成樹的準(zhǔn)則有三條：

1. 只能使用圖中的邊來構(gòu)造最小生成樹
2. 只能使用恰好n-1條邊來連接圖中的n個(gè)頂點(diǎn)
3. 選用的n-1條邊不能構(gòu)成回路 構(gòu)造最小生成樹的方法：Kruskal算法和Prim算法。這兩個(gè)算法都采用了逐步求解的貪心策略。

2、Kruskal算法

任給一個(gè)有n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)N={V,E}，首先構(gòu)造一個(gè)由這n個(gè)頂點(diǎn)組成、不含任何邊的圖G={V,NULL}，其中每個(gè)頂點(diǎn)自成一個(gè)連通分量， 其次不斷從E中取出權(quán)值最小的一條邊(若有多條任取其一)，若該邊的兩個(gè)頂點(diǎn)來自不同的連通分量，則將此邊加入到G中。如此重復(fù)，直到所有頂點(diǎn)在同一個(gè)連通分量上為止。
核心：每次迭代時(shí)，選出一條具有最小權(quán)值，且兩端點(diǎn)不在同一連通分量上的邊，加入生成樹。

上圖來自算法導(dǎo)論。

怎么實(shí)現(xiàn)？
（1）使用一個(gè)結(jié)構(gòu)體保存邊的信息。
（2）使用優(yōu)先隊(duì)列（小的在隊(duì)頭）將所有邊進(jìn)隊(duì)。
（3）開始挑邊，在挑的過程中使用一個(gè)并查集（將選頂點(diǎn)和不選的頂點(diǎn)分成兩個(gè)集合）判斷是否成環(huán)，直到挑到n-1（n：頂點(diǎn)的個(gè)數(shù)）條邊結(jié)束。

//并查集
#include<iostream>
#include<vector>using namespace std;class UnionFindSet
{
public:UnionFindSet(size_t size):_ufs(size, -1){}// 給一個(gè)元素的編號(hào)，找到該元素所在集合的名稱int FindRoot(int index){int root = index;while (_ufs[root] >= 0){root = _ufs[root];}while(_ufs[index] >= 0){int p = _ufs[index];_ufs[index] = root;index = p;}return root;}//將兩個(gè)元素合拼到同一個(gè)集合里bool Union(int x1, int x2){int root1 = FindRoot(x1);int root2 = FindRoot(x2);if (root1 == root2)return false;//小的并到大的里面if(abs(_ufs[root1]) < abs(_ufs[root2]))swap(root1,root2);_ufs[root1] += _ufs[root2];_ufs[root2] = root1;return true;}// 數(shù)組中負(fù)數(shù)的個(gè)數(shù)，即為集合的個(gè)數(shù)size_t Count()const{size_t ret = 0;for (int i = 0; i < _ufs.size(); i++){if (_ufs[i] < 0)ret++;}return ret;}//判斷兩個(gè)元素是否在同一個(gè)集合里bool IsGather(int x1, int x2){return FindRoot(x1) == FindRoot(x2);}private:std::vector<int> _ufs;
};//W - 權(quán)值類型
template<class W>
struct Edge
{int _srci;int _dsti;W _w;Edge(int srci, int dsti, const W& w): _srci(srci), _dsti(dsti), _w(w){}//重載大于bool operator>( const Edge<W>& e) const{return _w > e._w;}
};//最小生成樹 -- Kruskal算法
W Kruskal(Self& minTree)
{//通過現(xiàn)有的圖對minTree進(jìn)行初始化int n = _vertexs.size();minTree._vertexs = _vertexs;minTree._vIndexMap = _vIndexMap;minTree._matrix.resize(n);for (int i = 0; i < n; i++){minTree._matrix[i].resize(n, MAX_W);}//使用優(yōu)先隊(duì)列保存所有邊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]));}}}//通過并查集來判環(huán)UnionFindSet ufs(n);//開始選邊 -- 選n-1條int count = 0;//記錄邊的數(shù)W ret = W();//記錄權(quán)值while (!pq.empty()){//取隊(duì)頭元素Edge e = pq.top();pq.pop();//只要兩個(gè)點(diǎn)不同時(shí)在ufs中說明這條邊可選if (!ufs.IsGather(e._srci, e._dsti)){//加入并查集ufs.Union(e._srci,e._dsti);//添加邊minTree._AddEdge(e._srci,e._dsti,e._w);count++;ret += e._w;}//選完邊結(jié)束if(count == n-1)break;}return ret;}

3、Prim算法

上圖來自算法導(dǎo)論。

怎么實(shí)現(xiàn)
（1）從一個(gè)頂點(diǎn)開始，將與其相連的邊加入優(yōu)先隊(duì)列（小的在隊(duì)頭）。
（2）使用一個(gè)vector容器標(biāo)記頂點(diǎn)是否被訪問
（3）出隊(duì)，通過被指向的邊是否被標(biāo)記來判環(huán)（該邊的起點(diǎn)肯定已經(jīng)被標(biāo)記了，因?yàn)樵撨呥M(jìn)隊(duì)時(shí)就是選擇被標(biāo)記的點(diǎn)作為起點(diǎn)的），沒被標(biāo)記，選擇，直到選擇n-1（n:頂點(diǎn)數(shù)）條邊。

//W - 權(quán)值類型
template<class W>
struct Edge
{int _srci;int _dsti;W _w;Edge(int srci, int dsti, const W& w): _srci(srci), _dsti(dsti), _w(w){}//重載大于bool operator>( const Edge<W>& e) const{return _w > e._w;}
};
//最小生成樹 -- Prim算法
W Prim(Self& minTree, const V& src)
{//通過現(xiàn)有的圖對minTree進(jìn)行初始化int n = _vertexs.size();minTree._vertexs = _vertexs;minTree._vIndexMap = _vIndexMap;minTree._matrix.resize(n);for (int i = 0; i < n; i++){minTree._matrix[i].resize(n, MAX_W);}//標(biāo)記點(diǎn)是否被選vector<int> vis(n);int srci = GetVertexIndex(src);vis[srci] = true;//使用優(yōu)先隊(duì)列保存當(dāng)前點(diǎn)出去的邊priority_queue<Edge, vector<Edge>, greater<Edge>> pq;for (int i = 0; i < n; i++){if (_matrix[srci][i] != MAX_W){pq.push(Edge(srci, i, _matrix[srci][i]));}}W ret = W();//記錄權(quán)值int count = 0;//記錄當(dāng)前邊數(shù)while (!pq.empty()){//取出隊(duì)頭元素Edge e = pq.top();pq.pop();//判環(huán) --只要當(dāng)前邊的e._dsti沒被標(biāo)記就行，因?yàn)樵撨吺怯蒭._srci點(diǎn)發(fā)出的，所以//e._srci肯定被標(biāo)志了，不用判斷if (vis[e._dsti] == false){//修改標(biāo)志vis[e._dsti] = true;//添加邊minTree._AddEdge(e._srci, e._dsti, e._w);//將新加入的點(diǎn)出去的邊添加到優(yōu)先隊(duì)列中for (int i = 0; i < n; i++){if (_matrix[e._dsti][i] != MAX_W){pq.push(Edge(e._dsti, i, _matrix[e._dsti][i]));}}ret += e._w;count++;}//選完了結(jié)束if (count == n - 1)break;}return ret;
}

五、最短路徑問題

最短路徑問題：從在帶權(quán)有向圖G中的某一頂點(diǎn)出發(fā)，找出一條通往另一頂點(diǎn)的最短路徑，最短也就是沿路徑各邊的權(quán)值總和達(dá)到最小。

1、單源最短路徑–Dijkstra算法

1. 單源最短路徑問題：給定一個(gè)圖G = ( V ， E ) G=(V，E)G=(V，E)，求源結(jié)點(diǎn)s ∈ V s∈Vs∈V到圖 中每個(gè)結(jié)點(diǎn)v ∈ V v∈Vv∈V的最短路徑。Dijkstra算法就適用于解決帶權(quán)重的有向圖上的單源最短 路徑問題，同時(shí)算法要求圖中所有邊的權(quán)重非負(fù)。一般在求解最短路徑的時(shí)候都是已知一個(gè)起點(diǎn)和一個(gè)終點(diǎn)，所以使用Dijkstra算法求解過后也就得到了所需起點(diǎn)到終點(diǎn)的最短路徑。
2. 針對一個(gè)帶權(quán)有向圖G，將所有結(jié)點(diǎn)分為兩組S和Q，S是已經(jīng)確定最短路徑的結(jié)點(diǎn)集合，在初始時(shí) 為空（初始時(shí)就可以將源節(jié)點(diǎn)s放入，畢竟源節(jié)點(diǎn)到自己的代價(jià)是0），Q 為其余未確定最短路徑 的結(jié)點(diǎn)集合，每次從Q
   中找出一個(gè)起點(diǎn)到該結(jié)點(diǎn)代價(jià)最小的結(jié)點(diǎn)u ，將u 從Q 中移出，并放入S 中，對u 的每一個(gè)相鄰結(jié)點(diǎn)v 進(jìn)行松弛操作。松弛即對每一個(gè)相鄰結(jié)點(diǎn)v ，判斷源節(jié)點(diǎn)s到結(jié)點(diǎn)u 的代價(jià)與u 到v 的代價(jià)之和是否比原來s 到v 的代價(jià)更小，若代價(jià)比原來小則要將s 到v 的代價(jià)更新 為s 到u 與u 到v 的代價(jià)之和，否則維持原樣。如此一直循環(huán)直至集合Q 為空，即所有節(jié)點(diǎn)都已經(jīng) 查找過一遍并確定了最短路徑，至于一些起點(diǎn)到達(dá)不了的結(jié)點(diǎn)在算法循環(huán)后其代價(jià)仍為初始設(shè)定 的值，不發(fā)生變化。Dijkstra算法每次都是選擇V-S中最小的路徑節(jié)點(diǎn)來進(jìn)行更新，并加入S中，所 以該算法使用的是貪心策略。
3. Dijkstra算法存在的問題是不支持圖中帶負(fù)權(quán)路徑，如果帶有負(fù)權(quán)路徑，則可能會(huì)找不到一些路 徑的最短路徑。

上圖來自算法導(dǎo)論。

//src -- 開始的點(diǎn) dist -- src到每個(gè)點(diǎn)的最短距離 
// parentPath -- 記錄src到其他點(diǎn)的過程上的最近頂點(diǎn) 如：src -> k -> j j點(diǎn)記錄的是k的下標(biāo)
void Dijkstra(const V& src, vector<W>& dist, vector<int>& parentPath)
{//初始化int n = _vertexs.size();dist.resize(n, MAX_W);parentPath.resize(n, -1);//標(biāo)記數(shù)組vector<bool> vis(n);//給dist數(shù)組srci位置賦最小值，方便第一次找到int srci = GetVertexIndex(src);dist[srci] = W();//n個(gè)頂點(diǎn)更新n次for (int i = 0; i < n; i++){int u = 0;int min = MAX_W;//到srci最小的點(diǎn)for(int j = 0; j < n; j++){if (vis[j] == false && min > dist[j]){u = j;min = dist[j];}}//標(biāo)志vis[u] = true;//松弛操作//	更新u->其他點(diǎn)（srci->u->其他點(diǎn)）的distfor (int k = 0; k < n; k++){if (vis[k] == false && _matrix[u][k] != MAX_W &&dist[k] > dist[u] + _matrix[u][k]){dist[k] = dist[u] + _matrix[u][k];parentPath[k] = u;}}}
}

2、單源最短路徑–Bellman-Ford算法

Dijkstra算法只能用來解決正權(quán)圖的單源最短路徑問題，但有些題目會(huì)出現(xiàn)負(fù)權(quán)圖。這時(shí)這個(gè)算法 就不能幫助我們解決問題了，而bellman—ford算法可以解決負(fù)權(quán)圖的單源最短路徑問題。它的 優(yōu)點(diǎn)是可以解決有負(fù)權(quán)邊的單源最短路徑問題，而且可以用來判斷是否有負(fù)權(quán)回路。它也有明顯 的缺點(diǎn)，它的時(shí)間復(fù)雜度 O(N*E) (N是點(diǎn)數(shù)，E是邊數(shù))普遍是要高于Dijkstra算法O(N2)的。像這里 如果我們使用鄰接矩陣實(shí)現(xiàn)，那么遍歷所有邊的數(shù)量的時(shí)間復(fù)雜度就是O(N^3)，這里也可以看出 來Bellman-Ford就是一種暴力求解更新

上圖來自算法導(dǎo)論。

//src -- 開始的點(diǎn) dist -- src到每個(gè)點(diǎn)的最短距離 
// parentPath -- 記錄src到其他點(diǎn)的過程上的最近頂點(diǎn) 如：src -> k -> j j點(diǎn)記錄的是k的下標(biāo)
bool BellmanFord(const V& src, vector<W>& dist, vector<int>& parentPath)
{size_t n = _vertexs.size();size_t srci = GetVertexIndex(src);// vector<W> dist,記錄srci-其他頂點(diǎn)最短路徑權(quán)值數(shù)組dist.resize(n, MAX_W);// vector<int> parentPath 記錄srci-其他頂點(diǎn)最短路徑父頂點(diǎn)數(shù)組parentPath.resize(n, -1);// 先更新srci->srci為最小值,方便第一次找到dist[srci] = W();//最多更新n-1次（最壞的情況就是到另一個(gè)點(diǎn)需要更新n-1次）for (int k = 0; k < n-1; k++){//標(biāo)記，如果沒有修改則完成查找最短路徑bool flag = false;for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){//找到更小的了，進(jìn)行修改if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]){cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _matrix[i][j] << " | ";dist[j] = dist[i] + _matrix[i][j];parentPath[j] = i;flag = true;}}}//全部都是最短路徑了 - 結(jié)束if (flag == false)break;}//檢查有沒有負(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;}}}return true;
}

3、多源最短路徑–Floyd-Warshall算法

Floyd-Warshall算法是解決任意兩點(diǎn)間的最短路徑的一種算法。
Floyd算法考慮的是一條最短路徑的中間節(jié)點(diǎn)，即簡單路徑p={v1,v2,…,vn}上除v1和vn的任意節(jié)點(diǎn)。設(shè)k是p的一個(gè)中間節(jié)點(diǎn)，那么從i到j(luò)的最短路徑p就被分成i到k和k到j(luò)的兩段最短路徑p1，p2。p1是從i到k且中間節(jié)點(diǎn)屬于{1，2，…，k-1}取得的一條最短路徑。p2是從k到j(luò)且中間節(jié)點(diǎn)屬于{1，2，…，k-1}取得的一條最短路徑。

上圖來自算法導(dǎo)論。

即Floyd算法本質(zhì)是三維動(dòng)態(tài)規(guī)劃，D[i][j][k]表示從點(diǎn)i到點(diǎn)j只經(jīng)過0到k個(gè)點(diǎn)最短路徑，然后建立起轉(zhuǎn)移方程，然后通過空間優(yōu)化，優(yōu)化掉最后一維度，變成一個(gè)最短路徑的迭代算法，最后即得到所以點(diǎn)的最短路。

//vvDist -- 記錄全部的點(diǎn)到其他點(diǎn)的小權(quán)值 
//vvParentPath -- 記錄全部點(diǎn)到其他點(diǎn)的過程上的最近頂點(diǎn) 如：src -> k -> j j點(diǎn)記錄的是k的下標(biāo)
void FloydWarShall(vector<vector<W>>& vvDist, vector<vector<int>>&vvParentPath)
{// 初始化size_t n = _vertexs.size();vvDist.resize(n);vvParentPath.resize(n);//初始化權(quán)值和路徑矩陣for (size_t i = 0; i < n; ++i){vvDist[i].resize(n, MAX_W);vvParentPath[i].resize(n, -1);}//將相連的邊連在一起for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){if (_matrix[i][j] != MAX_W){vvDist[i][j] = _matrix[i][j];vvParentPath[i][j] = i;}else if (i == j){vvDist[i][j] = W();vvParentPath[i][j] = -1;}}}//將k作為中轉(zhuǎn)點(diǎn)依次遍歷for (int k = 0; k < n; k++){for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){//i ->( k )-> jif (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];vvParentPath[i][j] = vvParentPath[k][j];}}}}}

六、拓?fù)渑判?/h3>

1、概念

拓?fù)渑判蚴菍τ邢驘o環(huán)圖（DAG）頂點(diǎn)的一種排序。 在一個(gè)DAG中，如果存在一條有向邊(u, v)，那么在拓?fù)渑判虻慕Y(jié)果中，頂點(diǎn)u會(huì)排在頂點(diǎn)v的前面。它主要用于解決任務(wù)調(diào)度、課程學(xué)習(xí)順序等依賴關(guān)系問題（就是找做事情的先后順序），通?？梢杂蒙疃葍?yōu)先搜索（DFS）或 Kahn算法來實(shí)現(xiàn)拓?fù)渑判颉?br /> 注意：拓?fù)渑判虻捻樞虿晃ㄒ弧?/p>

2、如何排序

以下是使用 Kahn 算法實(shí)現(xiàn)拓?fù)渑判虻牟襟E：

1. 。
   遍歷有向圖中的所有邊，對于每條邊(u, v)，將頂點(diǎn) v 的入度加一。
2. 將入度為 0 的頂點(diǎn)加入隊(duì)列。
   初始化一個(gè)隊(duì)列，用于存儲(chǔ)入度為 0 的頂點(diǎn)。遍歷所有頂點(diǎn)，將入度為 0 的頂點(diǎn)加入隊(duì)列。
3. 進(jìn)行拓?fù)渑判颉?
   創(chuàng)建一個(gè)空列表，用于存儲(chǔ)排序后的頂點(diǎn)。當(dāng)隊(duì)列不為空時(shí)，從隊(duì)列中取出一個(gè)頂點(diǎn) u。將頂點(diǎn) u 加入排序后的列表中。遍歷頂點(diǎn) u 的所有鄰接頂點(diǎn) v，將頂點(diǎn) v 的入度減一。如果頂點(diǎn) v 的入度變?yōu)?0，則將其加入隊(duì)列。
4. 檢查是否存在有向環(huán)。
   如果排序后的列表中頂點(diǎn)的數(shù)量與圖中的頂點(diǎn)數(shù)量相同，則說明圖中不存在有向環(huán)，拓?fù)渑判虺晒?。否則，說明圖中存在有向環(huán)，無法進(jìn)行拓?fù)渑判颉?/li>

3、實(shí)現(xiàn)

//拓?fù)渑判?/span>
//graph數(shù)組 -- 下標(biāo)指向一個(gè)vector<int>,vector<int> - 該下標(biāo)頂點(diǎn)指向的頂點(diǎn)
//如0 -> {1,2} ,在圖中有兩條邊（0，1），（0，2）
vector<int> topologicalSort(vector<vector<int>>& graph) 
{//1、統(tǒng)計(jì)入度int n = graph.size();vector<int> in(n, 0);for (int i = 0; i < n; i++){for (auto e : graph[i])in[e]++;}//2、將入度為0的進(jìn)隊(duì)列queue<int> q;for (int i = 0; i < n; i++){if (in[i] == 0)q.push(i);}//3、拓?fù)渑判?/span>vector<int> ret;while (!q.empty()){//出隊(duì)int front = q.front();q.pop();//加入ret.push_back(front);//將front指向的入度減1for (auto e : graph[front]){in[e]--;//再次統(tǒng)計(jì)入度為0的頂點(diǎn)if (in[e] == 0)q.push(e);}}//4、判斷是否存在有向環(huán)if (ret.size() < n)return {};return ret;
}

4、應(yīng)用

題目：課程表

使用算法：拓?fù)渑判?br /> 這題多了一步就是需要我們自己建圖，遍歷prerequisites使用vector<vector> 或者map<int,vector>，將圖建（如頂點(diǎn)a指向其他頂點(diǎn)的集合）出來，其他步驟和上述代碼差不多了。

代碼實(shí)現(xiàn)：

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {//1、建圖vector<vector<int>> graph(numCourses);int n = prerequisites.size();for(int i = 0; i < n; i++){int a = prerequisites[i][0];int b = prerequisites[i][1];graph[b].push_back(a);}//統(tǒng)計(jì)入度vector<int> in(numCourses, 0);for (int i = 0; i < numCourses; i++){for (auto e : graph[i]){in[e]++;}}//3、將入度為0的進(jìn)隊(duì)列queue<int> q;for (int i = 0; i < numCourses; i++){if (in[i] == 0)q.push(i);}//4、拓?fù)渑判?/span>while (!q.empty()){//出隊(duì)int front = q.front();q.pop();//將front指向的入度減1for (auto e : graph[front]){in[e]--;//再次統(tǒng)計(jì)入度為0的頂點(diǎn)if (in[e] == 0)q.push(e);}}//4、判斷是否存在有向環(huán)for(int i = 0; i < numCourses; i++){if(in[i]) return false;}return true;}
};