在c++++中实现图结构主要有邻接矩阵和邻接表两种方式。1. 邻接矩阵使用二维数组实现，优点是查询边快o(1)，缺点是空间复杂度高o(n^2)；2. 邻接表使用链表或动态数组实现，空间复杂度低o(n+e)，适合稀疏图，但查询边的时间复杂度为o(degree(v))。图的遍历算法包括dfs和bfs：3. dfs采用递归或栈实现，适合路径查找、拓扑排序等问题；4. bfs采用队列实现，适合无权图最短路径问题。对于带权图，5. 邻接矩阵可存储权重，邻接表可用pair存储邻居与权重，并结合dijkstra等算法处理最短路径问题。选择表示方式应根据图的稠密程度及应用场景决定。
在C++中实现图结构，主要有两种方式：邻接矩阵和邻接表。邻接矩阵简单直观，但空间复杂度高；邻接表节省空间，更适合表示稀疏图。图的遍历算法则包括深度优先搜索（DFS）和广度优先搜索（BFS），它们是解决许多图问题的基础。
解决方案
邻接矩阵的实现：使用二维数组来表示图中顶点之间的连接关系。
matrix[i][j] = 1
表示顶点i到顶点j存在一条边。这种方式的优点是易于实现，查询两个顶点之间是否存在边的时间复杂度为O(1)。缺点是空间复杂度为O(n^2)，n为顶点数量，当图比较稀疏时，会造成空间浪费。
立即学习“C++免费学习笔记（深入）”；
邻接表的实现：使用链表或动态数组来存储每个顶点的邻居节点。每个顶点对应一个链表，链表中存储与该顶点相邻的所有顶点。这种方式的优点是空间复杂度为O(n+e)，n为顶点数量，e为边数量，适合表示稀疏图。缺点是查询两个顶点之间是否存在边的时间复杂度为O(degree(v))，degree(v)为顶点v的度。
深度优先搜索（DFS）：从起始顶点开始，沿着一条路径尽可能深地搜索，直到到达最深处，然后回溯到上一个节点，继续搜索其他路径。DFS可以使用递归或栈来实现。
广度优先搜索（BFS）：从起始顶点开始，逐层访问所有相邻顶点，然后依次访问这些相邻顶点的相邻顶点。BFS通常使用队列来实现。
C++ 代码示例 (邻接表 + DFS)：
#include <iostream> #include <vector> using namespace std; // 图的邻接表表示 class Graph { public: int numVertices; vector<vector<int>> adjList; Graph(int vertices) : numVertices(vertices), adjList(vertices) {} void addEdge(int u, int v) { adjList[u].push_back(v); adjList[v].push_back(u); // 假设是无向图 } void DFS(int startVertex, vector<bool>& visited) { visited[startVertex] = true; cout << startVertex << " "; for (int neighbor : adjList[startVertex]) { if (!visited[neighbor]) { DFS(neighbor, visited); } } } void DFS(int startVertex) { vector<bool> visited(numVertices, false); DFS(startVertex, visited); } }; int main() { Graph g(6); // 6个顶点的图 g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(2, 4); g.addEdge(3, 5); cout << "DFS traversal starting from vertex 0: "; g.DFS(0); cout << endl; return 0; }
图的表示方式选择：邻接矩阵 vs 邻接表？
选择哪种表示方式取决于图的特性和应用场景。如果图是稠密的（边的数量接近顶点数量的平方），那么邻接矩阵可能更合适，因为它提供了快速的边查询。如果图是稀疏的（边的数量远小于顶点数量的平方），那么邻接表更节省空间。此外，某些算法可能更适合使用邻接表，例如计算图的连通分量。
图的遍历算法：DFS和BFS的应用场景？
DFS通常用于解决路径查找、拓扑排序、连通性判断等问题。例如，在迷宫问题中，可以使用DFS来寻找从起点到终点的路径。BFS则更适合解决最短路径问题，例如在无权图中寻找两个顶点之间的最短路径。此外，BFS还可以用于网络爬虫等应用。
如何在C++中处理带权图？
对于带权图，邻接矩阵可以存储边的权重而不是简单的0或1。邻接表则可以在链表中存储顶点和边的权重。例如，可以使用
std::pair<int, int>
来存储邻居顶点和边的权重。在遍历算法中，需要考虑边的权重，例如在Dijkstra算法中，需要选择权重最小的边进行扩展。
C++ 代码示例 (带权图的邻接表 + Dijkstra)：
#include <iostream> #include <vector> #include <queue> #include <limits> using namespace std; // 带权图的邻接表表示 class WeightedGraph { public: int numVertices; vector<vector<pair<int, int>>> adjList; // pair<vertex, weight> WeightedGraph(int vertices) : numVertices(vertices), adjList(vertices) {} void addEdge(int u, int v, int weight) { adjList[u].push_back(make_pair(v, weight)); adjList[v].push_back(make_pair(u, weight)); // 假设是无向图 } vector<int> dijkstra(int startVertex) { vector<int> dist(numVertices, numeric_limits<int>::max()); dist[startVertex] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // pair<distance, vertex> pq.push(make_pair(0, startVertex)); while (!pq.empty()) { int u = pq.top().second; int d = pq.top().first; pq.pop(); if (d > dist[u]) continue; // 优化：如果已经找到更短的路径，则跳过 for (auto& neighbor : adjList[u]) { int v = neighbor.first; int weight = neighbor.second; if (dist[v] > dist[u] + weight) { dist[v] = dist[u] + weight; pq.push(make_pair(dist[v], v)); } } } return dist; } }; int main() { WeightedGraph g(5); g.addEdge(0, 1, 2); g.addEdge(0, 2, 4); g.addEdge(1, 2, 1); g.addEdge(1, 3, 7); g.addEdge(2, 4, 3); g.addEdge(3, 4, 1); vector<int> distances = g.dijkstra(0); cout << "Shortest distances from vertex 0:" << endl; for (int i = 0; i < distances.size(); ++i) { cout << "To vertex " << i << ": " << distances[i] << endl; } return 0; }
评论（已关闭）
评论已关闭