数据结构—图

图是在数据结构中难度比较大，并且比较抽象一种数据结构。

图在地图，社交网络这方面有应用。

图的基本概念

图是由顶点集合及顶点间的关系组成的一种数据结构：G=（V，E）。图标的英文：graph。

树是一种特殊的图（无环联通）。

图不一定是树。

树关注结点中存的值。 

图关注的是顶点及边的权值。

图的一些其他的概念：

图可以表示城市之间的关系，也还可以表示社交关系。比如顶点是人的话，那么边就是好友，边权值就是亲密度这些。像微信，qq这样的就是无向图，只要是好友，就可以双方互发和接收消息，那么这个也就是强社交关系。像抖音，微博这些，我们关注别人，但是别人没有关注我们，就只能单方面发送消息，而不能接收对方发来的消息，那么这个就是弱社交关系。

图的存储结构

邻接矩阵

我们发现无向图的矩阵沿着对角线对称，所以其实可以将矩阵压缩成一半，不过这样的就更加抽象复杂了。

有向图：

如果边带权值，那么我们可以在邻接矩阵中存权值，如果两个结点之间不连通，则可以用特殊数字代替，比如无穷大

 总结：

邻接矩阵有两个优点：

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算法的优点：

1. 适用于稀疏图：Kruskal算法在边的数量相对较少的情况下效率较高，因此在稀疏图中表现较好。
2. 简单易实现：Kruskal算法的实现相对简单，只需要对边进行排序，然后依次选择权值最小的边加入最小生成树即可。

Kruskal算法的缺点：

1. 需要排序：Kruskal算法需要对所有的边进行排序，因此在边的数量较多时，排序的时间复杂度较高。
2. 需要并查集：Kruskal算法需要使用并查集来判断选择的边是否形成环路，这增加了算法的复杂度。

Prim算法的优点：

1. 适用于稠密图：Prim算法在顶点的数量相对较多而边的数量相对较少的情况下效率较高，因此在稠密图中表现较好。
2. 使用邻接表方便：Prim算法使用邻接表来表示图时，可以方便地进行顶点的选择和距离的更新。

Prim算法的缺点：

1. 需要选择顶点：Prim算法每次需要选择距离当前生成树最近的顶点，这需要遍历所有的顶点来找到最近的顶点，增加了算法的时间复杂度。
2. 可能产生不唯一的解：在某些情况下，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用的动态规划的思想。

 

 代码：

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)，效率就太低了。

原文地址：https://blog.csdn.net/m0_74099572/article/details/136089636

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！