完成代码仓库：https://gitee.com/tgwTTT/data-structure/tree/master/Gragh1
图（Graph）是数据结构中非常重要的一类，广泛应用于网络、地图、社交关系等场景。本文结合实际代码，介绍如何用 C++ 实现图及其操作
一、邻接矩阵实现
邻接矩阵用一个二维数组存储顶点之间的边权。适合稠密图，查找和修改边权方便。
1. 顶点和边的存储
顶点用 _vertexs 数组保存，顶点到下标的映射用_indexMap 实现。边权用 _martix二维数组保存。
vector _vertexs; // 顶点集合
vector> _matrix; // 邻接矩阵
map _indexMap; // 顶点到下标的映射 2. 添加边
通过顶点名查找下标，然后设置矩阵对应位置的权值。无向图需对称赋值。
void AddEdge(const V& src, const V& dst, const W& w) {
size_t i = GetVertexIndex(src);
size_t j = GetVertexIndex(dst);
_matrix[i][j] = w;
if (!Direction) _matrix[j][i] = w; // 无向图
}- 图的遍历
以广度优先遍历（BFS）为例，利用队列和访问标记数组实现：
void BFS(const V& src) {
size_t i = GetVertexIndex(src);
queue q;
vector visit(_vertexs.size(), false);
q.push(i); visit[i] = true;
while (!q.empty()) {
int front = q.front(); q.pop();
cout << _vertexs[front] << " ";
for (int j = 0; j < _matrix[front].size(); j++) {
if (_matrix[front][j] != INT_MAX && !visit[j]) {
q.push(j); visit[j] = true;
}
}
}
} 二、邻接表实现
邻接表适合稀疏图，空间效率高。每个顶点维护一个链表，存储所有相邻边。
1. 结构设计
每个顶点对应一个链表头指针，链表节点保存目标顶点下标和权值。
struct Edge {
int _dsci; // 目标顶点下标
W _w; // 权值
Edge* _next; // 下一个边
};
vector _tables; // 邻接表 2. 添加边
插入链表头部，若为无向图则对称插入。
void AddEdge(const V& src, const V& dst, const W& w) {
size_t i = GetVertexIndex(src);
size_t j = GetVertexIndex(dst);
Edge *eg = new Edge(j, w);
eg->_next = _tables[i];
_tables[i] = eg;
if (!Direction) {
Edge *eg2 = new Edge(i, w);
eg2->_next = _tables[j];
_tables[j] = eg2;
}
}3. 遍历算法
邻接表的 BFS 和 DFS 只需遍历链表即可：
void BFS(const V& src) {
size_t i = GetVertexIndex(src);
queue q;
vector visit(_vertexs.size(), false);
q.push(i); visit[i] = true;
while (!q.empty()) {
int front = q.front(); q.pop();
cout << _vertexs[front] << " ";
Edge* vt = _tables[front];
while (vt) {
if (!visit[vt->_dsci]) {
q.push(vt->_dsci); visit[vt->_dsci] = true;
}
vt = vt->_next;
}
}
} 最小生成树：
以邻接矩阵为例：
1. Kruskal算法
核心思路：先把所有边按权值从小到大排序，然后用并查集判断是否形成环，逐步选取最小边，直到所有顶点连通。
1. 所有边入优先队列（小顶堆）
2. 并查集判断是否成环
3. 选边加入最小生成树
4. 直到选够 n-1 条边
W Kruskal(Self& minTree) const
{
const size_t n = _vertexs.size();
if (n == 0) return W();
std::priority_queue,
std::greater> minq;
for (size_t i = 0; i < n; ++i)
for (size_t j = 0; j < n; ++j)
if (i < j && _matrix[i][j] != MAX_W)
minq.emplace(i, j, _matrix[i][j]);
std::vector ufs(n, -1);
auto find = [&ufs](int x)
{
while (ufs[x] >= 0) x = ufs[x];
return x;
};
W totalW = W();
size_t cnt = 0;
while (!minq.empty() && cnt < n - 1)
{
Edge e = minq.top(); minq.pop();
int r1 = find(static_cast(e._srci));
int r2 = find(static_cast(e._dsti));
if (r1 != r2)
{
if (ufs[r1] > ufs[r2]) std::swap(r1, r2);
ufs[r1] += ufs[r2];
ufs[r2] = r1;
minTree._AddEdge(e._srci, e._dsti, e._w);
totalW += e._w;
++cnt;
}
}
return cnt == n - 1 ? totalW : W(); 0
} 2. Prim算法
核心思路：从一个顶点出发，每次选取连接到已选集合的最小权值边，直到所有顶点都被覆盖。
1. 用集合 x 记录已选顶点，y 记录未选顶点
2. 每次从 x 到 y 的边选最小权值
3. 加入最小生成树
W Prime(Self&minTree,const V&src)
{
size_t srci = GetVertexIndex(src);
size_t n = _vertexs.size();
minTree._indexMap = this->_indexMap;
minTree._vertexs = this->_vertexs;
minTree._matrix.resize(n);
for (int i = 0; i < n; i++) {
minTree._matrix[i].resize(n, MAX_W);
}
setx;
sety;
x.insert(srci);
for (int i = 0; i < n; i++) {
if (i != srci)y.insert(i);
}
priority_queue, greater>minq;
for (int i = 0; i < n; i++) {
if (_matrix[srci][i] != MAX_W) {
minq.push(Edge(srci, i, _matrix[srci][i]));
}
}
size_t k= 0;
W totalw = W();
while (!minq.empty()) {
Edge min = minq.top();
minq.pop();
if (x.count(min._dsti) == 1 && x.count(min._srci) == 1) {
continue;
}
minTree._AddEdge(min._srci, min._dsti, min._w);
x.insert(min._dsti);
y.erase(min._dsti);
k++;
totalw += min._w;
if (k == n - 1)break;
for (int i = 0; i < n; i++) {
if (_matrix[min._dsti][i] != MAX_W&&x.count(i)==0) {
minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
}
}
}
if (k == n - 1) {
return totalw;
}
else {
return W();
}
} 最短路径实现
1. Dijkstra算法
核心思路：每次选取未访问顶点中距离源点最近的顶点，更新其邻居的最短距离，直到所有顶点都被访问。
1. 初始化 dist 和 parentPath
2. 每次选最近的顶点 u
3. 用 u 更新所有邻居的距离
void Dijkstra(const V& src, vector& dist, vector& parentPath)
{
size_t N = _vertexs.size();
size_t srci = GetVertexIndex(src);
dist.resize(N, MAX_W);
parentPath.resize(N, -1);
vector S;
S.resize(N, false);
dist[srci] = W()；
for (size_t i = 0; i < N; ++i)
{
W min = MAX_W;
size_t u = srci;
for (size_t j = 0; j < N; ++j)
{
if (S[j] == false && dist[j] < min)
{
min = dist[j];
u = j;
}
}
S[u] = true;
for (size_t k = 0; k < N; ++k)
{
if (S[k] == false && _matrix[u][k] != MAX_W
&& dist[u] + _matrix[u][k] < dist[k])
{
dist[k] = dist[u] + _matrix[u][k];
parentPath[k] = u;
}
}
}
} 3. Floyd-Warshall算法
核心思路：三重循环，枚举所有顶点对，尝试用每个顶点作为中转点更新最短路径。
1. 初始化所有顶点对的距离
2. 枚举中转点 k，尝试更新 i 到 j 的最短路径
void FloydWarShall(vector>& vvDist, vector>&
vvParentPath)
{
size_t N = _vertexs.size();
vvDist.resize(N);
vvParentPath.resize(N);
for (size_t i = 0; i < N; ++i)
{
vvDist[i].resize(N, MAX_W);
vvParentPath[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];
vvParentPath[i][j] = i;
}
else
{
vvParentPath[i][j] = -1;
}
if (i == j)
{
vvDist[i][j] = 0;
vvParentPath[i][j] = -1;
}
}
}
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];
vvParentPath[i][j] = vvParentPath[k][j];
}
}
}
//for (size_t i = 0; i < N; ++i)
//{
// for (size_t j = 0; j < N; ++j)
// {
// if (vvDist[i][j] == MAX_W)
// {
// //cout << "*" << " ";
// printf("%3c", '*');
// }
// else
// {
// //cout << vvDist[i][j] << " ";
// 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)
// {
// //cout << vvParentPath[i][j] << " ";
// printf("%3d", vvParentPath[i][j]);
// }
// cout << endl;
//}
//cout << "=================================" << endl;
}
} 今天的更新就到这里了，如有错误欢迎评论区指出
评论
还没有任何评论，你来说两句吧!