void BFS(const Graph& g, int start)//广度遍历 { bool visited[199] = { false }; // 标记顶点是否被访问过 //定义一个q队列（直接引用现有的库） std::queue<int> m; m.push(start); visited[start] = true; while (!m.empty()) {//直到把队列清空 int v = m.front(); m.pop(); // 处理顶点v std::cout << g.vexs[v].city << " "; // 遍历v的邻接顶点 for (int w = 0; w < g.vexnum; ++w) { if (g.arcs[v][w].cost != 1975 && !visited[w]) { m.push(w); visited[w] = true; } } } }

这段代码是广度优先搜索算法的实现，用来遍历图中所有的顶点。该函数接收两个参数：图g和起始顶点的下标start。首先，定义一个bool类型的数组visited来标记每个顶点是否被访问过，其中所有元素初始值为false。然后定义一个std::queue<int>类型的队列m，将起始顶点的下标压入队列中，并将visited数组中该顶点的值标记为true。接下来，进入while循环，直到队列m为空为止。在循环中，先将队头元素v取出来，打印出该顶点的城市名。然后遍历该顶点的所有邻接顶点，如果邻接顶点w没有被访问过且存在一条从顶点v到顶点w的路径，就将其压入队列中，并将visited数组中该顶点的值标记为true。最终遍历完整个图。

相关问题

#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;
}

（1）创建图和实现图的深度优先遍历和广度优先遍历 a.所输入的数据要为整形数据 b.输出的形式为：每按一次回车，遍历一个结点。 c.实现对无向图的两种遍历：深度优先遍历和广度优先遍历。 程序流程： main()visited()DFS()visited()BFS()

以下是一个基于邻接矩阵的实现示例：

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

const int MAXN = 100;
int graph[MAXN][MAXN];  // 邻接矩阵
bool visited[MAXN];     // 记录结点是否被访问过

// 深度优先遍历
void DFS(int cur) {
    cout << cur << endl;
    visited[cur] = true;
    for (int i = 0; i < MAXN; i++) {
        if (graph[cur][i] && !visited[i]) {
            DFS(i);
        }
    }
}

// 广度优先遍历
void BFS(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        cout << cur << endl;
        for (int i = 0; i < MAXN; i++) {
            if (graph[cur][i] && !visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
}

int main() {
    // 初始化邻接矩阵
    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < MAXN; j++) {
            graph[i][j] = 0;
        }
        visited[i] = false;
    }

    // 添加边
    graph[0][1] = graph[1][0] = 1;
    graph[0][2] = graph[2][0] = 1;
    graph[1][3] = graph[3][1] = 1;
    graph[1][4] = graph[4][1] = 1;
    graph[2][4] = graph[4][2] = 1;
    graph[3][4] = graph[4][3] = 1;

    cout << "DFS:" << endl;
    DFS(0);

    for (int i = 0; i < MAXN; i++) {
        visited[i] = false;
    }

    cout << "BFS:" << endl;
    BFS(0);

    return 0;
}

其中，我们使用一个 `visited` 数组来记录结点是否被访问过，以避免重复访问。在深度优先遍历中，我们先访问当前结点，然后对于每个未访问的相邻结点，递归调用 `DFS` 函数进行遍历。在广度优先遍历中，我们使用一个队列来记录待访问的结点，从起始结点开始，先访问当前结点，然后将其相邻的未访问结点全部加入队列中。重复这个过程，直到队列为空。