图数据结构详解：概念、实现与应用

扫地的小何尚

1772人浏览 · 2025-03-31 11:16:41

扫地的小何尚 · 2025-03-31 11:16:41 发布

图数据结构详解：概念、实现与应用

图是计算机科学中最强大、最灵活的数据结构之一，它能够表示各种复杂的关系和网络。从社交网络到地图导航，从网页链接到电路设计，图无处不在。本教程将深入探讨图的基本概念、实现方法和常见应用，并提供详细的C/C++代码示例。

1. 图的基本概念

1.1 什么是图

图(Graph)是一种非线性数据结构，由顶点(Vertex)和边(Edge)组成。直观地说，图是由点和连接这些点的线组成的。在数学上，图通常表示为G = (V, E)，其中V是顶点集合，E是边集合。

图可以用来表示各种现实世界中的关系：

社交网络中的人际关系
城市之间的道路连接
计算机网络中的连接关系
分子结构中的原子连接
任务之间的依赖关系

1.2 图的术语

在深入了解图之前，我们需要熟悉一些基本术语：

顶点(Vertex)：图中的节点或点，通常用来表示实体。
边(Edge)：连接两个顶点的线，表示顶点之间的关系。
邻接(Adjacent)：如果两个顶点之间有一条边直接连接，则称这两个顶点是邻接的。
路径(Path)：从一个顶点到另一个顶点的顶点序列，其中相邻顶点之间有边相连。
环(Cycle)：起点和终点相同的路径。
度(Degree)：与某个顶点相连的边的数量。在有向图中，分为入度(In-degree)和出度(Out-degree)。
连通图(Connected Graph)：任意两个顶点之间都存在路径的图。
连通分量(Connected Component)：图中的最大连通子图。

1.3 图的分类

图可以根据不同的特性进行分类：

1.3.1 按边的方向分类

无向图(Undirected Graph)：边没有方向，表示双向关系。例如，朋友关系通常是双向的。
有向图(Directed Graph)：边有方向，表示单向关系。例如，网页之间的链接通常是单向的。

1.3.2 按边的权重分类

无权图(Unweighted Graph)：边没有权重，只表示连接关系。
带权图(Weighted Graph)：边有权重，表示连接的某种度量（如距离、成本等）。

1.3.3 其他分类

完全图(Complete Graph)：任意两个顶点之间都有边相连的图。
二分图(Bipartite Graph)：顶点可以分为两个不相交的集合，使得每条边的两个端点分别属于这两个集合。
树(Tree)：无环连通图，任意两个顶点之间有且仅有一条路径。
森林(Forest)：由多棵树组成的图。
平面图(Planar Graph)：可以在平面上画出而不让任何边相交的图。

2. 图的表示方法

在计算机中表示图有多种方法，每种方法都有其优缺点。选择哪种表示方法取决于图的特性和需要执行的操作。

2.1 邻接矩阵

邻接矩阵是表示图的最直观方法之一。对于有n个顶点的图，我们使用一个n×n的矩阵，其中矩阵的元素M[i][j]表示从顶点i到顶点j的边。

对于无权图，M[i][j] = 1表示存在边，M[i][j] = 0表示不存在边。
对于带权图，M[i][j]表示边的权重，通常用一个特殊值（如无穷大）表示不存在边。

下面是一个无向图的邻接矩阵表示示例：

在这里插入图片描述

对于有向图，邻接矩阵可能不是对称的：

在这里插入图片描述

邻接矩阵的C++实现

#include <iostream>
#include <vector>
using namespace std;

class Graph {
private:
    int V; // 顶点数
    vector<vector<int>> adjMatrix; // 邻接矩阵

public:
    // 构造函数
    Graph(int vertices) {
        this->V = vertices;
        // 初始化邻接矩阵，所有元素设为0
        adjMatrix.resize(V, vector<int>(V, 0));
    }

    // 添加边（无向图）
    void addEdge(int u, int v, int weight = 1) {
        // 确保顶点有效
        if (u >= 0 && u < V && v >= 0 && v < V) {
            adjMatrix[u][v] = weight;
            adjMatrix[v][u] = weight; // 对于无向图，矩阵是对称的
        }
    }

    // 添加边（有向图）
    void addDirectedEdge(int u, int v, int weight = 1) {
        // 确保顶点有效
        if (u >= 0 && u < V && v >= 0 && v < V) {
            adjMatrix[u][v] = weight;
        }
    }

    // 移除边
    void removeEdge(int u, int v) {
        // 确保顶点有效
        if (u >= 0 && u < V && v >= 0 && v < V) {
            adjMatrix[u][v] = 0;
            adjMatrix[v][u] = 0; // 对于无向图
        }
    }

    // 检查边是否存在
    bool isEdge(int u, int v) {
        // 确保顶点有效
        if (u >= 0 && u < V && v >= 0 && v < V) {
            return adjMatrix[u][v] != 0;
        }
        return false;
    }

    // 获取边的权重
    int getWeight(int u, int v) {
        // 确保顶点有效
        if (u >= 0 && u < V && v >= 0 && v < V) {
            return adjMatrix[u][v];
        }
        return 0; // 或者返回一个表示无效的值
    }

    // 打印邻接矩阵
    void printMatrix() {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                cout << adjMatrix[i][j] << " ";
            }
            cout << endl;
        }
    }
};

// 使用示例
int main() {
    // 创建一个有5个顶点的图
    Graph g(5);
    
    // 添加边
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 3);
    g.addEdge(3, 4);
    
    // 打印邻接矩阵
    cout << "邻接矩阵表示：" << endl;
    g.printMatrix();
    
    return 0;
}

邻接矩阵的优缺点

优点：

实现简单直观
检查两个顶点之间是否有边的时间复杂度为O(1)
适合表示稠密图（边数接近顶点数的平方）
方便进行矩阵运算（如求最短路径的Floyd算法）

缺点：

空间复杂度为O(V²)，对于大型稀疏图会浪费大量空间
添加或删除顶点的操作复杂度高，需要重新调整整个矩阵
遍历所有边的时间复杂度为O(V²)，对于稀疏图效率低

2.2 邻接表

邻接表是另一种常用的图表示方法，特别适合表示稀疏图。对于每个顶点，我们维护一个列表，存储与该顶点相邻的所有顶点。

下面是一个无向图的邻接表表示示例：

在这里插入图片描述

对于有向图，邻接表只存储出边：

在这里插入图片描述

对于带权图，我们可以在邻接表中存储边的权重：

在这里插入图片描述

邻接表的C++实现

#include <iostream>
#include <vector>
#include <list>
using namespace std;

// 用于存储边信息的结构体（用于带权图）
struct Edge {
    int dest;   // 目标顶点
    int weight; // 边的权重
    
    Edge(int d, int w) : dest(d), weight(w) {}
};

class Graph {
private:
    int V; // 顶点数
    vector<list<Edge>> adjList; // 邻接表

public:
    // 构造函数
    Graph(int vertices) {
        this->V = vertices;
        adjList.resize(V);
    }

    // 添加边（无向图）
    void addEdge(int u, int v, int weight = 1) {
        // 确保顶点有效
        if (u >= 0 && u < V && v >= 0 && v < V) {
            adjList[u].push_back(Edge(v, weight));
            adjList[v].push_back(Edge(u, weight)); // 对于无向图，添加反向边
        }
    }

    // 添加边（有向图）
    void addDirectedEdge(int u, int v, int weight = 1) {
        // 确保顶点有效
        if (u >= 0 && u < V && v >= 0 && v < V) {
            adjList[u].push_back(Edge(v, weight));
        }
    }

    // 移除边
    void removeEdge(int u, int v) {
        // 确保顶点有效
        if (u >= 0 && u < V && v >= 0 && v < V) {
            // 移除u到v的边
            adjList[u].remove_if([v](const Edge& e) { return e.dest == v; });
            // 对于无向图，还需要移除v到u的边
            adjList[v].remove_if([u](const Edge& e) { return e.dest == u; });
        }
    }

    // 检查边是否存在
    bool isEdge(int u, int v) {
        // 确保顶点有效
        if (u >= 0 && u < V && v >= 0 && v < V) {
            for (const Edge& e : adjList[u]) {
                if (e.dest == v) {
                    return true;
                }
            }
        }
        return false;
    }

    // 获取边的权重
    int getWeight(int u, int v) {
        // 确保顶点有效
        if (u >= 0 && u < V && v >= 0 && v < V) {
            for (const Edge& e : adjList[u]) {
                if (e.dest == v) {
                    return e.weight;
                }
            }
        }
        return 0; // 或者返回一个表示无效的值
    }

    // 打印邻接表
    void printList() {
        for (int i = 0; i < V; i++) {
            cout << "顶点 " << i << " 的邻接点: ";
            for (const Edge& e : adjList[i]) {
                cout << "(" << e.dest << ", 权重:" << e.weight << ") ";
            }
            cout << endl;
        }
    }
};

// 使用示例
int main() {
    // 创建一个有5个顶点的图
    Graph g(5);
    
    // 添加边
    g.addEdge(0, 1, 2);
    g.addEdge(0, 4, 5);
    g.addEdge(1, 2, 3);
    g.addEdge(1, 3, 1);
    g.addEdge(1, 4, 4);
    g.addEdge(2, 3, 6);
    g.addEdge(3, 4, 7);
    
    // 打印邻接表
    cout << "邻接表表示：" << endl;
    g.printList();
    
    return 0;
}

邻接表的优缺点

优点：

空间效率高，特别是对于稀疏图
遍历所有边的时间复杂度为O(V+E)
添加顶点操作简单，只需添加一个新的列表
适合进行图的遍历操作

缺点：

检查两个顶点之间是否有边的时间复杂度为O(degree)，最坏情况下为O(V)
删除边的操作较复杂
不如邻接矩阵直观

2.3 其他表示方法

除了邻接矩阵和邻接表，还有其他一些表示图的方法：

2.3.1 边列表

边列表是最简单的图表示方法之一，它直接存储所有的边。每条边由起点、终点和权重（如果有）组成。

#include <iostream>
#include <vector>
using namespace std;

// 边结构体
struct Edge {
    int src;    // 源顶点
    int dest;   // 目标顶点
    int weight; // 边的权重
    
    Edge(int s, int d, int w) : src(s), dest(d), weight(w) {}
};

class Graph {
private:
    int V; // 顶点数
    vector<Edge> edges; // 边列表

public:
    // 构造函数
    Graph(int vertices) {
        this->V = vertices;
    }

    // 添加边
    void addEdge(int u, int v, int weight = 1) {
        edges.push_back(Edge(u, v, weight));
    }

    // 打印边列表
    void printEdges() {
        for (const Edge& e : edges) {
            cout << "边: " << e.src << " -> " << e.dest << " 权重: " << e.weight << endl;
        }
    }
};

// 使用示例
int main() {
    // 创建一个有5个顶点的图
    Graph g(5);
    
    // 添加边
    g.addEdge(0, 1, 2);
    g.addEdge(0, 4, 5);
    g.addEdge(1, 2, 3);
    g.addEdge(1, 3, 1);
    g.addEdge(1, 4, 4);
    g.addEdge(2, 3, 6);
    g.addEdge(3, 4, 7);
    
    // 打印边列表
    cout << "边列表表示：" << endl;
    g.printEdges();
    
    return 0;
}

边列表适合某些特定算法（如Kruskal最小生成树算法），但不适合快速查询顶点之间的连接关系。

2.3.2 十字链表

十字链表是一种适合有向图的表示方法，它结合了邻接表和逆邻接表的优点，可以同时快速找到一个顶点的出边和入边。

2.3.3 邻接多重表

邻接多重表是一种适合无向图的表示方法，它可以方便地查找和删除边，以及查找与顶点关联的边。

3. 图的遍历算法

图的遍历是指按照某种顺序访问图中的所有顶点，确保每个顶点都被访问且仅被访问一次。图的遍历是许多图算法的基础，主要有两种遍历方式：深度优先搜索(DFS)和广度优先搜索(BFS)。

3.1 深度优先搜索(DFS)

深度优先搜索(Depth-First Search, DFS)是一种优先走到底、无路可走再回溯的遍历方式。它的基本思想是：从起始顶点出发，沿着一条路径一直走到底，直到不能再继续前进，然后回溯到上一个顶点，选择另一条路径继续走到底，如此往复，直到所有顶点都被访问。

DFS通常使用递归或栈来实现。

在这里插入图片描述

DFS的C++实现（递归版）

#include <iostream>
#include <vector>
#include <list>
using namespace std;

class Graph {
private:
    int V; // 顶点数
    vector<list<int>> adjList; // 邻接表

public:
    // 构造函数
    Graph(int vertices) {
        this->V = vertices;
        adjList.resize(V);
    }

    // 添加边
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
    }

    // DFS辅助函数
    void DFSUtil(int v, vector<bool>& visited) {
        // 标记当前顶点为已访问
        visited[v] = true;
        cout << v << " ";

        // 递归访问所有未访问的邻接点
        for (int adjacent : adjList[v]) {
            if (!visited[adjacent]) {
                DFSUtil(adjacent, visited);
            }
        }
    }

    // DFS遍历
    void DFS(int startVertex) {
        // 创建标记数组，初始化所有顶点为未访问
        vector<bool> visited(V, false);

        // 从指定顶点开始DFS
        cout << "从顶点 " << startVertex << " 开始的DFS遍历: ";
        DFSUtil(startVertex, visited);
        cout << endl;

        // 处理非连通图的情况，确保所有顶点都被访问
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                DFSUtil(i, visited);
            }
        }
    }
};

// 使用示例
int main() {
    // 创建一个有5个顶点的图
    Graph g(5);
    
    // 添加边
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 3);
    g.addEdge(3, 4);
    
    // 执行DFS遍历
    g.DFS(0);
    
    return 0;
}

DFS的C++实现（非递归版，使用栈）

#include <iostream>
#include <vector>
#include <list>
#include <stack>
using namespace std;

class Graph {
private:
    int V; // 顶点数
    vector<list<int>> adjList; // 邻接表

public:
    // 构造函数
    Graph(int vertices) {
        this->V = vertices;
        adjList.resize(V);
    }

    // 添加边
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
    }

    // 非递归DFS遍历
    void DFS(int startVertex) {
        // 创建标记数组，初始化所有顶点为未访问
        vector<bool> visited(V, false);
        stack<int> s;

        // 将起始顶点入栈
        s.push(startVertex);

        cout << "从顶点 " << startVertex << " 开始的DFS遍历: ";
        
        while (!s.empty()) {
            // 弹出栈顶顶点并打印
            int v = s.top();
            s.pop();

            // 如果当前顶点未访问，则标记为已访问并处理
            if (!visited[v]) {
                cout << v << " ";
                visited[v] = true;
            }

            // 将所有未访问的邻接点入栈
            // 注意：这里我们逆序遍历邻接点，以保持与递归版本相似的访问顺序
            for (auto it = adjList[v].rbegin(); it != adjList[v].rend(); ++it) {
                if (!visited[*it]) {
                    s.push(*it);
                }
            }
        }
        cout << endl;
    }
};

// 使用示例
int main() {
    // 创建一个有5个顶点的图
    Graph g(5);
    
    // 添加边
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 3);
    g.addEdge(3, 4);
    
    // 执行DFS遍历
    g.DFS(0);
    
    return 0;
}

DFS的应用

DFS有许多重要的应用：

路径查找：查找从一个顶点到另一个顶点的路径。
拓扑排序：对有向无环图进行拓扑排序。
连通分量：查找图的连通分量。
环检测：检测图中是否存在环。
迷宫生成与求解：生成迷宫或求解迷宫问题。
二分图检测：检测一个图是否是二分图。

3.2 广度优先搜索(BFS)

广度优先搜索(Breadth-First Search, BFS)是一种优先访问邻近顶点的遍历方式。它的基本思想是：从起始顶点出发，先访问所有邻接点，然后再从这些邻接点出发，访问它们的邻接点，以此类推，直到所有顶点都被访问。

BFS通常使用队列来实现。

在这里插入图片描述

BFS的C++实现

#include <iostream>
#include <vector>
#include <list>
#include <queue>
using namespace std;

class Graph {
private:
    int V; // 顶点数
    vector<list<int>> adjList; // 邻接表

public:
    // 构造函数
    Graph(int vertices) {
        this->V = vertices;
        adjList.resize(V);
    }

    // 添加边
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
    }

    // BFS遍历
    void BFS(int startVertex) {
        // 创建标记数组，初始化所有顶点为未访问
        vector<bool> visited(V, false);
        queue<int> q;

        // 标记起始顶点为已访问并入队
        visited[startVertex] = true;
        q.push(startVertex);

        cout << "从顶点 " << startVertex << " 开始的BFS遍历: ";
        
        while (!q.empty()) {
            // 出队一个顶点并打印
            int v = q.front();
            q.pop();
            cout << v << " ";

            // 将所有未访问的邻接点入队
            for (int adjacent : adjList[v]) {
                if (!visited[adjacent]) {
                    visited[adjacent] = true;
                    q.push(adjacent);
                }
            }
        }
        cout << endl;
    }
};

// 使用示例
int main() {
    // 创建一个有5个顶点的图
    Graph g(5);
    
    // 添加边
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 3);
    g.addEdge(3, 4);
    
    // 执行BFS遍历
    g.BFS(0);
    
    return 0;
}

BFS的应用

BFS也有许多重要的应用：

最短路径：在无权图中查找两点之间的最短路径。
连通分量：查找图的连通分量。
层次遍历：对图进行层次遍历。
网络爬虫：实现网络爬虫，从一个网页开始，按层次抓取相关网页。
社交网络分析：分析社交网络中的"六度分隔"理论。
广告推荐系统：基于用户关系网络的广告推荐。

4. 图的应用和高级主题

图是一种非常强大的数据结构，有着广泛的应用。在本节中，我们将探讨一些重要的图算法和应用。

4.1 最小生成树

最小生成树(Minimum Spanning Tree, MST)是连通加权无向图中一棵权值最小的生成树。在许多网络设计问题中，我们需要以最小的成本连接所有节点，这就是最小生成树问题。

在这里插入图片描述

有两种经典算法用于求解最小生成树问题：Prim算法和Kruskal算法。

4.1.1 Prim算法

Prim算法的基本思想是从一个起始顶点开始，逐步扩展生成树，每次选择一条连接树内顶点和树外顶点的最小权边，将该边和对应的树外顶点加入到生成树中，直到所有顶点都被加入。

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

// 用于优先队列的比较函数
struct CompareEdge {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        return a.second > b.second; // 最小堆
    }
};

class Graph {
private:
    int V; // 顶点数
    vector<vector<pair<int, int>>> adjList; // 邻接表，pair表示(目标顶点, 权重)

public:
    // 构造函数
    Graph(int vertices) {
        this->V = vertices;
        adjList.resize(V);
    }

    // 添加边
    void addEdge(int u, int v, int weight) {
        adjList[u].push_back(make_pair(v, weight));
        adjList[v].push_back(make_pair(u, weight)); // 无向图
    }

    // Prim算法求最小生成树
    void primMST() {
        // 存储MST的结果
        vector<int> parent(V, -1); // 存储MST中每个顶点的父节点
        vector<int> key(V, INT_MAX); // 存储每个顶点加入MST的最小权值
        vector<bool> inMST(V, false); // 标记顶点是否已加入MST

        // 使用优先队列来获取最小权值边
        priority_queue<pair<int, int>, vector<pair<int, int>>, CompareEdge> pq;

        // 从顶点0开始
        key[0] = 0;
        pq.push(make_pair(0, 0)); // (顶点, 权值)

        while (!pq.empty()) {
            // 提取最小权值顶点
            int u = pq.top().first;
            pq.pop();

            // 如果顶点已在MST中，则跳过
            if (inMST[u]) {
                continue;
            }

            // 将顶点加入MST
            inMST[u] = true;

            // 更新相邻顶点的key值
            for (const auto& edge : adjList[u]) {
                int v = edge.first;
                int weight = edge.second;

                // 如果v不在MST中且权值小于当前key值
                if (!inMST[v] && weight < key[v]) {
                    // 更新key值和父节点
                    parent[v] = u;
                    key[v] = weight;
                    pq.push(make_pair(v, key[v]));
                }
            }
        }

        // 打印MST
        cout << "最小生成树的边：" << endl;
        for (int i = 1; i < V; 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算法
    g.primMST();
    
    return 0;
}

4.1.2 Kruskal算法

Kruskal算法的基本思想是按照边的权值从小到大排序，然后逐一考察每条边，如果当前边的两个端点不在同一个连通分量中，则将该边加入到生成树中，直到所有顶点都在同一个连通分量中。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 边结构体
struct Edge {
    int src, dest, weight;
    
    Edge(int s, int d, int w) : src(s), dest(d), weight(w) {}
};

// 并查集结构
class DisjointSet {
private:
    vector<int> parent, rank;

public:
    DisjointSet(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) {
            return;
        }
        
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
};

class Graph {
private:
    int V; // 顶点数
    vector<Edge> edges; // 边列表

public:
    // 构造函数
    Graph(int vertices) {
        this->V = vertices;
    }

    // 添加边
    void addEdge(int u, int v, int weight) {
        edges.push_back(Edge(u, v, weight));
    }

    // Kruskal算法求最小生成树
    void kruskalMST() {
        // 存储MST的结果
        vector<Edge> result;
        
        // 按照边的权值排序
        sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
            return a.weight < b.weight;
        });
        
        // 创建并查集
        DisjointSet ds(V);
        
        // 遍历所有边
        for (const Edge& edge : edges) {
            int srcRoot = ds.find(edge.src);
            int destRoot = ds.find(edge.dest);
            
            // 如果当前边的两个端点不在同一个连通分量中，则将该边加入MST
            if (srcRoot != destRoot) {
                result.push_back(edge);
                ds.unionSets(srcRoot, destRoot);
            }
            
            // 如果MST已经有V-1条边，则结束
            if (result.size() == V - 1) {
                break;
            }
        }
        
        // 打印MST
        cout << "最小生成树的边：" << endl;
        for (const Edge& edge : result) {
            cout << edge.src << " - " << edge.dest << " 权重: " << edge.weight << 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);
    
    // 执行Kruskal算法
    g.kruskalMST();
    
    return 0;
}

4.1.3 Prim算法与Kruskal算法的比较

算法	时间复杂度	适用场景
Prim	O(E log V)	稠密图
Kruskal	O(E log E) 或 O(E log V)	稀疏图

Prim算法从顶点的角度出发，适合稠密图；Kruskal算法从边的角度出发，适合稀疏图。

4.2 最短路径算法

最短路径问题是图论中的一个经典问题，它要求在一个带权图中找到从一个顶点到另一个顶点的路径，使得路径上的权值之和最小。

最短路径问题有多种变体：

单源最短路径：从一个源点到所有其他顶点的最短路径。
单目标最短路径：从所有顶点到一个目标顶点的最短路径。
单对最短路径：从一个顶点到另一个顶点的最短路径。
全对最短路径：任意两个顶点之间的最短路径。

4.2.1 Dijkstra算法

Dijkstra算法用于解决单源最短路径问题，前提是图中不存在负权边。

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

// 用于优先队列的比较函数
struct CompareDistance {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        return a.second > b.second; // 最小堆
    }
};

class Graph {
private:
    int V; // 顶点数
    vector<vector<pair<int, int>>> adjList; // 邻接表，pair表示(目标顶点, 权重)

public:
    // 构造函数
    Graph(int vertices) {
        this->V = vertices;
        adjList.resize(V);
    }

    // 添加边
    void addEdge(int u, int v, int weight) {
        adjList[u].push_back(make_pair(v, weight));
    }

    // Dijkstra算法求单源最短路径
    void dijkstra(int src) {
        // 存储最短距离
        vector<int> dist(V, INT_MAX);
        // 存储前驱顶点，用于重建路径
        vector<int> prev(V, -1);
        // 标记顶点是否已处理
        vector<bool> processed(V, false);

        // 使用优先队列来获取最小距离顶点
        priority_queue<pair<int, int>, vector<pair<int, int>>, CompareDistance> pq;

        // 源点到自身的距离为0
        dist[src] = 0;
        pq.push(make_pair(src, 0)); // (顶点, 距离)

        while (!pq.empty()) {
            // 提取最小距离顶点
            int u = pq.top().first;
            pq.pop();

            // 如果顶点已处理，则跳过
            if (processed[u]) {
                continue;
            }

            // 标记顶点为已处理
            processed[u] = true;

            // 更新相邻顶点的距离
            for (const auto& edge : adjList[u]) {
                int v = edge.first;
                int weight = edge.second;

                // 松弛操作
                if (!processed[v] && dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    prev[v] = u;
                    pq.push(make_pair(v, dist[v]));
                }
            }
        }

        // 打印最短路径
        cout << "从顶点 " << src << " 到各顶点的最短距离：" << endl;
        for (int i = 0; i < V; i++) {
            cout << "到顶点 " << i << " 的距离: ";
            if (dist[i] == INT_MAX) {
                cout << "无法到达" << endl;
            } else {
                cout << dist[i] << endl;
                
                // 打印路径
                cout << "  路径: ";
                vector<int> path;
                for (int at = i; at != -1; at = prev[at]) {
                    path.push_back(at);
                }
                for (int j = path.size() - 1; j >= 0; j--) {
                    cout << path[j];
                    if (j > 0) {
                        cout << " -> ";
                    }
                }
                cout << endl;
            }
        }
    }
};

// 使用示例
int main() {
    // 创建一个有5个顶点的图
    Graph g(5);
    
    // 添加边
    g.addEdge(0, 1, 4);
    g.addEdge(0, 2, 1);
    g.addEdge(1, 3, 1);
    g.addEdge(2, 1, 2);
    g.addEdge(2, 3, 5);
    g.addEdge(3, 4, 3);
    
    // 执行Dijkstra算法
    g.dijkstra(0);
    
    return 0;
}

4.2.2 Floyd-Warshall算法

Floyd-Warshall算法用于解决全对最短路径问题，它可以处理带有负权边的图，但不能处理带有负权环的图。

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

class Graph {
private:
    int V; // 顶点数
    vector<vector<int>> adjMatrix; // 邻接矩阵

public:
    // 构造函数
    Graph(int vertices) {
        this->V = vertices;
        adjMatrix.resize(V, vector<int>(V, INT_MAX));
        
        // 自身到自身的距离为0
        for (int i = 0; i < V; i++) {
            adjMatrix[i][i] = 0;
        }
    }

    // 添加边
    void addEdge(int u, int v, int weight) {
        adjMatrix[u][v] = weight;
    }

    // Floyd-Warshall算法求全对最短路径
    void floydWarshall() {
        // 创建距离矩阵的副本
        vector<vector<int>> dist = adjMatrix;
        // 创建前驱矩阵，用于重建路径
        vector<vector<int>> next(V, vector<int>(V, -1));
        
        // 初始化next矩阵
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (i != j && dist[i][j] != INT_MAX) {
                    next[i][j] = j;
                }
            }
        }

        // 核心算法
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    // 如果经过顶点k的路径更短，则更新
                    if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && 
                        dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        next[i][j] = next[i][k];
                    }
                }
            }
        }

        // 检测负权环
        for (int i = 0; i < V; i++) {
            if (dist[i][i] < 0) {
                cout << "图中存在负权环" << endl;
                return;
            }
        }

        // 打印所有顶点对之间的最短路径
        cout << "所有顶点对之间的最短距离：" << endl;
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (i != j) {
                    cout << "从顶点 " << i << " 到顶点 " << j << " 的距离: ";
                    if (dist[i][j] == INT_MAX) {
                        cout << "无法到达" << endl;
                    } else {
                        cout << dist[i][j] << endl;
                        
                        // 打印路径
                        cout << "  路径: ";
                        vector<int> path;
                        path.push_back(i);
                        
                        int at = i;
                        while (at != j) {
                            at = next[at][j];
                            if (at == -1) {
                                break;
                            }
                            path.push_back(at);
                        }
                        
                        for (size_t k = 0; k < path.size(); k++) {
                            cout << path[k];
                            if (k < path.size() - 1) {
                                cout << " -> ";
                            }
                        }
                        cout << endl;
                    }
                }
            }
        }
    }
};

// 使用示例
int main() {
    // 创建一个有4个顶点的图
    Graph g(4);
    
    // 添加边
    g.addEdge(0, 1, 5);
    g.addEdge(0, 3, 10);
    g.addEdge(1, 2, 3);
    g.addEdge(2, 3, 1);
    
    // 执行Floyd-Warshall算法
    g.floydWarshall();
    
    return 0;
}

4.2.3 Bellman-Ford算法

Bellman-Ford算法也用于解决单源最短路径问题，它可以处理带有负权边的图，并能检测负权环。

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// 边结构体
struct Edge {
    int src, dest, weight;
    
    Edge(int s, int d, int w) : src(s), dest(d), weight(w) {}
};

class Graph {
private:
    int V; // 顶点数
    vector<Edge> edges; // 边列表

public:
    // 构造函数
    Graph(int vertices) {
        this->V = vertices;
    }

    // 添加边
    void addEdge(int u, int v, int weight) {
        edges.push_back(Edge(u, v, weight));
    }

    // Bellman-Ford算法求单源最短路径
    void bellmanFord(int src) {
        // 存储最短距离
        vector<int> dist(V, INT_MAX);
        // 存储前驱顶点，用于重建路径
        vector<int> prev(V, -1);

        // 源点到自身的距离为0
        dist[src] = 0;

        // 松弛操作，最多进行V-1次
        for (int i = 0; i < V - 1; i++) {
            for (const Edge& edge : edges) {
                int u = edge.src;
                int v = edge.dest;
                int weight = edge.weight;

                // 松弛操作
                if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    prev[v] = u;
                }
            }
        }

        // 检测负权环
        for (const Edge& edge : edges) {
            int u = edge.src;
            int v = edge.dest;
            int weight = edge.weight;

            // 如果还能继续松弛，则存在负权环
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                cout << "图中存在负权环" << endl;
                return;
            }
        }

        // 打印最短路径
        cout << "从顶点 " << src << " 到各顶点的最短距离：" << endl;
        for (int i = 0; i < V; i++) {
            cout << "到顶点 " << i << " 的距离: ";
            if (dist[i] == INT_MAX) {
                cout << "无法到达" << endl;
            } else {
                cout << dist[i] << endl;
                
                // 打印路径
                cout << "  路径: ";
                vector<int> path;
                for (int at = i; at != -1; at = prev[at]) {
                    path.push_back(at);
                }
                for (int j = path.size() - 1; j >= 0; j--) {
                    cout << path[j];
                    if (j > 0) {
                        cout << " -> ";
                    }
                }
                cout << endl;
            }
        }
    }
};

// 使用示例
int main() {
    // 创建一个有5个顶点的图
    Graph g(5);
    
    // 添加边
    g.addEdge(0, 1, 4);
    g.addEdge(0, 2, 1);
    g.addEdge(1, 3, 1);
    g.addEdge(2, 1, 2);
    g.addEdge(2, 3, 5);
    g.addEdge(3, 4, 3);
    
    // 执行Bellman-Ford算法
    g.bellmanFord(0);
    
    return 0;
}

4.3 拓扑排序

拓扑排序是对有向无环图(DAG)的顶点进行排序，使得对于图中的每一条有向边(u, v)，顶点u在排序中都出现在顶点v之前。拓扑排序常用于表示任务之间的依赖关系。

#include <iostream>
#include <vector>
#include <list>
#include <queue>
using namespace std;

class Graph {
private:
    int V; // 顶点数
    vector<list<int>> adjList; // 邻接表
    vector<int> inDegree; // 存储每个顶点的入度

public:
    // 构造函数
    Graph(int vertices) {
        this->V = vertices;
        adjList.resize(V);
        inDegree.resize(V, 0);
    }

    // 添加边
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
        inDegree[v]++; // 增加v的入度
    }

    // 拓扑排序（Kahn算法）
    void topologicalSort() {
        // 存储结果
        vector<int> result;
        // 存储入度为0的顶点
        queue<int> q;

        // 将所有入度为0的顶点入队
        for (int i = 0; i < V; i++) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }

        // 计数已排序的顶点数
        int count = 0;

        // 处理队列中的顶点
        while (!q.empty()) {
            // 出队一个顶点并加入结果
            int u = q.front();
            q.pop();
            result.push_back(u);
            count++;

            // 减少所有相邻顶点的入度，如果入度变为0，则入队
            for (int v : adjList[u]) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    q.push(v);
                }
            }
        }

        // 检查是否存在环
        if (count != V) {
            cout << "图中存在环，无法进行拓扑排序" << endl;
            return;
        }

        // 打印拓扑排序结果
        cout << "拓扑排序结果: ";
        for (int i : result) {
            cout << i << " ";
        }
        cout << endl;
    }
};

// 使用示例
int main() {
    // 创建一个有6个顶点的有向无环图
    Graph g(6);
    
    // 添加边
    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);
    
    // 执行拓扑排序
    g.topologicalSort();
    
    return 0;
}

4.4 关键路径

关键路径是在带权有向无环图(DAG)中，从源点到汇点的最长路径。它通常用于项目管理中，表示完成整个项目所需的最短时间。

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <algorithm>
#include <climits>
using namespace std;

class Graph {
private:
    int V; // 顶点数
    vector<list<pair<int, int>>> adjList; // 邻接表，pair表示(目标顶点, 权重)

public:
    // 构造函数
    Graph(int vertices) {
        this->V = vertices;
        adjList.resize(V);
    }

    // 添加边
    void addEdge(int u, int v, int weight) {
        adjList[u].push_back(make_pair(v, weight));
    }

    // 拓扑排序
    void topologicalSortUtil(int v, vector<bool>& visited, stack<int>& s) {
        // 标记当前顶点为已访问
        visited[v] = true;

        // 递归访问所有未访问的邻接点
        for (const auto& edge : adjList[v]) {
            int u = edge.first;
            if (!visited[u]) {
                topologicalSortUtil(u, visited, s);
            }
        }

        // 将当前顶点入栈
        s.push(v);
    }

    // 关键路径算法
    void criticalPath() {
        // 执行拓扑排序
        stack<int> s;
        vector<bool> visited(V, false);
        
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                topologicalSortUtil(i, visited, s);
            }
        }

        // 初始化最早开始时间
        vector<int> earliest(V, 0);

        // 按拓扑顺序计算最早开始时间
        while (!s.empty()) {
            int u = s.top();
            s.pop();

            for (const auto& edge : adjList[u]) {
                int v = edge.first;
                int weight = edge.second;
                
                // 更新最早开始时间
                if (earliest[u] + weight > earliest[v]) {
                    earliest[v] = earliest[u] + weight;
                }
            }
        }

        // 找到汇点（出度为0的顶点）
        vector<int> outDegree(V, 0);
        for (int u = 0; u < V; u++) {
            for (const auto& edge : adjList[u]) {
                outDegree[u]++;
            }
        }

        // 找到项目完成时间（汇点的最早开始时间）
        int projectDuration = 0;
        for (int i = 0; i < V; i++) {
            if (outDegree[i] == 0 && earliest[i] > projectDuration) {
                projectDuration = earliest[i];
            }
        }

        // 初始化最晚开始时间
        vector<int> latest(V, projectDuration);

        // 重新执行拓扑排序
        visited.assign(V, false);
        while (!s.empty()) {
            s.pop();
        }
        
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                topologicalSortUtil(i, visited, s);
            }
        }

        // 按逆拓扑顺序计算最晚开始时间
        while (!s.empty()) {
            int u = s.top();
            s.pop();

            for (const auto& edge : adjList[u]) {
                int v = edge.first;
                int weight = edge.second;
                
                // 更新最晚开始时间
                if (latest[v] - weight < latest[u]) {
                    latest[u] = latest[v] - weight;
                }
            }
        }

        // 计算松弛时间并找出关键路径
        cout << "关键活动（零松弛时间的活动）：" << endl;
        for (int u = 0; u < V; u++) {
            for (const auto& edge : adjList[u]) {
                int v = edge.first;
                int weight = edge.second;
                
                // 计算松弛时间
                int slack = latest[v] - earliest[u] - weight;
                
                // 如果松弛时间为0，则该活动在关键路径上
                if (slack == 0) {
                    cout << u << " -> " << v << " 权重: " << weight << endl;
                }
            }
        }

        // 打印项目完成时间
        cout << "项目完成时间: " << projectDuration << endl;
    }
};

// 使用示例
int main() {
    // 创建一个有7个顶点的有向无环图
    Graph g(7);
    
    // 添加边（活动）
    g.addEdge(0, 1, 3);
    g.addEdge(0, 2, 5);
    g.addEdge(1, 3, 6);
    g.addEdge(2, 3, 2);
    g.addEdge(2, 4, 4);
    g.addEdge(3, 5, 1);
    g.addEdge(4, 5, 8);
    g.addEdge(5, 6, 2);
    
    // 执行关键路径算法
    g.criticalPath();
    
    return 0;
}

总结

图是一种非常强大和灵活的数据结构，它可以用来表示各种复杂的关系和网络。在本教程中，我们深入探讨了图的基本概念、表示方法、遍历算法以及一些重要的应用和高级主题。

我们学习了：

图的基本概念和术语
图的分类（有向图、无向图、带权图等）
图的表示方法（邻接矩阵、邻接表、边列表等）
图的遍历算法（深度优先搜索和广度优先搜索）
图的应用和高级主题（最小生成树、最短路径算法、拓扑排序、关键路径）

通过这些知识，你应该能够理解和实现各种图算法，并将它们应用到实际问题中。

图算法在计算机科学中有着广泛的应用，从网络路由到社交网络分析，从游戏开发到人工智能，几乎无处不在。掌握图算法将为你解决复杂问题提供强大的工具。

参考资料

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. “Introduction to Algorithms”
Robert Sedgewick, Kevin Wayne. “Algorithms”
Hello 算法. “图的遍历”. https://www.hello-algo.com/chapter_graph/graph_traversal/
CSDN博客. “图的应用-最小生成树-最短路径-拓扑排序-关键路径”. https://blog.csdn.net/huajian225/article/details/135898276
CSDN博客. “数据结构——图的应用（最小生成树，最短路径，拓扑排序，关键路径）”. https://blog.csdn.net/2301_79431343/article/details/136930451