【C++数据结构——图】图的遍历（头歌教学实验平台习题） 【合集】

【C++数据结构——图】图的遍历（头歌教学实验平台习题） 【合集】

任务描述

本关任务：实现图的遍历

相关知识

为了完成本关任务，你需要掌握：

1. 深度优先遍历（采用递归算法）
2. 广度优先遍历

深度优先遍历

1. 定义

• 深度优先遍历（Depth - First Search，简称 DFS）是一种用于遍历或搜索图（包括树，树是一种特殊的图）的算法。采用递归算法的深度优先遍历是指在遍历图的过程中，通过递归调用函数自身来实现对图中节点的深度优先访问。
• 其基本思想是从给定的起始节点开始，沿着一条路径尽可能深地探索图，直到无法继续或者达到目标节点，然后回溯到前一个节点，继续探索其他未访问的分支路径。

2. 工作原理

初始状态

• 选择一个起始节点，将其标记为已访问，以避免重复访问。
• 通常会使用一个数据结构（如数组、布尔向量等）来记录节点是否被访问过。

递归探索

• 对于起始节点的每一个未访问的邻接节点，递归地调用深度优先遍历函数。这意味着每次到一个新的邻接节点，就将其视为新的起始节点，继续深入探索它的邻接节点。
• 例如，在一个简单的图中，如果从节点 A 开始，A 有邻接节点 B 和 C。先访问 B，然后对于 B 的未访问邻接节点（假设为 D 和 E），又会分别以 D 和 E 为新的起点进行递归探索，直到所有从 B 可达的节点都被访问，然后回溯到 A，再去访问 C 及其可达节点。

回溯机制

• 当一个节点的所有邻接节点都被访问后，递归函数会返回上一层调用，这就是回溯过程。回溯到上一层后，继续探索上一层节点的其他未访问邻接节点。
• 例如，在上述例子中，当完成对以 B 为起点的所有可达节点的访问后，就会回溯到 A，然后开始访问 C 及其可达节点。

. 示例代码（以简单图的邻接表表示为例）

以下是一个简单的 C++ 代码示例，用于对一个图进行深度优先遍历：

代码语言：javascript代码运行次数：0运行复制

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

class Graph {
private:
    int V;
    vector<vector<int>> adj;
public:
    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }
    void DFS(int v, vector<bool>& visited) {
        visited[v] = true;
        cout << v << " ";
        for (int i : adj[v]) {
            if (!visited[i]) {
                DFS(i, visited);
            }
        }
    }
};

int main() {
    int V = 5;
    Graph g(V);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, );
    g.addEdge(1, 4);
    vector<bool> visited(V, false);
    g.DFS(0, visited);
    return 0;
}

在这个示例中：

• Graph 类表示图，V 是顶点数量，adj 是邻接表，用于存储每个顶点的邻接顶点。
• addEdge 函数用于向图中添加边，将一个顶点的邻接顶点添加到其对应的邻接表中。
• DFS 函数实现了深度优先遍历。它接受一个顶点索引 v 和一个用于记录访问状态的向量 visited。首先将当前顶点标记为已访问，然后输出当前顶点，接着遍历当前顶点的所有邻接顶点。对于未访问的邻接顶点，递归调用 DFS 函数进行深度优先遍历。
• 在 main 函数中，创建了一个有 5 个顶点的图，添加了一些边，初始化了访问向量，然后从顶点 0 开始进行深度优先遍历。

4. 优势和应用场景

优势

• 代码简洁直观：对于熟悉递归思想的开发者来说，递归实现的深度优先遍历代码结构相对简单，易于理解和实现。
• 自然地反映深度优先的思想：递归调用的过程很好地模拟了不断深入图的过程，符合深度优先遍历的逻辑。

应用场景

• 图的连通性判断：可以判断一个图是否是连通图，或者出图中的连通分量。
• 拓扑排序（对于有向无环图）：在对有向无环图进行拓扑排序时，深度优先遍历是一种常用的基础算法。
• 寻路径：用于在图中寻从一个节点到另一个节点的路径，如在迷宫求解等问题中，将迷宫看作一个图，使用深度优先遍历寻从起点到终点的路径。

广度优先遍历

1. 定义

• 广度优先遍历（Breadth - First Search，简称 BFS）是一种图的遍历算法。它从给定的起始顶点开始，按照与起始顶点的距离远近，一层一层地向外扩展遍历图中的顶点，直到图中的所有顶点都被访问。在遍历过程中，先访问距离起始顶点距离为 1 的顶点，再访问距离为 2 的顶点，以此类推。

2. 工作原理

初始化

• 首先，将起始顶点标记为已访问，并且将其放入一个队列（Queue）中。队列是一种先进先出（FIFO）的数据结构，这保证了在遍历过程中先访问先加入的顶点的邻接顶点。

迭代过程

• 当队列不为空时，取出队首顶点，访问该顶点，然后遍历这个顶点的所有邻接顶点。对于每个未被访问的邻接顶点，将其标记为已访问，并放入队列中。
• 这样，每次从队列中取出的顶点都是按照距离起始顶点的层次顺序进行的，先处理离起始顶点近的顶点，再逐渐处理更远的顶点。
• 例如，在一个简单的图中，从顶点 A 开始进行广度优先遍历。A 被放入队列，然后取出 A，访问 A 并将 A 的邻接顶点 B、C 放入队列；接着取出 B，访问 B 并将 B 的邻接顶点 D、E 放入队列（如果 D、E 未被访问），以此类推，直到队列为空。

. 示例代码（以简单图的邻接表表示为例）

以下是一个简单的 C++ 代码示例，用于对一个图进行广度优先遍历：

代码语言：javascript代码运行次数：0运行复制

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

class Graph {
private:
    int V;
    vector<vector<int>> adj;
public:
    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }
    void BFS(int start) {
        vector<bool> visited(V, false);
        queue<int> q;
        visited[start] = true;
        q.push(start);
        while (!()) {
            int v = q.front();
            q.pop();
            cout << v << " ";
            for (int i : adj[v]) {
                if (!visited[i]) {
                    visited[i] = true;
                    q.push(i);
                }
            }
        }
    }
};

int main() {
    int V = 6;
    Graph g(V);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, );
    g.addEdge(1, 4);
    g.addEdge(2, 4);
    g.addEdge(, 5);
    g.addEdge(4, 5);
    g.BFS(0);
    return 0;
}

在这个示例中：

• Graph 类表示图，V 是顶点数量，adj 是邻接表，用于存储每个顶点的邻接顶点。
• addEdge 函数用于向图中添加边，将一个顶点的邻接顶点添加到其对应的邻接表中。
• BFS 函数实现了广度优先遍历。它接受一个起始顶点索引 start。首先创建一个用于记录访问状态的向量 visited 和一个队列 q，将起始顶点标记为已访问并放入队列。在循环中，只要队列不为空，就取出队首顶点，访问该顶点，然后遍历它的邻接顶点。对于未被访问的邻接顶点，标记为已访问并放入队列。
• 在 main 函数中，创建了一个有 6 个顶点的图，添加了一些边，然后从顶点 0 开始进行广度优先遍历。

4. 优势和应用场景

优势

• 到最短路径：在无权图（边没有权重的图）中，广度优先遍历可以到从起始顶点到其他顶点的最短路径长度。因为它是按照距离层次进行遍历的，第一次访问到某个顶点时的路径长度就是最短路径长度。
• 均匀地搜索图：相比于深度优先遍历可能会沿着一条路径深入而忽略其他部分，广度优先遍历可以比较均匀地搜索图，对图的整体结构有更好的探索效果。

应用场景

• 最短路径问题（无权图）：如在社交网络中寻两个人之间的最短关系链，或者在迷宫中寻从起点到终点的最短路径（将迷宫看作一个图）。
• 网络爬虫：广度优先遍历可以用于网络爬虫中，从一个起始网页开始，一层一层地爬取链接页面，先爬取离起始网页近的链接，再逐渐向外扩展。
• 连通分量计算：和深度优先遍历一样，也可以用于计算图的连通分量，不过广度优先遍历是按照层次来划分的。

带权有向图 带权有向图如下图所示，要求指定初始点，从初始点出发进行图的遍历。

---

测试说明

平台会对你编写的代码进行测试：

测试输入：

代码语言：javascript代码运行次数：0运行复制

0

预期输出：

代码语言：javascript代码运行次数：0运行复制

从顶点0开始的DFS:
  0  1  2  5  4  
从顶点0开始的BFS:
  0  1    2  5  4

【提示：输出遍历顶点的格式为 printf("%d",v);】

开始你的任务吧，祝你成功！

---

通关代码代码语言：javascript代码运行次数：0运行复制

#include <iostream>  
#include <vector>  
#include <queue>  
#include <stack>  
#include <algorithm> // 用于sort  

using namespace std;  

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

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

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

    // 深度优先遍历  
    void DFS(int start) {  
        vector<bool> visited(V, false); // 访问标记  
        stack<int> s; // 使用栈实现DFS  

        s.push(start);  
        cout << "从顶点" << start << "开始的DFS:\n";  

        while (!()) {  
            int v = ();  
            s.pop();  

            if (!visited[v]) {  
                visited[v] = true;  
                printf("%d", v); // 输出顶点  
            }  

            // 遍历邻接节点，逆序入栈  
            for (int i = adj[v].size() - 1; i >= 0; --i) {  
                int neighbor = adj[v][i];  
                if (!visited[neighbor]) {  
                    s.push(neighbor);  
                }  
            }  
        }  
        cout << endl;  
    }  

    // 广度优先遍历  
    void BFS(int start) {  
        vector<bool> visited(V, false); // 访问标记  
        queue<int> q; // 使用队列实现BFS  

        q.push(start);  
        visited[start] = true;  
        cout << "从顶点" << start << "开始的BFS:\n";  

        while (!()) {  
            int v = q.front();  
            q.pop();  

            printf("%d", v); // 输出顶点  

            // 遍历邻接节点  
            for (int neighbor : adj[v]) {  
                if (!visited[neighbor]) {  
                    visited[neighbor] = true;  
                    q.push(neighbor);  
                }  
            }  
        }  
        cout << endl;  
    }  

    // 函数：排序邻接表  
    void sortAdjacencyList() {  
        for (int i = 0; i < V; ++i) {  
            sort(adj[i].begin(), adj[i].end()); // 对每个邻接链表进行排序  
        }  
    }  
};  

int main() {  
    int V = 6; // 顶点数量  
    Graph g(V);  

    // 添加边 (u, v)  
    g.addEdge(5, 4);
    g.addEdge(4, );
    g.addEdge(, 2);
    g.addEdge(2, 0);    
    g.addEdge(0, 1);  
    g.addEdge(0, );  
    g.addEdge(1, 2);  
    g.addEdge(, 5);  
    g.addEdge(2, 5);  
    g.addEdge(5, 0);  
    

    // 手动控制邻接表的顺序  
    g.sortAdjacencyList();  

    int startVertex;  
    cin >> startVertex;  

    // 进行深度优先遍历和广度优先遍历  
    g.DFS(startVertex);  
    g.BFS(startVertex);  

    return 0;  
}

---

测试结果

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-12-25，如有侵权请联系 cloudcommunity@tencent 删除前往查看递归队列c++数据结构遍历