图的表示与遍历 - C++ 数据结构与算法

← 返回课程C++ 数据结构与算法 › 第 5 关

进度 0%

第 5 关：图的表示与遍历

C++进阶

📖 本课目标

本关属于《C++ 数据结构与算法》第 5 课。阅读右侧代码模板，理解每一行的作用，然后动手修改并完成练习。

🎯 本课要点

include <iostream>
include <vector>
include <queue>

🛠 学习方式

阅读右侧代码模板中的注释与实现
修改代码，尝试达成新的效果
点击「运行」查看实际输出
确认理解后点击「提交」标记本关完成

💡 说明

本关为 C++，浏览器内无法真正执行该语言。当前「运行」输出为演示结果，请在本地环境中编译运行以验证代码。

main.pytest.py

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

class Graph {
    int V;
    vector<vector<int>> adj;
public:
    Graph(int v) : V(v), adj(v) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // BFS 广度优先搜索
    void bfs(int start) {
        vector<bool> visited(V, false);
        queue<int> q;
        visited[start] = true;
        q.push(start);
        
        cout << "BFS: ";
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            cout << v << " ";
            
            for (int neighbor : adj[v]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        cout << endl;
    }
    
    // DFS 深度优先搜索
    void dfs(int v, vector<bool>& visited) {
        visited[v] = true;
        cout << v << " ";
        for (int neighbor : adj[v]) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited);
            }
        }
    }
    
    void dfsStart(int start) {
        vector<bool> visited(V, false);
        cout << "DFS: ";
        dfs(start, visited);
        cout << endl;
    }
};

int main() {
    Graph g(6);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 5);
    
    g.bfs(0);
    g.dfsStart(0);
    
    return 0;
}

点击「运行」或「提交代码」查看结果

📖 查看本课说明

第 5 关：图的表示与遍历

C++ · 进阶 · 《C++ 数据结构与算法》

include <iostream>
include <vector>
include <queue>

本关为 C++，浏览器无法真正编译运行，请在本地环境验证代码。