怎样在C++中实现图结构_图的表示与遍历算法详解

在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为顶点数量，当图比较稀疏时，会造成空间浪费。

邻接表的实现：使用链表或动态数组来存储每个顶点的邻居节点。每个顶点对应一个链表，链表中存储与该顶点相邻的所有顶点。这种方式的优点是空间复杂度为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>> 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  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 <p>图的表示方式选择：邻接矩阵 vs 邻接表？</p>
<p>选择哪种表示方式取决于图的特性和应用场景。如果图是稠密的（边的数量接近顶点数量的平方），那么邻接矩阵可能更合适，因为它提供了快速的边查询。如果图是稀疏的（边的数量远小于顶点数量的平方），那么邻接表更节省空间。此外，某些算法可能更适合使用邻接表，例如计算图的连通分量。</p>
<p>图的遍历算法：DFS和BFS的应用场景？</p>
<p>DFS通常用于解决路径查找、拓扑排序、连通性判断等问题。例如，在迷宫问题中，可以使用DFS来寻找从起点到终点的路径。BFS则更适合解决最短路径问题，例如在无权图中寻找两个顶点之间的最短路径。此外，BFS还可以用于网络爬虫等应用。</p>
<p>如何在C++中处理带权图？</p>
<p>对于带权图，邻接矩阵可以存储边的权重而不是简单的0或1。邻接表则可以在链表中存储顶点和边的权重。例如，可以使用<pre class="brush:php;toolbar:false">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 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>, vector<pair int>>, greater<pair 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 </int></distance></pair></pair></pair></int></int></int></vertex></vector></limits></queue></vector></iostream>

C++免费学习笔记（深入）：立即学习
>在学习笔记中，你将探索 C++ 的入门与实战技巧！