图是在数据结构中难度比较大，并且比较抽象一种数据结构。
图在地图，社交网络这方面有应用。
图的基本概念
图是由顶点集合及顶点间的关系组成的一种数据结构：G=（V，E）。图标的英文：graph。
(x, y) 表示 x 到 y 的一条双向通路，即 (x, y) 是无方向的； Path(x, y) 表示从 x 到 y 的一条单向通路，即
Path(x, y) 是有方向的。
顶点和边： 图中结点称为顶点 ，第 i 个顶点记作 vi 。 两个顶点 vi 和 vj 相关联称作顶点 vi 和顶点 vj 之间
有一条边 ，图中的第 k 条边记作 ek ， ek = (vi ， vj) 或 <vi ， vj> 。
有向图和无向图： 在有向图中，顶点对 <x, y> 是有序的，顶点对 <x ， y> 称为顶点 x 到顶点 y 的一条
边 ( 弧 ) ， <x, y> 和 <y, x> 是两条不同的边， 在 无向图中，顶点对 (x, y) 是无序的，顶点对 (x,y) 称为顶点 x 和顶点 y 相关联的一条边，这条边没有特定方向， (x, y) 和 (y ， x) 是同一条边，注意： 无向边 (x, y) 等于有向边 <x, y> 和 <y, x> 。
树是一种特殊的图（无环联通）。
图不一定是树。
树关注结点中存的值。
图关注的是顶点及边的权值。
图的一些其他的概念：
完全图：在 有 n 个顶点的无向图中 ，若 有 n * (n-1)/2 条边 ，即 任意两个顶点之间有且仅有一条边 ，
则称此图为 无向完全图 ，比如上图 G1 ；在 n 个顶点的有向图 中，若 有 n * (n-1) 条边 ，即 任意两个
顶点之间有且仅有方向相反的边 ，则称此图为 有向完全图。
邻接顶点：在 无向图中 G 中，若 (u, v) 是 E(G) 中的一条边，则称 u 和 v 互为邻接顶点 ，并称 边 (u,v) 依
附于顶点 u 和 v ；在 有向图 G 中，若 <u, v> 是 E(G) 中的一条边，则称顶点 u 邻接到 v ，顶点 v 邻接自顶
点 u ，并称边 <u, v> 与顶点 u 和顶点 v 相关联 。
顶点的度： 顶点 v 的度是指与它相关联的边的条数，记作 deg(v) 。在有向图中， 顶点的度等于该顶
点的入度与出度之和 ，其中顶点 v 的 入度是以 v 为终点的有向边的条数 ，记作 indev(v); 顶点 v 的 出度
是以 v 为起始点的有向边的条数 ，记作 outdev(v) 。因此： dev(v) = indev(v) + outdev(v) 。注 意：对于无向图，顶点的度等于该顶点的入度和出度，即 dev(v) = indev(v) = outdev(v) 。
路径：在图 G = (V ， E) 中，若 从顶点 vi 出发有一组边使其可到达顶点 vj ，则称顶点 vi 到顶点 vj 的顶
点序列为从顶点 vi 到顶点 vj 的路径 。
路径长度：对于 不带权的图，一条路径的路径长度是指该路径上的边的条数 ；对于 带权的图，一
条路 径的路径长度是指该路径上各个边权值的总和 。
简单路径与回路： 若路径上各顶点 v1 ， v2 ， v3 ， … ， vm 均不重复，则称这样的路径为简单路
径 。 若路 径上第一个顶点 v1 和最后一个顶点 vm 重合，则称这样的路径为回路或环 。
子图： 设图 G = {V, E} 和图 G1 = {V1 ， E1} ，若 V1 属于 V 且 E1 属于 E ，则称 G1 是 G 的子图 。
连通图：在 无向图 中，若从顶点 v1 到顶点 v2 有路径，则称顶点 v1 与顶点 v2 是连通的。 如果图中任
意一 对顶点都是连通的，则称此图为连通图。注意连通图是无向图。
强连通图：在 有向图 中，若在 每一对顶点 vi 和 vj 之间都存在一条从 vi 到 vj 的路径，也存在一条从 vj
到 vi 的路径，则称此图是强连通图。注意是强连通图指的是有向图。
生成树：一个 连通图的最小连通子图 称作该图的生成树。 有 n 个顶点的连通图的生成树有 n 个顶点
和 n- 1 条边 。
图可以表示城市之间的关系，也还可以表示社交关系。比如顶点是人的话，那么边就是好友，边权值就是亲密度这些。像微信，qq这样的就是无向图，只要是好友，就可以双方互发和接收消息，那么这个也就是强社交关系。像抖音，微博这些，我们关注别人，但是别人没有关注我们，就只能单方面发送消息，而不能接收对方发来的消息，那么这个就是弱社交关系。
图的存储结构
邻接矩阵
因为节点与节点之间的关系就是连通与否，即为 0 或者 1 ，因此 邻接矩阵 ( 二维数组 ) 即是：先用一
个数组将定点保存，然后采用矩阵来表示节点与节点之间的关系 。
无向图：
我们发现无向图的矩阵沿着对角线对称，所以其实可以将矩阵压缩成一半，不过这样的就更加抽象复杂了。
有向图：
如果边带权值，那么我们可以在邻接矩阵中存权值，如果两个结点之间不连通，则可以用特殊数字代替，比如无穷大
总结：
邻接矩阵有两个优点：
1.它非常适合用来储存稠密图。（稠密图就是相对于稀疏图，它有相对较多的边）
2.邻接矩阵可以用O（1）的时间复杂度来判断两个顶点的关系，并取到权值。
但是它也有一个缺点：
就是它不适合找一个顶点链接的所有边。O（N）复杂度。
邻接表
邻接表：用数组表示顶点的合集，用链表表示边的关系。
可以看到其实它也有分入边表和出边表，但是大多数情况下就只用出边表。
看着这个结构，我们发现跟思想跟哈希桶很像。
对照邻接矩阵的优缺点来看，邻接表和邻接矩阵属于相辅相成，各有优缺点的互补结构。
邻接表的简单实现
namespace link_table
{
template<class W>
struct Edge
{
int _dsti;
W _w;
Edge<W>* _next;
Edge(int dsti, const W& w)
:_dsti(dsti)
, _w(w)
, _next(nullptr)
{}
};
template <class V, class W, bool Direction = false>
class Graph
{
typedef Edge<W> Edge;
public:
Graph(const V* a, size_t n)
{
_vertexs.reserve(n);
for (size_t i = 0; i < n; ++i)
{
_vertexs.push_back(a[i]);
_indexMap[a[i]] = i;
}
_tables.resize(n, nullptr);
}
size_t GetVertexIndex(const V& v)
{
auto it = _indexMap.find(v);
if (it != _indexMap.end())
{
return it->second;
}
else
{
throw invalid_argument("顶点不存在");
return -1;
}
}
void AddEdge(const V& src, const V& dst, const W& w)
{
size_t srci = GetVertexIndex(src);
size_t dsti = GetVertexIndex(dst);
Edge* eg = new Edge(dsti, w);
eg->_next = _tables[srci];
_tables[srci] = eg;
if (Direction == false)
{
Edge* eg = new Edge(srci, w);
eg->_next = _tables[dsti];
_tables[dsti] = eg;
}
}
void Print()
{
// 顶点
for (size_t i = 0; i < _vertexs.size(); ++i)
{
cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
}
cout << endl;
for (size_t i = 0; i < _tables.size(); ++i)
{
cout << _vertexs[i] << "[" << i << "]->";
Edge* cur = _tables[i];
while (cur)
{
cout << "[" << _vertexs[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << "]->";
cur = cur->_next;
}
cout << "nullptr" << endl;
}
}
private:
vector<V> _vertexs;
map<V, int> _indexMap;
vector<Edge*> _tables;
};
void TestGraph1()
{
/*Graph<char, int, true> g("0123", 4);
g.AddEdge('0', '1', 1);
g.AddEdge('0', '3', 4);
g.AddEdge('1', '3', 2);
g.AddEdge('1', '2', 9);
g.AddEdge('2', '3', 8);
g.AddEdge('2', '1', 5);
g.AddEdge('2', '0', 3);
g.AddEdge('3', '2', 6);
g.Print();*/
string a[] = { "张三", "李四", "王五", "赵六" };
Graph<string, int, true> g1(a, 4);
g1.AddEdge("张三", "李四", 100);
g1.AddEdge("张三", "王五", 200);
g1.AddEdge("王五", "赵六", 30);
g1.Print();
}
}
图的遍历
图的遍历并不是很难，在实现上有点像树的遍历，也分为广度优先遍历和深度优先遍历。
以邻接矩阵来实现两种遍历
广度优先遍历
void BFS(const V& src)
{
size_t srci = GetVertexIndex(src);
// 队列和标记数组
queue<int> q;
vector<bool> visited(_vertexs.size(), false);
q.push(srci);
visited[srci] = true;
int levelSize = 1;
size_t n = _vertexs.size();
while (!q.empty())
{
for (int i = 0; i < levelSize; ++i)
{
int front = q.front();
q.pop();
cout << front << ":" << _vertexs[front] << " ";
for (size_t i = 0; i < n; ++i)
{
if (_matrix[front][i] != MAX_W)
{
if (visited[i] == false)
{
q.push(i);
visited[i] = true;
}
}
}
}
cout << endl;
levelSize = q.size();
}
cout << endl;
}有点像树的层序遍历 。
深度优先遍历
void _DFS(size_t srci, vector<bool>& visited)
{
cout << srci << ":" << _vertexs[srci] << endl;
visited[srci] = true;
for (size_t i = 0; i < _vertexs.size(); ++i)
{
if (_matrix[srci][i] != MAX_W && visited[i] == false)
{
_DFS(i, visited);
}
}
}
void DFS(const V& src)
{
size_t srci = GetVertexIndex(src);
vector<bool> visited(_vertexs.size(), false);
_DFS(srci, visited);
}加一个bool数组这样的来标记已经访问过的结点。
最小生成树
若连通图由n个顶点构成，则生成树必包含n个顶点和n-1条边。构成最小生成树有三个准则：
1.只能用图中的边来构造最小生成树。
2.只能使用恰好n-1条边来连接图中的n个顶点。
3.选用的n-1条边不能构成回路。
构造最小生成树的算法有kruskal算法和prim算法，二者都是用了贪心策略。
贪心算法：是指在问题求解时，总是做出当前看起来最好的选择。也就是说贪心算法做出的不是
整体
最优的的选择，而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优
解。
kruskal算法
这个算法就是每次都找到权值最小的边，直到能成为一棵树。这个算法有一个难点就是，我们找边是按最小权值来找的，因此有可能出现环的问题。但是之前我们学过并查集，可以把存入的边放入并查集中，这样判断是否会成环就简单多了。
我们可以将边放入一个小堆当中，这样每次找最小的边时效率非常高。
邻接矩阵+kruskal算法
#pragma once
#include <vector>
#include <map>
#include <string>
#include <queue>
#include <functional>
using namespace std;
namespace matrix
{
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* a, size_t n)
{
_vertexs.reserve(n);
for (size_t i = 0; i < n; ++i)
{
_vertexs.push_back(a[i]);
_indexMap[a[i]] = i;
}
_matrix.resize(n);
for (size_t i = 0; i < _matrix.size(); ++i)
{
_matrix[i].resize(n, MAX_W);
}
}
size_t GetVertexIndex(const V& v)
{
auto it = _indexMap.find(v);
if (it != _indexMap.end())
{
return it->second;
}
else
{
throw invalid_argument("顶点不存在!");
return -1;
}
}
void _AddEdge(size_t srci, size_t dsti, const W& w)
{
_matrix[srci][dsti] = w;
//无向图
if (Direction == false)
{
_matrix[dsti][srci] = w;
}
}
void AddEdge(const V& src, const V& dst, const W& w)
{
size_t srci = GetVertexIndex(src);
size_t dsti = GetVertexIndex(dst);
_AddEdge(srci, dsti, w);
}
void Print()
{
for (size_t i = 0; i < _vertexs.size(); ++i)
{
cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
}
cout << endl;
cout << " ";
for (size_t i = 0; i < _vertexs.size(); ++i)
{
printf("%4d", i);
}
cout << endl;
for (size_t i = 0; i < _matrix.size(); ++i)
{
cout << i << " "; // 竖下标
for (size_t j = 0; j < _matrix[i].size(); ++j)
{
if (_matrix[i][j] == MAX_W)
{
printf("%4c", '#');
}
else
{
printf("%4d", _matrix[i][j]);
}
}
cout << endl;
}
cout << endl;
}
void BFS(const V& src)
{
size_t srci = GetVertexIndex(src);
// 队列和标记数组
queue<int> q;
vector<bool> visited(_vertexs.size(), false);
q.push(srci);
visited[srci] = true;
int levelSize = 1;
size_t n = _vertexs.size();
while (!q.empty())
{
for (int i = 0; i < levelSize; ++i)
{
int front = q.front();
q.pop();
cout << front << ":" << _vertexs[front] << " ";
for (size_t i = 0; i < n; ++i)
{
if (_matrix[front][i] != MAX_W)
{
if (visited[i] == false)
{
q.push(i);
visited[i] = true;
}
}
}
}
cout << endl;
levelSize = q.size();
}
cout << endl;
}
void _DFS(size_t srci, vector<bool>& visited)
{
cout << srci << ":" << _vertexs[srci] << endl;
visited[srci] = true;
for (size_t i = 0; i < _vertexs.size(); ++i)
{
if (_matrix[srci][i] != MAX_W && visited[i] == false)
{
_DFS(i, visited);
}
}
}
void DFS(const V& src)
{
size_t srci = GetVertexIndex(src);
vector<bool> visited(_vertexs.size(), false);
_DFS(srci, visited);
}
struct Edge
{
size_t _srci;
size_t _dsti;
W _w;
Edge(size_t srci, size_t dsti, const W& w)
:_srci(srci)
, _dsti(dsti)
, _w(w)
{}
bool operator>(const Edge& e)const
{
return _w > e._w;
}
};
W Kruskal(Self& minTree)
{
size_t n = _vertexs.size();
minTree._vertexs = _vertexs;
minTree._indexMap = _indexMap;
minTree._matrix.resize(n);
for (size_t i = 0; i < n; ++i)
{
minTree._matrix[i].resize(n, MAX_W);
}
priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
if (i < j && _matrix[i][j] != MAX_W)
{
minque.push(Edge(i, j, _matrix[i][j]));
}
}
}
// 选出n-1条边
int size = 0;
W totalW = W();
UnionFindSet ufs(n);
while (!minque.empty())
{
Edge min = minque.top();
minque.pop();
if (!ufs.InSet(min._srci,min._dsti)) // 判断是否构成环
{
cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
minTree.AddEdge(min._srci, min._dsti, min._w);
ufs.Union(min._srci, min._dsti);
++size;
totalW += min._w;
}
else
{
cout << "构成环: ";
cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
}
}
if (size == n - 1)
{
return totalW;
}
else
{
return W(); // 说明不能生成一棵树
}
}
private:
vector<V> _vertexs; // 顶点集合
map<V, int> _indexMap;// 顶点映射下标
vector<vector<W>> _matrix; // 邻接矩阵
};
void TestBDFS()
{
string a[] = { "张三", "李四", "王五", "赵六", "周七" };
Graph<string, int> g1(a, sizeof(a) / sizeof(string));
g1.AddEdge("张三", "李四", 100);
g1.AddEdge("张三", "王五", 200);
g1.AddEdge("王五", "赵六", 30);
g1.AddEdge("王五", "周七", 30);
g1.Print();
g1.BFS("张三");
g1.DFS("张三");
}
void TestGraphMinTree()
{
const char str[] = "abcdefghi";
Graph<char, int> g(str, strlen(str));
g.AddEdge('a', 'b', 4);
g.AddEdge('a', 'h', 8);
//g.AddEdge('a', 'h', 9);
g.AddEdge('b', 'c', 8);
g.AddEdge('b', 'h', 11);
g.AddEdge('c', 'i', 2);
g.AddEdge('c', 'f', 4);
g.AddEdge('c', 'd', 7);
g.AddEdge('d', 'f', 14);
g.AddEdge('d', 'e', 9);
g.AddEdge('e', 'f', 10);
g.AddEdge('f', 'g', 2);
g.AddEdge('g', 'h', 1);
g.AddEdge('g', 'i', 6);
g.AddEdge('h', 'i', 7);
Graph<char, int> kminTree;
cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
kminTree.Print();
cout << endl << endl;
Graph<char, int> pminTree;
cout << "Prim:" << g.Prim(pminTree, 'a') << endl;
pminTree.Print();
cout << endl;
for (size_t i = 0; i < strlen(str); ++i) // 测试不同从不同源点使用Prim算法结果是否相同
{
cout << "Prim:" << g.Prim(pminTree, str[i]) << endl;
}
}
}这个邻接矩阵的设计就是先把顶点都传入，先构造顶点和编号的映射关系，然后再手动的添加顶点之间边的关系及这个边的权值。
Prim算法
kruskal算法是每次直接找权值最小的边，直到能生成一个树，这样的问题就是可能会生成环。
而Prim算法就是专门针对了会生成环这个问题，因为一样也需要将边放到堆中以便每次能选出权值最小的边，Prim算法将顶点分成了两个集合，一个集合里放着已经是树的顶点了，另一个集合放着尚未成为树的顶点，每次从已经生成树集合里面的顶点选边，如果这个边是与已经是树的顶点连接的，那么肯定会成环，所以就不选。这样一来就可以达到避免生成环的效果，选完之后再将这个顶点转移到放着已经是树的顶点集合中，直到堆中的数据为空。所以本策略也是贪心策略。
示意图：
代码实现依旧是使用邻接矩阵，并且是对上一个代码的补充，在同一个类中。
并且，用来表示顶点的集合其实用一个bool数组就可以都标识了。并且与kruskal算法不同的是，我们可以传入一个源点，可以从任意一个点开始生成树。
W Prim(Self& minTree, const V& src)
{
size_t srci = GetVertexIndex(src);
size_t n = _vertexs.size();
minTree._vertexs = _vertexs;
minTree._indexMap = _indexMap;
minTree._matrix.resize(n);
for (size_t i = 0; i < n; ++i)
{
minTree._matrix[i].resize(n, MAX_W);
}
vector<bool> X(n, false); // 其实用一个数组即可完成
X[srci] = true;
// 先把srci的边放入堆中，kruskal是直接全放入堆中
priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
for (size_t i = 0; i < n; ++i)
{
if (_matrix[srci][i] != MAX_W)
{
minq.push(Edge(srci, i, _matrix[srci][i]));
}
}
cout << "Prim Start!" << endl;
size_t size = 0;
W totalW = W();
while (!minq.empty())
{
Edge min = minq.top();
minq.pop();
if (X[min._dsti]) // 如果最小边的目标点也在X集合，则会构成环
{
cout << "构成环:";
cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
}
else
{
minTree._AddEdge(min._srci, min._dsti, min._w);
X[min._dsti] = true; // 记得更新X集合
++size;
totalW += min._w;
if (size == n - 1)
break;
//记得更新下一次需要用到的边
for (size_t i = 0; i < n; ++i)
{
if (_matrix[min._dsti][i] != MAX_W)
{
minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
}
}
}
}
if (size == n - 1)
{
return totalW;
}
else
{
return W();
}
}两个算法的优缺点
Kruskal算法的优点：
- 适用于稀疏图：Kruskal算法在边的数量相对较少的情况下效率较高，因此在稀疏图中表现较好。
- 简单易实现：Kruskal算法的实现相对简单，只需要对边进行排序，然后依次选择权值最小的边加入最小生成树即可。
Kruskal算法的缺点：
- 需要排序：Kruskal算法需要对所有的边进行排序，因此在边的数量较多时，排序的时间复杂度较高。
- 需要并查集：Kruskal算法需要使用并查集来判断选择的边是否形成环路，这增加了算法的复杂度。
Prim算法的优点：
- 适用于稠密图：Prim算法在顶点的数量相对较多而边的数量相对较少的情况下效率较高，因此在稠密图中表现较好。
- 使用邻接表方便：Prim算法使用邻接表来表示图时，可以方便地进行顶点的选择和距离的更新。
Prim算法的缺点：
- 需要选择顶点：Prim算法每次需要选择距离当前生成树最近的顶点，这需要遍历所有的顶点来找到最近的顶点，增加了算法的时间复杂度。
- 可能产生不唯一的解：在某些情况下，Prim算法可能会产生不唯一的最小生成树。
综上所述，Kruskal算法和Prim算法各有优劣，选择哪种算法取决于具体的应用场景和图的特性。在稀疏图中，Kruskal算法可能更为适合；而在稠密图中，Prim算法可能更有优势。
最短路径
图最难，也是最后一个学习的部分就是最短路径问题了，就是找到最短路径。有Dijkstra算法和Bellman-ford算法，是解决单源最短路径的，Floyd-Warshall是解决多源最短路径问题的。
Dijkstra算法
Dijkstra算法是一种用于解决单源最短路径问题的贪心算法，由荷兰计算机科学家狄克斯特拉于1959年提出。该算法采用广度优先搜索的思想，从起始点开始，逐步扩展到其他顶点，直到找到从起始点到所有其他顶点的最短路径。
它的思路跟Prim算法有点想，也是用两个集合A，B对顶点进行标记。首先是初始化，将所有顶点的值比如可以初始化成无穷大，源点的值可以初始化成0，毕竟自己走到自己的花费一般都是0。然后根据边的权值更新从这个顶点出发到目标点的权值（这个顶点要满足不在A集合在B集合的条件），然后取最小的一个点作为下一次的起点，并放入A集合中，以此不断更新。这也是贪心策略
另外记得要把路径记录下来，也可以使用数组来记录。
代码，同样要给一个源点外，我们可以通过输出型参数的方式把结果带出去。
// 因为我们存的pPath是从子找源点，打印的时候我们需要将其倒过来
void PrintShortPath(const V& src, const vector<W>& dist, const vector<int>& pPath)
{
size_t srci = GetVertexIndex(src);
size_t n = _vertexs.size();
for (size_t i = 0; i < n; ++i)
{
if (i != srci)
{
// 找出i顶点的路径
vector<int> path;
size_t parenti = i;
while (parenti != srci)
{
path.push_back(parenti);
parenti = pPath[parenti];
}
path.push_back(srci);
reverse(path.begin(), path.end()); // 逆置过来
for (auto index : path)
{
cout << _vertexs[index] << "->";
}
cout << "# 权值和为:" << dist[i] << endl;
}
}
}
void Dijkstra(const V& src,vector<W>& dist,vector<int>& pPath)
{
size_t srci = GetVertexIndex(src);
size_t n = _vertexs.size();
dist.resize(n, MAX_W);
pPath.resize(n, -1); // 用这个来储存路径，其原理很像并查集,每个编号存自己的父节点以此来找到源点
dist[srci] = 0; // 源点要初始成0
pPath[srci] = srci; // 路径集合也要特殊处理
//已经确定最短路径的顶点集合
vector<bool> S(n, false);
for (size_t j = 0; j < n; ++j)
{
// 选最短路径顶点，且不在S。 还要更新其他路径
int u = 0; // 当前路径最短的顶点
W min = MAX_W;
for (size_t i = 0; i < n; ++i)
{
if (S[i] == false && dist[i] < min)
{
u = i;
min = dist[i];
}
}
S[u] = true;
//如果不在最短路径的顶点的权值出现了更低的值，需要更新成最低的，同时也要更新这个u->v的路径。
for (size_t v = 0; v < n; ++v)
{
if (S[v] == false && _matrix[u][v] != MAX_W
&& dist[u] + _matrix[u][v] < dist[v])
{
dist[v] = dist[u] + _matrix[u][v];
pPath[v] = u;
}
}
}
}
// 补充测试函数，放在类外，命名空间内
void TestGraphDijkstra()
{
const char* str = "syztx";
Graph<char, int, INT_MAX, true> g(str, strlen(str));
g.AddEdge('s', 't', 10);
g.AddEdge('s', 'y', 5);
g.AddEdge('y', 't', 3);
g.AddEdge('y', 'x', 9);
g.AddEdge('y', 'z', 2);
g.AddEdge('z', 's', 7);
g.AddEdge('z', 'x', 6);
g.AddEdge('t', 'y', 2);
g.AddEdge('t', 'x', 1);
g.AddEdge('x', 'z', 4);
vector<int> dist;
vector<int> parentPath;
g.Dijkstra('s', dist, parentPath);
g.PrintShortPath('s', dist, parentPath);
// 图中带有负权路径时，贪心策略则失效了。
// 测试结果可以看到s->t->y之间的最短路径没更新出来
/*const char* str = "sytx";
Graph<char, int, INT_MAX, true> g(str, strlen(str));
g.AddEdge('s', 't', 10);
g.AddEdge('s', 'y', 5);
g.AddEdge('t', 'y', -7);
g.AddEdge('y', 'x', 3);
vector<int> dist;
vector<int> parentPath;
g.Dijkstra('s', dist, parentPath);
g.PrintShortPath('s', dist, parentPath);*/
}
}运行结果可以对照：
但是Dijkstra算法不能支持带负权路径的图，这样会使算法失效，算出错误的结果。
因为我们自习想想这个贪心策略，它是在我们选到这个结点后，不可能再会有到这个结点更小的路径的结果的基础上进行的，如果存在负权，那么这个条件就不一定满足。它每次是以最短路径去更新的。
Dijkstra算法的时间复杂度为O（N^2），空间复杂度为O(N)。
Bellman-Ford算法
Dijkstra算法的优点就是效率高，但是存在如果有负权就失效的缺点。Bellman-Ford算法解决了不能计算负权的缺点，但是这是在牺牲效率的前提下。Bellman-Ford算法它采取的是一种暴力的搜索方式， 因此时间复杂度是O(N^3)，空间复杂度也是O(N)。
代码
bool BellmanFord(const V& src,vector<W>&dist, vector<int>&pPath)
{
size_t n = _vertexs.size();
size_t srci = GetVertexIndex(src);
dist.resize(n, MAX_W);
pPath.resize(n, -1);
dist[srci] = W();
for (size_t k = 0; k < n; ++k)
{
bool update = false; // 一个小优化，如果次轮已经没有更新，那么就可以直接退出了
cout << "更新第：" << k << "轮" << endl;
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
{
update = true;
cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _matrix[i][j] << endl;
dist[j] = dist[i] + _matrix[i][j];
pPath[j] = i;
}
}
}
if (update == false)
{
break;
}
}
// 如果还能更新说明存在负权回路
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
{
return false;
}
}
}
return true;
}
//补充同理
void TestGraphBellmanFord()
{
const char* str = "syztx";
Graph<char, int, INT_MAX, true> g(str, strlen(str));
g.AddEdge('s', 't', 6);
g.AddEdge('s', 'y', 7);
g.AddEdge('y', 'z', 9);
g.AddEdge('y', 'x', -3);
g.AddEdge('z', 's', 2);
g.AddEdge('z', 'x', 7);
g.AddEdge('t', 'x', 5);
g.AddEdge('t', 'y', 8);
g.AddEdge('t', 'z', -4);
g.AddEdge('x', 't', -2);
vector<int> dist;
vector<int> parentPath;
g.BellmanFord('s', dist, parentPath);
g.PrintShortPath('s', dist, parentPath);
//const char* str = "syztx";
//Graph<char, int, INT_MAX, true> g(str, strlen(str));
//g.AddEdge('s', 't', 6);
//g.AddEdge('s', 'y', 7);
//g.AddEdge('y', 'z', 9);
//g.AddEdge('y', 'x', -3);
g.AddEdge('y', 's', 1); // 新增
//g.AddEdge('z', 's', 2);
//g.AddEdge('z', 'x', 7);
//g.AddEdge('t', 'x', 5);
g.AddEdge('t', 'y', -8); //更改
//g.AddEdge('t', 'y', 8);
//g.AddEdge('t', 'z', -4);
//g.AddEdge('x', 't', -2);
//vector<int> dist;
//vector<int> parentPath;
//if (g.BellmanFord('s', dist, parentPath))
// g.PrintShortPath('s', dist, parentPath);
//else
// cout << "带负权回路" << endl;
}测试结果参考此图
看代码就知道，这个算法的时间其实很简单，直接三层循环。为什么要更新n次呢？比如更新第一次的时候，每更新一个新的更小路径，就有可能影响到之前已经更新过的路径，因此需要再更新一次，同理这次更新还有可能又会影响到其他的路径，最坏的情况下要更新n次。
在这个代码中我们还进行了一个小优化，那就是如果此次循环并没更新新的路径，那么就退出。
还有一个优化思想就是，除了第一次更新，往后所有的更新我们只需要更新那些被后面更新影响到的路径即可，不需要所有路径都再更新一次。
另外我们发现Bellman-Ford是有返回值的，这是为了判断这个图中是否有存在负权回路。负权回路就是从源点出发，更新一圈后发现源点到源点的值居然变小了也就是变成负数了，并且每一次更新都会变得更小。
为什么Dijkstra算法不担心呢？因为它连负权都解决不了。
并且负权回路问题不是算法能解决的，是问题本身出了问题。
Floyd-Warshall算法
这个算法不同于之前两个算法，之前两个算法是解决单源最短路径的，而Floyd-Warshall算法是解决多源最短路径问题的。也就是能求出任意两个点之间的最短路径。这个算法也是这三个算法中最抽象的，并且Floyd-Warshall用的动态规划的思想。
设k是p的一个中间节点，那么从i到j的最短路径p就被分成i到k和k到j的两段最短路径p1，p2。p1
是从i到k且中间节点属于{1，2，…，k-1}取得的一条最短路径。p2是从k到j且中间节点属于{1，
2，…，k-1}取得的一条最短路径。
代码：
void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath)
{
size_t n = _vertexs.size();
vvDist.resize(n);
vvpPath.resize(n);
// 初始化权值和路径矩阵
for (size_t i = 0; i < n; ++i)
{
vvDist[i].resize(n, MAX_W);
vvpPath[i].resize(n, -1);
}
// 直接相连的边更新一下
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;
}
if (i == j)
{
vvDist[i][j] = W();
}
}
}
// 为什么不是n - 2呢，因为 a -> b, 和c -> d，虽然需要遍历的最大次数同时n - 2，但是结果却不同
for (size_t k = 0; k < n; ++k)
{
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
// 这里的k是作为中间结点去更新i->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];
// 注意下面关于路径的更新
// 是找j相连的上一个邻接顶点
// 如果k->j 直接相连，那么j的上一个就是k，所以vvpPath[k][j]存的就是k
// 如果k->j 没有直接相连，比如 k->...->x->j,那么vvpPath[k][j]存的就是x
vvpPath[i][j] = vvpPath[k][j];
}
}
}
}
// 打印权值和路径矩阵来观察数据
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
if (vvDist[i][j] == MAX_W)
{
printf("%3c", '#');
}
else
{
printf("%3d", vvDist[i][j]);
}
}
cout << endl;
}
cout << endl;
// 再打印路径图
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
printf("%3d", vvpPath[i][j]);
}
cout << endl;
}
cout << "======================================" << endl;
}
// 补充同理
void TestFloydWarShall()
{
const char* str = "12345";
Graph<char, int, INT_MAX, true> g(str, strlen(str));
g.AddEdge('1', '2', 3);
g.AddEdge('1', '3', 8);
g.AddEdge('1', '5', -4);
g.AddEdge('2', '4', 1);
g.AddEdge('2', '5', 7);
g.AddEdge('3', '2', 4);
g.AddEdge('4', '1', 2);
g.AddEdge('4', '3', -5);
g.AddEdge('5', '4', 6);
vector<vector<int>> vvDist;
vector<vector<int>> vvParentPath;
g.FloydWarshall(vvDist, vvParentPath);
// 打印任意两点之间的最短路径
for (size_t i = 0; i < strlen(str); ++i)
{
g.PrintShortPath(str[i], vvDist[i], vvParentPath[i]);
cout << endl;
}
}
结果参考图
Floyd-Warshall算法的时间复杂度为O(N^3)，空间复杂度为O(N^2)。
其实找任意两个结点的最短路径Dijkstra和Bellman-Ford算法也可以做到，无非就是再套一层循环，Dijkstra再套一层循环时间复杂度是O(N^3)，效率跟Floyd-Warshall是一样的，但是无法解决负权问题，Bellman-Ford再套一层就O(N^4)，效率就太低了。
