c++ 数据结构：图

图是一种重要的非线性数据结构，用于表示对象及其关系。它广泛应用于社交网络、交通网络、任务调度、导航等领域。

图的基本概念

图的定义： 图由 顶点（Vertex） 和 边（Edge） 组成，记为 G=(V,E)，其中：

• V 是顶点的集合。
• E 是边的集合，每条边连接两个顶点。

顶点和边的属性：

• 顶点（Vertex）：也称节点，表示数据项。
• 边（Edge）：连接两个顶点，表示它们之间的关系。
• 度（Degree）：
  • 入度（In-Degree）：指向某个顶点的边的数量。
  • 出度（Out-Degree）：从某个顶点发出的边的数量。

图的分类：

• 无向图（Undirected Graph）：边没有方向，表示双向关系。
• 有向图（Directed Graph）：边有方向，表示单向关系。
• 加权图（Weighted Graph）：边带有权重（如距离、费用）。
• 稀疏图（Sparse Graph）：边的数量远少于顶点的平方。
• 稠密图（Dense Graph）：边的数量接近顶点数的平方。
• 连通图（Connected Graph）：任意两顶点之间有路径相连。
• 无环图（Acyclic Graph）：没有环路的图。

特殊图：

• 树（Tree）：无环、连通、且具有 n个顶点和 n−1 条边。
• 完全图（Complete Graph）：每对顶点之间都有一条边。
• 二分图（Bipartite Graph）：顶点集可分为两个互不相交的子集，且边只连接不同子集的顶点。

图的存储表示

邻接矩阵

概念

• 使用二维数组表示图，适合稠密图。

• 实现方式：如果有边 (u,v)，则adj[u] [v] = 1;否则为0；

• 优点：

  • 快速查找是否存在边，时间复杂度 O(1)。

• 缺点：

  • 空间复杂度高，为 O(V^2)。

邻接矩阵表示无向图

#include <iostream>
#include <vector>using namespace std;class Graph {
private:int vertices;vector<vector<int>> adjMatrix;public:Graph(int V) : vertices(V), adjMatrix(V, vector<int>(V, 0)) {}void addEdge(int u, int v) {adjMatrix[u][v] = 1;adjMatrix[v][u] = 1; // 无向图}void printMatrix() {for (const auto& row : adjMatrix) {for (int val : row) {cout << val << " ";}cout << endl;}}
};int main() {Graph g(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 3);cout << "Adjacency Matrix:" << endl;g.printMatrix();return 0;
}

邻接表

概念

• 使用链表或向量表示每个顶点的邻接点，适合稀疏图。

• 实现方式：每个顶点存储其所有邻接顶点。

• 优点：

  • 节省空间，适合稀疏图，空间复杂度 O(V+E)。

• 缺点：

  • 查找边是否存在需要 O(邻接点数量)O(\text{邻接点数量})O(邻接点数量)。

邻接表表示无向图

#include <iostream>
#include <vector>using namespace std;class Graph {
private:int vertices;vector<vector<int>> adjList;public:Graph(int V) : vertices(V), adjList(V) {}void addEdge(int u, int v) {adjList[u].push_back(v);adjList[v].push_back(u); // 无向图}void printList() {for (int i = 0; i < vertices; ++i) {cout << "Vertex " << i << ":";for (int neighbor : adjList[i]) {cout << " " << neighbor;}cout << endl;}}
};int main() {Graph g(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 3);cout << "Adjacency List:" << endl;g.printList();return 0;
}

图的遍历

图的遍历是对图中所有顶点进行访问，常用方法有 深度优先搜索（DFS） 和 广度优先搜索（BFS）。

深度优先搜索（DFS）

• 类似树的先序遍历，沿着一条路径尽可能深地搜索。

• 使用递归或栈实现。

• 时间复杂度：O(V+E)。

#include <iostream>
#include <vector>using namespace std;class Graph {
private:int vertices;vector<vector<int>> adjList;vector<bool> visited;public:Graph(int V) : vertices(V), adjList(V), visited(V, false) {}void addEdge(int u, int v) {adjList[u].push_back(v);adjList[v].push_back(u); // 无向图}void DFS(int start) {visited[start] = true;cout << start << " ";for (int neighbor : adjList[start]) {if (!visited[neighbor]) {DFS(neighbor);}}}
};int main() {Graph g(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 3);cout << "DFS Traversal starting from vertex 0:" << endl;g.DFS(0);return 0;
}

广度优先搜索（BFS）

• 类似树的层序遍历，从起点逐层访问邻接点。

• 使用队列实现。

• 时间复杂度：O(V+E)。

#include <iostream>
#include <vector>
#include <queue>using namespace std;class Graph {
private:int vertices;vector<vector<int>> adjList;public:Graph(int V) : vertices(V), adjList(V) {}void addEdge(int u, int v) {adjList[u].push_back(v);adjList[v].push_back(u); // 无向图}void BFS(int start) {vector<bool> visited(vertices, false);queue<int> q;visited[start] = true;q.push(start);while (!q.empty()) {int current = q.front();q.pop();cout << current << " ";for (int neighbor : adjList[current]) {if (!visited[neighbor]) {visited[neighbor] = true;q.push(neighbor);}}}}
};int main() {Graph g(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 3);cout << "BFS Traversal starting from vertex 0:" << endl;g.BFS(0);return 0;
}

典型算法

最短路径算法

Dijkstra 算法

适用于无负权图。

• 使用一个优先队列（最小堆）存储顶点和其当前最短路径距离。
• 从源点出发，逐步松弛每个相邻顶点的距离。
• 更新优先队列中的顶点距离。
• 直到处理完所有顶点。
• 复杂度：
  • 时间复杂度为 O((V+E)log⁡V)，其中 V 是顶点数，E 是边数。
  • 空间复杂度为 O(V+E)。

#include <iostream>
#include <vector>
#include <queue>
#include <climits>using namespace std;// 用于表示图中的边
struct Edge {int target; // 边的目标顶点int weight; // 边的权重
};// 比较函数，用于优先队列（按距离升序排列）
struct Compare {bool operator()(pair<int, int> a, pair<int, int> b) {return a.second > b.second;}
};class Graph {
private:int vertices; // 顶点数量vector<vector<Edge>> adjList; // 邻接表public:Graph(int V) : vertices(V), adjList(V) {}// 添加边void addEdge(int u, int v, int weight) {adjList[u].push_back({v, weight});adjList[v].push_back({u, weight}); // 无向图}// Dijkstra 算法void dijkstra(int source) {// 存储从源点到每个顶点的最短距离，初始为无穷大vector<int> distance(vertices, INT_MAX);distance[source] = 0;// 优先队列，用于选择当前距离最小的顶点priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;pq.push({source, 0});// 遍历优先队列while (!pq.empty()) {int current = pq.top().first;  // 当前顶点int currentDist = pq.top().second; // 当前顶点的距离pq.pop();// 遍历当前顶点的邻接点for (const Edge& edge : adjList[current]) {int neighbor = edge.target;int weight = edge.weight;// 如果找到更短的路径，更新距离if (currentDist + weight < distance[neighbor]) {distance[neighbor] = currentDist + weight;pq.push({neighbor, distance[neighbor]});}}}// 输出结果cout << "Shortest distances from source " << source << ":" << endl;for (int i = 0; i < vertices; ++i) {cout << "Vertex " << i << " -> Distance: " << distance[i] << endl;}}
};int main() {// 创建一个包含5个顶点的图Graph g(5);// 添加边g.addEdge(0, 1, 2);g.addEdge(0, 3, 6);g.addEdge(1, 2, 3);g.addEdge(1, 3, 8);g.addEdge(1, 4, 5);g.addEdge(2, 4, 7);g.addEdge(3, 4, 9);// 调用 Dijkstra 算法g.dijkstra(0);return 0;
}

Bellman-Ford 算法

处理有负权图。

• 对每条边进行 V−1次松弛操作（顶点数 - 1）。

  • 每次松弛尝试更新从源点到目标点的最短路径距离。

• 在第 V 次迭代检查是否仍有边可以被松弛：

  • 如果可以，则图中存在负权环。

• 时间复杂度

  • O(V⋅E)，其中 V 是顶点数，E 是边数。
  • 适合稀疏图。

• 空间复杂度

  • O(V)用于存储距离数组。

#include <iostream>
#include <vector>
#include <climits>using namespace std;// 用于表示图中的边
struct Edge {int src;    // 边的起点int dest;   // 边的终点int weight; // 边的权重
};class Graph {
private:int vertices; // 顶点数量vector<Edge> edges; // 边的集合public:Graph(int V) : vertices(V) {}// 添加边void addEdge(int u, int v, int weight) {edges.push_back({u, v, weight});}// Bellman-Ford 算法void bellmanFord(int source) {vector<int> distance(vertices, INT_MAX); // 初始化距离为无穷大distance[source] = 0; // 源点到自身的距离为0// 松弛所有边 V-1 次for (int i = 1; i <= vertices - 1; ++i) {for (const Edge& edge : edges) {if (distance[edge.src] != INT_MAX && distance[edge.src] + edge.weight < distance[edge.dest]) {distance[edge.dest] = distance[edge.src] + edge.weight;}}}// 检测负权环for (const Edge& edge : edges) {if (distance[edge.src] != INT_MAX && distance[edge.src] + edge.weight < distance[edge.dest]) {cout << "Graph contains a negative weight cycle!" << endl;return;}}// 输出结果cout << "Shortest distances from source " << source << ":" << endl;for (int i = 0; i < vertices; ++i) {cout << "Vertex " << i << " -> Distance: ";if (distance[i] == INT_MAX)cout << "INF";elsecout << distance[i];cout << endl;}}
};int main() {// 创建一个包含5个顶点的图Graph g(5);// 添加边 (u, v, weight)g.addEdge(0, 1, -1);g.addEdge(0, 2, 4);g.addEdge(1, 2, 3);g.addEdge(1, 3, 2);g.addEdge(1, 4, 2);g.addEdge(3, 2, 5);g.addEdge(3, 1, 1);g.addEdge(4, 3, -3);// 调用 Bellman-Ford 算法g.bellmanFord(0);return 0;
}

最小生成树

Prim 算法

• 从任意一个顶点开始，将其加入最小生成树集合。

• 找到连接当前生成树集合与其余顶点的权重最小的边，将该边和顶点加入最小生成树。

• 重复上述步骤，直到所有顶点都加入生成树。

• 时间复杂度

  • 使用优先队列优化后，时间复杂度为 O(Elog⁡V)，其中 V是顶点数，E 是边数。

• 空间复杂度

  • O(V+E)，用于存储图的邻接表和辅助数组。

#include <iostream>
#include <vector>
#include <climits>
#include <queue>using namespace std;// 用于表示图中的边
struct Edge {int target; // 目标顶点int weight; // 边的权重
};// 比较函数，用于优先队列（按边权重升序排列）
struct Compare {bool operator()(pair<int, int> a, pair<int, int> b) {return a.second > b.second;}
};class Graph {
private:int vertices; // 顶点数量vector<vector<Edge>> adjList; // 邻接表public:Graph(int V) : vertices(V), adjList(V) {}// 添加边void addEdge(int u, int v, int weight) {adjList[u].push_back({v, weight});adjList[v].push_back({u, weight}); // 无向图}// Prim 算法void primMST() {vector<bool> inMST(vertices, false);  // 标记顶点是否在 MST 中vector<int> key(vertices, INT_MAX);  // 每个顶点的当前最小边权重vector<int> parent(vertices, -1);    // 记录生成树中的父节点priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;// 从第一个顶点开始key[0] = 0;pq.push({0, 0}); // {顶点, 权重}while (!pq.empty()) {int u = pq.top().first; // 当前顶点pq.pop();if (inMST[u]) continue; // 如果顶点已在 MST 中，跳过inMST[u] = true;// 遍历当前顶点的邻接点for (const Edge& edge : adjList[u]) {int v = edge.target;int weight = edge.weight;// 如果顶点 v 不在 MST 中，且权重更小，更新if (!inMST[v] && weight < key[v]) {key[v] = weight;parent[v] = u;pq.push({v, weight});}}}// 输出最小生成树cout << "Edge   Weight" << endl;for (int i = 1; i < vertices; ++i) {cout << parent[i] << " - " << i << "    " << key[i] << endl;}}
};int main() {// 创建一个包含5个顶点的图Graph g(5);// 添加边g.addEdge(0, 1, 2);g.addEdge(0, 3, 6);g.addEdge(1, 2, 3);g.addEdge(1, 3, 8);g.addEdge(1, 4, 5);g.addEdge(2, 4, 7);g.addEdge(3, 4, 9);// 调用 Prim 算法cout << "Minimum Spanning Tree (MST):" << endl;g.primMST();return 0;
}

Kruskal 算法

计算最小生成树（MST），适用于边集稠密的图。与 Prim 算法不同，Kruskal 算法是基于边的，按照边的权重从小到大排序后逐步选择边来构建生成树。

• 边排序：将图中所有边按权重从小到大排序。

• 构建最小生成树：从权重最小的边开始，逐一检查边是否会形成环（使用并查集来判断）。

• 并查集（Union-Find）：通过并查集数据结构来管理顶点，判断两顶点是否在同一个连通分量中，以防止形成环。

• 时间复杂度：

  • 排序边的时间复杂度是 O(Elog⁡E)，其中 E是边数。
  • 每次查找和合并操作的时间复杂度是 O(α(V))，其中 α是反阿克曼函数，几乎是常数级的。
  • 总体时间复杂度为 O(Elog⁡E)，由于 E 通常大于 V，因此常常简化为 O(Elog⁡V)。

• 空间复杂度：

  • O(V+E)，用于存储图的邻接表、边集合和并查集。

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// 用于表示边
struct Edge {int u, v, weight; // 边的两个端点和边的权重bool operator<(const Edge& other) const {return weight < other.weight; // 按边的权重升序排列}
};// 并查集（Union-Find）数据结构
class UnionFind {
private:vector<int> parent, rank;public:UnionFind(int n) {parent.resize(n);rank.resize(n, 0);for (int i = 0; i < n; ++i) {parent[i] = i; // 初始化时每个顶点是自己的父节点}}// 查找操作，带路径压缩int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]); // 路径压缩}return parent[x];}// 合并操作，按秩合并void unionSets(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {// 按秩合并，保持树的平衡if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else {parent[rootY] = rootX;rank[rootX]++;}}}
};class Graph {
private:int vertices; // 顶点数量vector<Edge> edges; // 边集合public:Graph(int V) : vertices(V) {}// 添加边void addEdge(int u, int v, int weight) {edges.push_back({u, v, weight});}// Kruskal 算法void kruskalMST() {// 1. 将所有边按照权重排序sort(edges.begin(), edges.end());// 2. 初始化并查集UnionFind uf(vertices);vector<Edge> mst; // 最小生成树// 3. 逐条边检查for (const Edge& edge : edges) {int u = edge.u;int v = edge.v;// 4. 如果当前边的两个端点不在同一连通分量中，则加入 MSTif (uf.find(u) != uf.find(v)) {uf.unionSets(u, v); // 合并两个顶点的连通分量mst.push_back(edge); // 将当前边加入最小生成树}}// 5. 输出最小生成树cout << "Minimum Spanning Tree (MST):" << endl;int mstWeight = 0;for (const Edge& edge : mst) {cout << edge.u << " - " << edge.v << " : " << edge.weight << endl;mstWeight += edge.weight;}cout << "Total Weight of MST: " << mstWeight << endl;}
};int main() {// 创建一个包含5个顶点的图Graph g(5);// 添加边 (u, v, weight)g.addEdge(0, 1, 2);g.addEdge(0, 3, 6);g.addEdge(1, 2, 3);g.addEdge(1, 3, 8);g.addEdge(1, 4, 5);g.addEdge(2, 4, 7);g.addEdge(3, 4, 9);// 调用 Kruskal 算法g.kruskalMST();return 0;
}

拓扑排序

参考：https://blog.csdn.net/www_dong/article/details/144122257