//void BFS(Graph& g, vector<bool>& visited, int v) { // queue<int> q; // visited[v] = true; // q.push(v); // while (!q.empty()) { // int u = q.front(); // q.pop(); // cout << u << " "; // for (int i = 0; i < g.adj[u].size(); i++) { // int w = g.adj[u][i]; // if (!visited[w]) { // visited[w] = true; // q.push(w); // }

这段代码是一个基于BFS（广度优先搜索）算法的遍历图的实现。其中，Graph是一个图的数据结构，visited是一个bool类型的数组，用于标记节点是否被访问过。v是起始节点，q是一个队列，用于存储待访问的节点。

具体实现过程如下：

1. 将起始节点v标记为已访问，并将其加入队列q中。
2. 当队列q非空时，取出队首节点u，并输出其信息。
3. 遍历节点u的所有邻居节点，若其未被访问过，则标记为已访问，并将其加入队列q中。
4. 重复步骤2和步骤3，直到队列q为空，即所有节点均被访问过。

该算法的时间复杂度为O(V+E)，其中V为节点数，E为边数。

相关问题

#include <iostream> #include <vector> #include <queue> using namespace std; // 定义图的边结构体 struct Edge { int to; // 边的终点 int weight; // 边的权重 Edge(int t, int w) : to(t), weight(w) {} }; // 定义图的邻接表结构体 struct Graph { int n; // 节点数 vector<vector<Edge>> adj; // 邻接表 Graph(int n) : n(n), adj(n) {} // 添加一条边 void addEdge(int from, int to, int weight) { adj[from].push_back(Edge(to, weight)); } // 深度优先遍历 void dfs(int cur, vector<bool>& visited) { visited[cur] = true; cout << cur << " "; for (auto e : adj[cur]) { if (!visited[e.to]) { dfs(e.to, visited); } } } // 广度优先遍历 void bfs(int cur, vector<bool>& visited) { queue<int> q; q.push(cur); visited[cur] = true; while (!q.empty()) { int u = q.front(); q.pop(); cout << u << " "; for (auto e : adj[u]) { if (!visited[e.to]) { visited[e.to] = true; q.push(e.to); } } } } }; int main() { int n, m; cin >> n >> m; Graph g(n); for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; g.addEdge(u, v, w); g.addEdge(v, u, w); // 无向图需要添加反向边 } // 深度优先遍历 cout << "DFS: "; vector<bool> visited(n, false); g.dfs(0, visited); cout << endl; // 广度优先遍历 cout << "BFS: "; visited.assign(n, false); g.bfs(0, visited); cout << endl; return 0; }给代码添加注释

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

// 定义图的边结构体
struct Edge {
    int to;     // 边的终点
    int weight; // 边的权重
    Edge(int t, int w) : to(t), weight(w) {} // 构造函数
};

// 定义图的邻接表结构体
struct Graph {
    int n;                  // 节点数
    vector<vector<Edge>> adj; // 邻接表
    Graph(int n) : n(n), adj(n) {} // 构造函数

    // 添加一条边
    void addEdge(int from, int to, int weight) {
        adj[from].push_back(Edge(to, weight));
    }

    // 深度优先遍历
    void dfs(int cur, vector<bool>& visited) {
        visited[cur] = true;
        cout << cur << " ";
        for (auto e : adj[cur]) {
            if (!visited[e.to]) {
                dfs(e.to, visited);
            }
        }
    }

    // 广度优先遍历
    void bfs(int cur, vector<bool>& visited) {
        queue<int> q;
        q.push(cur);
        visited[cur] = true;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            cout << u << " ";
            for (auto e : adj[u]) {
                if (!visited[e.to]) {
                    visited[e.to] = true;
                    q.push(e.to);
                }
            }
        }
    }
};

int main() {
    int n, m;
    cin >> n >> m;

    Graph g(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g.addEdge(u, v, w);
        g.addEdge(v, u, w); // 无向图需要添加反向边
    }

    // 深度优先遍历
    cout << "DFS: ";
    vector<bool> visited(n, false);
    g.dfs(0, visited);
    cout << endl;

    // 广度优先遍历
    cout << "BFS: ";
    visited.assign(n, false);
    g.bfs(0, visited);
    cout << endl;

    return 0;
}

注释已添加在代码中。

#include<iostream> #include<queue> #include<vector> using namespace std; // 定义图的邻接表结构 struct edge { int dest; edge* next; }; struct vertex { edge* head; }; // 图类 class Graph { private: int V; // 顶点数 vertex* adj; // 邻接表 public: Graph(int V) { this->V = V; adj = new vertex[V]; for (int i = 0; i < V; ++i) { adj[i].head = nullptr; } } // 添加边 void addEdge(int src, int dest) { edge* e = new edge; e->dest = dest; e->next = adj[src].head; adj[src].head = e; } // 深度优先遍历 void DFS(int v, bool* visited) { visited[v] = true; cout << v << " "; edge* e = adj[v].head; while (e != nullptr) { if (!visited[e->dest]) { DFS(e->dest, visited); } e = e->next; } } // 广度优先遍历 void BFS(int v, bool* visited) { queue<int> q; visited[v] = true; q.push(v); while (!q.empty()) { int u = q.front(); q.pop(); cout << u << " "; edge* e = adj[u].head; while (e != nullptr) { if (!visited[e->dest]) { visited[e->dest] = true; q.push(e->dest); } e = e->next; } } } }; int main() { int V, E; cout << "请输入顶点数和边数：" << endl; cin >> V >> E; Graph g(V); cout << "请输入每条边的起点和终点：" << endl; for (int i = 0; i < E; ++i) { int src, dest; cin >> src >> dest; g.addEdge(src, dest); } // 深度优先遍历 cout << "深度优先遍历结果为：" << endl; bool* visited = new bool[V]; for (int i = 0; i < V; ++i) { visited[i] = false; } for (int i = 0; i < V; ++i) { if (!visited[i]) { g.DFS(i, visited); } } cout << endl; // 广度优先遍历 cout << "广度优先遍历结果为：" << endl; for (int i = 0; i < V; ++i) { visited[i] = false; } for (int i = 0; i < V; ++i) { if (!visited[i]) { g.BFS(i, visited); } } cout << endl; return 0; }这段代码从输入数字修改为输入为字母

将输入数字修改为输入字母需要对代码进行一定的修改，因为字母无法直接转化为整数进行处理。以下是修改后的代码：

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

// 定义图的邻接表结构
struct edge {
    char dest;
    edge* next;
};

struct vertex {
    edge* head;
};

// 图类
class Graph {
private:
    int V; // 顶点数
    vertex* adj; // 邻接表
    map<char, int> charToInt; // 将字母映射为数字
public:
    Graph(int V) {
        this->V = V;
        adj = new vertex[V];
        for (int i = 0; i < V; ++i) {
            adj[i].head = nullptr;
        }
    }

    // 添加边
    void addEdge(char src, char dest) {
        // 将字母映射为数字
        int srcInt, destInt;
        if (charToInt.count(src) == 0) {
            srcInt = charToInt.size();
            charToInt[src] = srcInt;
        } else {
            srcInt = charToInt[src];
        }
        if (charToInt.count(dest) == 0) {
            destInt = charToInt.size();
            charToInt[dest] = destInt;
        } else {
            destInt = charToInt[dest];
        }

        edge* e = new edge;
        e->dest = destInt;
        e->next = adj[srcInt].head;
        adj[srcInt].head = e;
    }

    // 深度优先遍历
    void DFS(int v, bool* visited) {
        visited[v] = true;
        // 将数字映射为字母输出
        for (auto it = charToInt.begin(); it != charToInt.end(); ++it) {
            if (it->second == v) {
                cout << it->first << " ";
                break;
            }
        }
        edge* e = adj[v].head;
        while (e != nullptr) {
            if (!visited[e->dest]) {
                DFS(e->dest, visited);
            }
            e = e->next;
        }
    }

    // 广度优先遍历
    void BFS(int v, bool* visited) {
        queue<int> q;
        visited[v] = true;
        q.push(v);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            // 将数字映射为字母输出
            for (auto it = charToInt.begin(); it != charToInt.end(); ++it) {
                if (it->second == u) {
                    cout << it->first << " ";
                    break;
                }
            }
            edge* e = adj[u].head;
            while (e != nullptr) {
                if (!visited[e->dest]) {
                    visited[e->dest] = true;
                    q.push(e->dest);
                }
                e = e->next;
            }
        }
    }
};

int main() {
    int V, E;
    cout << "请输入顶点数和边数：" << endl;
    cin >> V >> E;
    Graph g(V);
    cout << "请输入每条边的起点和终点：" << endl;
    for (int i = 0; i < E; ++i) {
        char src, dest;
        cin >> src >> dest;
        g.addEdge(src, dest);
    }

    // 深度优先遍历
    cout << "深度优先遍历结果为：" << endl;
    bool* visited = new bool[V];
    for (int i = 0; i < V; ++i) {
        visited[i] = false;
    }
    for (int i = 0; i < V; ++i) {
        if (!visited[i]) {
            g.DFS(i, visited);
        }
    }
    cout << endl;

    // 广度优先遍历
    cout << "广度优先遍历结果为：" << endl;
    for (int i = 0; i < V; ++i) {
        visited[i] = false;
    }
    for (int i = 0; i < V; ++i) {
        if (!visited[i]) {
            g.BFS(i, visited);
        }
    }
    cout << endl;

    return 0;
}