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 
#include 

using namespace std;

// 图的邻接表表示
class Graph {
public:
    int numVertices;
    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& visited) {
        visited[startVertex] = true;
        cout << startVertex << " ";

        for (int neighbor : adjList[startVertex]) {
            if (!visited[neighbor]) {
                DFS(neighbor, visited);
            }
        }
    }

    void DFS(int startVertex) {
        vector 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来存储邻居顶点和边的权重。在遍历算法中，需要考虑边的权重，例如在Dijkstra算法中，需要选择权重最小的边进行扩展。

C++ 代码示例 (带权图的邻接表 + Dijkstra)：

#include 
#include 
#include 
#include 

using namespace std;

// 带权图的邻接表表示
class WeightedGraph {
public:
    int numVertices;
    vector>> adjList; // pair

    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 dijkstra(int startVertex) {
        vector dist(numVertices, numeric_limits::max());
        dist[startVertex] = 0;

        priority_queue, vector>, greater>> pq; // pair
        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 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;
}