从概念到实践，探索C++中的图论基础

11个月前 (08-09)编程语言20

在编程的世界里，图论是一种强大的工具，它能够帮助我们解决复杂的问题，本篇文章将深入浅出地讲解图论的基础概念以及如何使用C++来实现图的储存和操作，通过一系列有趣且富有创意的例子，我们将带你一步步走进图的世界。

图的基本概念

图是由顶点（Vertex）和边（Edge）组成的抽象数据结构，顶点表示实体或事件，边则表示实体之间的关系，根据边的方向，图可以分为无向图、有向图和混合图，图还可以根据边是否允许重复、是否存在自环进行分类。

图的储存方式

在C++中，我们可以采用邻接矩阵和邻接表两种方式来储存图：

邻接矩阵

邻接矩阵是一种二维数组，用于表示图中的边，对于无向图，如果从顶点i到顶点j有一条边，则矩阵[i][j]和[j][i]都为1；对于有向图，只有从i到j存在边时，矩阵[i][j]才为1。

#include 
#include 
using namespace std;
int main() {
    int n = 5; // 顶点数
    vector> adjMatrix(n, vector(n, 0)); // 初始化邻接矩阵
    // 添加边
    adjMatrix[0][1] = 1;
    adjMatrix[1][2] = 1;
    adjMatrix[2][3] = 1;
    adjMatrix[3][4] = 1;
    adjMatrix[4][0] = 1;
    // 打印邻接矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << adjMatrix[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

邻接表

邻接表用链表表示图中的边，每个顶点都有一个链表指向与其相连的所有顶点。

#include 
#include 
using namespace std;
struct Edge {
    int to;
    Edge* next;
};
void addEdge(Edge*& head, int from, int to) {
    Edge* newEdge = new Edge();
    newEdge->to = to;
    newEdge->next = head[from];
    head[from] = newEdge;
}
int main() {
    int n = 5; // 顶点数
    vector head(n);
    // 添加边
    addEdge(head, 0, 1);
    addEdge(head, 1, 2);
    addEdge(head, 2, 3);
    addEdge(head, 3, 4);
    addEdge(head, 4, 0);
    // 遍历邻接表并打印边
    for (int i = 0; i < n; ++i) {
        Edge* edge = head[i];
        while (edge != nullptr) {
            cout << i << " -> " << edge->to << endl;
            edge = edge->next;
        }
    }
    return 0;
}

实战案例：求解最短路径

使用Dijkstra算法解决最短路径问题是一个典型的图论应用，以下是一个简单的实现：

#include 
#include 
#include 
#define INF INT_MAX
void dijkstra(vector>>& graph, int start) {
    int n = graph.size();
    vector dist(n, INF);
    dist[start] = 0;
    vector visited(n, false);
    for (int count = 0; count < n - 1; ++count) {
        int u = -1;
        for (int v = 0; v < n; ++v) {
            if (!visited[v] && (u == -1 || dist[v] < dist[u])) {
                u = v;
            }
        }
        visited[u] = true;
        for (auto& edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (!visited[v] && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        cout << "Node " << i << " distance: " << dist[i] << endl;
    }
}
int main() {
    int n = 5; // 顶点数
    vector>> graph(n);
    // 添加边及权重
    graph[0].push_back(make_pair(1, 1));
    graph[1].push_back(make_pair(2, 1));
    graph[1].push_back(make_pair(0, 1));
    graph[2].push_back(make_pair(3, 1));
    graph[3].push_back(make对4, 1);
    graph[4].push_back(make_pair(0, 1));
    dijkstra(graph, 0);
    return 0;
}

通过本文，我们不仅学习了图论的基本概念和C++中图的储存方式，还通过实际案例了解了如何应用这些知识解决实际问题，图论作为计算机科学中的重要分支，在网络分析、路径规划、社交网络分析等领域有着广泛的应用，希望这篇教程能激发你对图论的兴趣，并在实践中不断提升自己的编程能力。