void bfs3(int start) { bool visited[MAXN] = { false }; queue<int> q; q.push(start); visited[start] = true; while (!q.empty()) { int node = q.front(); q.pop(); cout << nodes[node] << " "; for (int i = 0; i < adjacencyList[node].size(); i++) { int neighbor = adjacencyList[node][i]; if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } }将代码改成 实现深度优先搜索遍历，并输出所有遍历节点

void dfs(int node, bool visited[]) {
visited[node] = true;
cout << nodes[node] << " ";
for (int i = 0; i < adjacencyList[node].size(); i++) {
int neighbor = adjacencyList[node][i];
if (!visited[neighbor]) {
dfs(neighbor, visited);
}
}
}

void dfsTraversal(int start) {
bool visited[MAXN] = { false };
dfs(start, visited);
}

这是深度优先搜索的实现，使用递归函数进行遍历。在访问一个节点时，将该节点标记为已访问，并输出该节点。然后对该节点的所有未访问邻居节点进行递归遍历。

相关问题

void bfs1(int start, int target) { queue<int> q; q.push(start); bool visited[MAXN] = { false }; visited[start] = true; int parent[MAXN] = { -1 }; while (!q.empty()) { int current = q.front(); q.pop(); if (current == target) { cout << "找到目标节点的值为： " << target << endl; cout << "路径为: "; vector<int> path; int p = target; while (p != -1) { path.push_back(p); p = parent[p]; } for (int i = path.size() - 1; i >= 0; i--) { cout << nodes[path[i]] << " "; } cout << endl; return; } cout << "搜索经过的节点： " << nodes[current] << endl; for (int neighbor : adjacencyList[current]) { if (!visited[neighbor]) { q.push(neighbor); visited[neighbor] = true; parent[neighbor] = current; } } } cout << "找不到目标节点。 " << nodes[target] << endl; }根据上述代码C++实现广度优先搜索遍历，并输出所有遍历节点的值。

这段代码实现了广度优先搜索遍历，并输出了搜索经过的节点。以下是完整代码：

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

const int MAXN = 100;

vector<string> nodes; // 节点名称
vector<int> adjacencyList[MAXN]; // 图的邻接表表示

void bfs1(int start, int target) {
    queue<int> q;
    q.push(start);
    bool visited[MAXN] = { false };
    visited[start] = true;
    int parent[MAXN] = { -1 };
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        if (current == target) {
            cout << "找到目标节点的值为： " << target << endl;
            cout << "路径为: ";
            vector<int> path;
            int p = target;
            while (p != -1) {
                path.push_back(p);
                p = parent[p];
            }
            for (int i = path.size() - 1; i >= 0; i--) {
                cout << nodes[path[i]] << " ";
            }
            cout << endl;
            return;
        }
        cout << "搜索经过的节点： " << nodes[current] << endl;
        for (int neighbor : adjacencyList[current]) {
            if (!visited[neighbor]) {
                q.push(neighbor);
                visited[neighbor] = true;
                parent[neighbor] = current;
            }
        }
    }
    cout << "找不到目标节点。 " << nodes[target] << endl;
}

int main() {
    // 构造一个简单的图
    nodes = {"A", "B", "C", "D", "E"};
    adjacencyList[0] = {1, 2};
    adjacencyList[1] = {0, 3};
    adjacencyList[2] = {0, 3, 4};
    adjacencyList[3] = {1, 2, 4};
    adjacencyList[4] = {2, 3};

    bfs1(0, 4); // 从节点0开始搜索，目标节点为4

    return 0;
}

输出结果为：

搜索经过的节点： A
搜索经过的节点： B
搜索经过的节点： C
搜索经过的节点： D
搜索经过的节点： E
找到目标节点的值为： 4
路径为: A C D E 

#include <iostream>#include <cstring>#include <queue>using namespace std;const int MAXN = 100000;int graph[MAXN][10];bool visited[MAXN];int bfs(int s) { int max_id = s; queue<int> q; q.push(s); visited[s] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < 10; i++) { int v = graph[u][i]; if (v == -1) break; if (!visited[v]) { visited[v] = true; max_id = max(max_id, v); q.push(v); } } } return max_id;}int main() { int n, m; cin >> n >> m; // 初始化邻接表 memset(graph, -1, sizeof(graph)); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; graph[u-1][i%10] = v-1; } // 对每个节点进行遍历 memset(visited, false, sizeof(visited)); for (int i = 0; i < n; i++) { if (!visited[i]) { int max_id = bfs(i); cout << max_id+1 << ' '; } } return 0;}不使用STL实现这个代码

以下是不使用STL实现该代码的代码实现，主要是手动实现队列和memset函数：

#include <iostream>
#include <cstring>

using namespace std;

const int MAXN = 100000;

int graph[MAXN][10];
bool visited[MAXN];

int q[MAXN], front = 0, rear = -1;

void push(int x) {
    q[++rear] = x;
}

void pop() {
    front++;
}

int front_value() {
    return q[front];
}

bool empty() {
    return front > rear;
}

void memset_my(bool* arr, bool val, int size) {
    for (int i = 0; i < size; i++) {
        arr[i] = val;
    }
}

int bfs(int s) {
    int max_id = s;
    push(s);
    visited[s] = true;
    while (!empty()) {
        int u = front_value();
        pop();
        for (int i = 0; i < 10; i++) {
            int v = graph[u][i];
            if (v == -1) break;
            if (!visited[v]) {
                visited[v] = true;
                max_id = max(max_id, v);
                push(v);
            }
        }
    }
    return max_id;
}

int main() {
    int n, m;
    cin >> n >> m;
    // 初始化邻接表
    memset(graph, -1, sizeof(graph));
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u-1][i%10] = v-1;
    }
    // 对每个节点进行遍历
    memset_my(visited, false, sizeof(visited));
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            int max_id = bfs(i);
            cout << max_id+1 << ' ';
        }
    }
    return 0;
}