Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！
我的博客：<但凡.
我的专栏：《编程之路》、《数据结构与算法之美》、《题海拾贝》、《C++修炼之路》
欢迎点赞，关注！
目录
1、什么是图
1.1、图的基本概念
图（Graph）是一种数据结构，由节点（Vertex）和边（Edge）组成，用于表示实体之间的关系。节点代表实体，边表示实体之间的连接或交互。图的数学定义为：
[ G = (V, E) ]
其中，( V ) 是节点集合，( E ) 是边集合。
1.2、图的类型
- 无向图
边没有方向性，表示双向关系。例如社交网络中的好友关系。 - 有向图
边有方向性，表示单向关系。如网页之间的超链接。 - 加权图
边带有权重，表示关系的强度或成本。如地图中的路径距离。 - 无权图
边无权重，仅表示连接关系。
1.3、图的表示方法
邻接矩阵
用二维数组表示节点间的连接关系。矩阵元素 ( A[i][j] ) 表示节点 ( i ) 和 ( j ) 是否相连。- 无向图的邻接矩阵对称。
- 适合稠密图（边较多）。
邻接表
节省空间，适合稀疏图（边较少）。
每个节点维护一个链表，存储与其直接相连的节点。
1.4、图的应用场景
- 社交网络分析
节点代表用户，边代表好友关系。 - 路径规划
如导航系统中的最短路径计算（Dijkstra算法）。 - 推荐系统
通过用户-商品二分图挖掘关联规则。 - 知识图谱
用有向图表示实体间的语义关系。
1.5、图的常见算法
- 遍历算法
- 深度优先搜索（DFS）
- 广度优先搜索（BFS）
- 最短路径算法
- Dijkstra（非负权重）
- Bellman-Ford（含负权重）
- SPFA(升级版Bellman-Ford)
- 最小生成树算法
- Kruskal
- Prim
图的理论与实践结合紧密，是计算机科学中解决复杂问题的核心工具之一。
1.6、图的相关概念
度（Degree）：无向图中与顶点相连的边数。有向图中分为入度（In-Degree）和出度（Out-Degree）。
路径（Path）：顶点序列，通过边依次连接。简单路径不重复经过顶点。
环（Cycle）：起点和终点相同的路径。有向图中称为有向环。
连通性（Connectivity）：无向图中任意两顶点间存在路径则为连通图。有向图中强连通指双向可达。
子图（Subgraph）：顶点和边均为原图子集的图。
2、建图
2.1、邻接矩阵
主要成员变量包含_vIndexMap,_vertexs,_matrix。其中，_vIndexMap是存储每个顶点在邻接矩阵中的映射值，_vertexs存储所有的顶点，_matrix是存储图的矩阵。
图的类默认是无向图，如果两点之间没有路，我们就把这两点在邻接矩阵中的值设置为INT_MAX。
我们使用成员函数GetVertexIndex获得某个顶点的映射值，使用成员函数AddEdge和_AddEdge来在邻接矩阵中添加边。
namespace Matrix
{
// 顶点 权重
template<class V,class W,W MAX_W=INT_MAX,bool Direction=false>
class Graph
{
public:
struct Edge//边
{
V _srci;
V _dsti;
W _w;
Edge(const V& srci,const V& dsti,const W& w)
:_srci(srci)
,_dsti(dsti)
,_w(w)
{}
bool operator<(const Edge& eg) const
{
return _w < eg._w;
}
bool operator>(const Edge& eg) const
{
return _w > eg._w;
}
};
typedef Graph<V, W, MAX_W, Direction> Self;
Graph() = default;//生成一个默认构造
Graph(const V* vertexs, size_t n)
{
_vertexs.reserve(n);
for (size_t i = 0;i < n;i++)
{
_vertexs.push_back(vertexs[i]);
_vIndexMap[vertexs[i]] = i;
}
//MAX_W作为不存在边的标识值
_matrix.resize(n);
for (auto& e : _matrix)
{
e.resize(n, MAX_W);
}
}
size_t GetVertexIndex(const V& v)
{
auto ret = _vIndexMap.find(v);
if (ret != _vIndexMap.end())
{
return ret->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& det, const W& w)
{
size_t srci = GetVertexIndex(src);
size_t dsti = GetVertexIndex(det);
_AddEdge(srci, dsti, w);
}
private:
map<V, size_t> _vIndexMap;
vector<V> _vertexs;//顶点集合
vector<vector<W>> _matrix;//存储边集合的矩阵
};
}2.2、邻接表
邻接表也有三个成员变量，分别是_vertexs，_indexMap，_tables。_vertexs是顶点集合，_indexMap记录顶点的映射下标，_tables是邻接表。
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(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;//邻接表
};
}接下来我们各种有关图的算法都使用邻接矩阵的图实现。
3、遍历
3.1、BFS
我们给定遍历开始的起点，然后按照BFS算法，依次遍历每一层节点。
我们根据图来理解一下，首先左上角的节点是起点，第一次，我们是把和起点相连的节点加入到队列中，接着我们设置好dsize，第二次遍历的时候就会把第一层的两个节点取出，然后我们再把和第一层相连的几个节点加入到队列中，第三层就是把和第二层相连的节点加入到队列中。
void BFS(const V& src)
{
size_t srcindex = GetVertexIndex(src);
vector<bool> visited;
visited.resize(_vertexs.size(), false);
queue<int> q;
q.push(srcindex);
visited[srcindex] = true;
size_t d = 1;
size_t dSize = 1;
while (!q.empty())
{
printf("%s的%d度好友：",src.c_str(), d);//其实就是从src开始第几层好友
while (dSize--)
{
size_t front = q.front();
q.pop();
for (size_t i = 0;i < _vertexs.size();i++)
{
if (visited[i] == false && _matrix[front][i] != MAX_W)
{
printf("[%d:%s]", i, _vertexs[i].c_str());
visited[i] = true;
q.push(i);
}
}
}
cout << endl;
dSize = q.size();
++d;
}
cout << endl;
}3.2、DFS
注意我这里写的dfs只使用于存储值为字符串的，其他版本的大家自己改一下就好了。
对于bfs来说，我们可以理解为能走就走，走不了就回退。
void _DFS(size_t srcIndex, vector<bool>& visited)
{
printf("[%d:%s]->", srcIndex, _vertexs[srcIndex].c_str());
visited[srcIndex] = true;
for (size_t i = 0;i < _vertexs.size();i++)
{
if (visited[i] == false && _matrix[srcIndex][i] != MAX_W)
{
_DFS(i, visited);
}
}
}
void DFS(const V& src)
{
size_t srcindex = GetVertexIndex(src);
vector<bool> visited;
visited.resize(_vertexs.size(), false);
_DFS(srcindex, visited);
cout << endl;
}4、最小生成树
最小生成树（Minimum Spanning Tree，MST）是指在一个带权无向连通图（注意一定是连通图）中，选取一棵包含所有顶点的树，且树的边权值之和最小。它满足以下条件：
- 包含图中所有顶点。
- 是原图的子图且无环（即为一棵树）。
- 所有边的权值总和最小。
常见的最小生成树算法
Kruskal算法
基于贪心策略，按边权从小到大排序，依次选择不形成环的边，直到覆盖所有顶点。适合稀疏图。
Prim算法
从一个顶点出发，逐步选择与当前树相连的最小权边，扩展树直至覆盖所有顶点。适合稠密图。
接下来我们实现以下这两种算法：
4.1、Kruskal
我在这里实现的kruskal算法运用了并查集，大家可以看我上一期文章来实现并查集。
kruskal我们可以理解为全局贪心，我们直接把所有边都加入到堆中，接着，依次取出堆中的每个边，如果这个边中的起点和终点不存在一个并查集中，说明这个边是合法的，我们把这个边加入到最小生成树中。直到取出n-1条边，其中n是节点的个数。
我们结合图来理解一下：
kruskal算法的时间复杂度为O(n logn)，另外，我这里的kruskal算法是使用堆实现的，如果使用库中自带的sort效率会略低一些，因为我们要考虑到，有一部分边我们不需要排序他们，也就是说大部分情况下，我们不需要拿出所有的边才能生成这个最小生成树，对于权重较大的边我们不需要排序。
kruskal算法适用于稀疏图，在稠密图中，排序阶段可能成为性能瓶颈。若边数接近顶点平方，采用Prim算法（基于优先队列）可能更高效。
W Kruskal(Self& minTree)
{
//全局贪心
minTree._vertexs = _vertexs;
minTree._vIndexMap = _vIndexMap;
minTree._matrix.resize(_vertexs.size());
for (auto& e : minTree._matrix)
{
e.resize(_vertexs.size(), MAX_W);
}
//所有的边都先入堆
priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
for (size_t i = 0;i < _matrix.size();i++)
{
for (size_t j = 0;j < _matrix.size();j++)
{
if (i < j && _matrix[i][j] != MAX_W)
{
pq.push(Edge(i, j, _matrix[i][j]));
}
}
}
W total = W();
size_t i = 1;
UnionFindSet ufs(_vertexs.size());
while (i < _vertexs.size() && !pq.empty())
{
Edge min = pq.top();
pq.pop();
if (ufs.FindRoot(min._srci) != ufs.FindRoot(min._dsti))
{
minTree._AddEdge(min._srci, min._dsti, min._w);
total += min._w;
ufs.Union(min._srci, min._dsti);
++i;
}
}
if (i == _vertexs.size())
{
return total;
}
else
{
return W();//说明这个图不连通
}
}4.2、Prim
Prim算法是一种用于求解加权无向图最小生成树（Minimum Spanning Tree, MST）的贪心算法。该算法从任意顶点开始，逐步扩展生成树，每次选择连接生成树与非生成树顶点且权值最小的边，直至所有顶点都被包含在生成树中。Prim算法适合稠密图，时间复杂度为O()。
Prim算法我们可以理解为局部贪心。从起点开始，每次拿边都是拿以当前这个点为起点的边中权重最小的那个。同样，Prim算法的结束条件也是抽到n-1条边。在下面的代码实现中，我用X，Y两个数组作为标记数组，判断选取某个边是否会形成环。
对于最小生成树的两个算法来说，都是对边进行选择，而和顶点的标号没有关系。
W Prim(Self& minTree, const V& src)
{
size_t srci = GetVertexIndex(src);
size_t n = _vertexs.size();
minTree._vertexs = _vertexs;
minTree._vIndexMap = _vIndexMap;
minTree._matrix.resize(n);
for (size_t i = 0;i < _vertexs.size();i++)
{
minTree._matrix[i].resize(n, MAX_W);
}
vector<bool> X(n, false);
vector<bool> Y(n, true);
X[srci] = true;
Y[srci] = false;
priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
//先把srci链接的边添加到队列中
for (int i = 0;i < n;i++)
{
if (_matrix[srci][i] != MAX_W)
{
minq.push(Edge(srci, i, _matrix[srci][i]));
}
}
cout << "开始选边" << endl;
size_t size = 0;
W totalW = W();
while (!minq.empty())
{
Edge min = minq.top();
minq.pop();
if (X[min._dsti])
{
//这个边的末尾的节点已经作为开始节点选过了，所以成环，所以这个边不能要
}
else
{
minTree._AddEdge(min._srci, min._dsti, min._w);
cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
X[min._dsti] = true;
Y[min._dsti] = false;
++size;
totalW += min._w;
if (size == n - 1)
{
break;
}
//把这个节点为起点的边都加进堆
for (size_t i = 0;i < n;i++)
{
if (_matrix[min._dsti][i] != MAX_W && Y[i])
{
minq. push(Edge(min._dsti, i, _matrix[min._dsti][i]));
}
}
}
}
if (size == n - 1)
{
return totalW;
}
else
{
return W();
}
}5、单源最短路算法
单源最短路问题是指在加权图（有向或无向）中，从给定源点到其他所有顶点的最短路径问题。
单源最短路算法包含三个，Dijkstra算法，Bellman-Ford算法，spfa算法。
5.1、Dijkstra
Dijkstra算法适用于边权为非负的图。算法通过贪心策略逐步扩展最短路径树。注意，Dijkstra算法不实用于存在负权边的图。以下实现的Dijkstra时间复杂度为O()。
对于Dijkstra算法来说，每次我们确定一个顶点的最短路径，所以说最外层循环进行n轮。对于每轮循环，我们查找dist数组中的最小值，以这个最小值对应的节点为起点开始对周边节点进行更新。我们结合下图理解一下：
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;
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;
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;
}
}
}
}5.2、Bellman-Ford
Bellman-Ford算法是一种用于求解单源最短路径问题的算法，能够处理带有负权边的图。与Dijkstra算法不同，Bellman-Ford适用于存在负权边但无负权环的情况，并能检测图中是否存在负权环。以下算法的实现时间复杂度为O()。
通过松弛操作（Relaxation）逐步逼近最短路径。对于包含(V)个顶点和(E)条边的图，算法进行(V-1)轮松弛操作，每轮遍历所有边。若在第(V)轮仍能松弛，则说明存在负权环。所谓松弛操作，其实就是更新某一个节点的dist。我们最多经过n轮松弛操作，因为每轮松弛操作至少确定一个顶点的最短路径。如果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();
//最多进行n轮
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] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
{
update = true;
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]!=MAX_W&&dist[i] + _matrix[i][j] < dist[j])
{
return false;
}
}
}
return true;
}5.3、SPFA
SPFA（Shortest Path Faster Algorithm）是一种用于求解单源最短路径的算法，适用于带有负权边的图。它是Bellman-Ford算法的优化版本，通过动态调整队列结构减少冗余计算，从而提高效率。该算法平均时间复杂度为O(n)。
算法利用队列优化松弛操作。每次从队列中取出一个节点，对其邻接节点进行松弛操作。若邻接节点的距离被更新且不在队列中，则将其加入队列。重复这一过程直到队列为空。
其实SPFA算法的本质就是在bellman-ford的基础上，发现对于每轮更新来说，如果某一个节点上一轮没有变化，说明这个节点已经确定了，我们在当前轮就没必要更新他周围的边了。所以说对于松弛操作，我们就只需要把当前轮被改变的那个节点加入队列就好。倘若存在一个节点加入队列，移除队列这个操作循环了n次及以上，说明这个图有负环。
bool SPFA(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();
queue<size_t> q;
q.push(srci);
vector<bool> inQueue(n, false);
inQueue[srci] = true;
vector<size_t> count(n, 0); // 记录节点入队次数，用于检测负环
while (!q.empty()) {
size_t u = q.front();
q.pop();
inQueue[u] = false;
for (size_t v = 0; v < n; ++v) {
if (_matrix[u][v] != MAX_W && dist[u] != MAX_W && dist[u] + _matrix[u][v] < dist[v]) {
dist[v] = dist[u] + _matrix[u][v];
pPath[v] = u;
if (!inQueue[v]) {
q.push(v);
inQueue[v] = true;
count[v]++;
if (count[v] >= n) {
return false; // 存在负环
}
}
}
}
}
return true;
}6、多源最短路
这里就介绍一个Floyd算法。Floyd-Warshall算法是一种用于寻找加权图中所有顶点对之间最短路径的动态规划算法。该算法适用于有向图或无向图，可以处理负权边（但不允许存在负权回路）。其时间复杂度为O(N^3)，其中N是图中的顶点数。
我们看最主要的三轮循环，最外一层循环的k我们叫他中转点，也就是说，我们把每个点是中转点的情况都考虑一下，然后再遍历以这个点为中转点的所有情况，如果，从i到k的距离加从k到j的距离小于从i到j的距离，那么就更新dist。
这个就不画图了，太难画了。
void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath)
{
size_t n = _vertexs.size();
vvDist.resize(n);
vvpPath.resize(n);
//vvpPath设置的是到达j的前驱节点
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();
}
}
}
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];
}
}
}
}
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;
}以上就是我们需要掌握的和图有关的内容。需要注意的是，在以上的各种算法中我大多都是实现的朴素版本，或者说是传统版本。这些算法在其他的数据结构的优化下可能会有一些小提升，但是大体思路是不变的。 另外，在算法比赛中，无论是建图，还是各种算法，我们的代码量都会打一个折扣，因为以上代码是基于动态的图结构实现的。但是无论如何我们建图，各种算法的思想是不变的。
好了，今天的内容就分享到这，我们下期再见！