C++图论简介与实现

图论是计算机科学中一个重要的领域，用于研究图数据结构以及图算法。图由节点（顶点）和连接节点的边组成，可以用于表示各种关系和网络结构。在本篇博客中，我们将介绍C++中常用的图论算法，并给出相应的代码实现。

图的表示

图可以用多种方式进行表示，常见的有邻接矩阵和邻接链表。在C++中，我们可以使用二维数组或者容器来表示图。

邻接矩阵表示

邻接矩阵是一个二维数组，用于表示图中每个节点之间的连接关系。如果节点i和节点j之间有一条边，则邻接矩阵中的第i行第j列和第j行第i列的元素为1，否则为0。

const int MAX_NODES = 100;
int adjMatrix[MAX_NODES][MAX_NODES];

void addEdge(int u, int v) {
    adjMatrix[u][v] = adjMatrix[v][u] = 1;
}

邻接链表表示

邻接链表是一种更灵活的图表示方法，它使用一个数组或者容器来存储每个节点的邻居节点。在C++中，我们可以使用vector或者list来实现邻接链表。

const int MAX_NODES = 100;
vector<int> adjList[MAX_NODES];

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

图的遍历

图的遍历是指以某个节点为起点，依次访问图中的所有节点。常见的图遍历算法有深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索

深度优先搜索是一种递归的图遍历算法，它从起点开始，依次访问起点的邻居节点，然后再访问邻居节点的邻居节点，直到遍历完所有的节点。

bool visited[MAX_NODES];

void dfs(int u) {
    visited[u] = true;
    cout << u << " ";

    for (int v : adjList[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

广度优先搜索

广度优先搜索是一种非递归的图遍历算法，它从起点开始，依次访问起点的邻居节点，然后再访问邻居节点的邻居节点，直到遍历完所有的节点。广度优先搜索使用队列来保存待访问的节点。

bool visited[MAX_NODES];

void bfs(int u) {
    queue<int> q;
    visited[u] = true;
    q.push(u);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        cout << v << " ";

        for (int w : adjList[v]) {
            if (!visited[w]) {
                visited[w] = true;
                q.push(w);
            }
        }
    }
}

图的最短路径

最短路径是指在图中找到两个节点之间最短的路径。常见的最短路径算法有Dijkstra算法和Bellman-Ford算法。

Dijkstra算法

Dijkstra算法是一种贪心算法，用于求解带权图中的最短路径。它从起点开始，依次更新起点到其他节点的最短路径，并选择当前最短路径的节点作为下一个节点。

const int INF = INT_MAX;

void dijkstra(int start) {
    vector<int> dist(MAX_NODES, INF);
    dist[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        for (int v : adjList[u]) {
            int weight = 1; // 假设边的权重都为1
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
}

Bellman-Ford算法

Bellman-Ford算法是一种动态规划算法，用于求解带权图中的最短路径。它从起点开始，依次更新起点到其他节点的最短路径，直到没有更新操作为止。

const int INF = INT_MAX;

void bellmanFord(int start) {
    vector<int> dist(MAX_NODES, INF);
    dist[start] = 0;

    for (int i = 0; i < MAX_NODES - 1; i++) {
        for (int u = 0; u < MAX_NODES; u++) {
            for (int v : adjList[u]) {
                int weight = 1; // 假设边的权重都为1
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }
    }
}

总结

图论在计算机科学中有着广泛的应用，涉及到图的表示、遍历和最短路径等问题。本篇博客介绍了C++中常用的图论算法，并给出了相应的代码实现。希望对读者能有所帮助