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。最终遍历完整个图。

相关问题

void BFS(const Graph& g, int start)//广度遍历 { bool visited[199] = { false }; // 标记顶点是否被访问过 //定义一个q队列（直接引用现有的库） std::queue<int> q; q.push(start); visited[start] = true; while (!q.empty()) {//直到把队列清空 int v = q.front(); q.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]) { q.push(w); visited[w] = true; } } } }

这段代码是用来实现图的广度优先遍历算法的。其中，参数g表示待遍历的图，参数start表示遍历的起始顶点。该算法使用了一个bool类型的visited数组来标记每个顶点是否被访问过，初始值都为false。广度优先遍历使用了队列来存储待遍历的顶点，初始只有起始顶点start在队列中。在遍历过程中，每次从队列中取出队首元素v，并输出该顶点的信息。然后遍历v的所有邻接顶点w，如果w还没有被访问过，就将其加入队列中，并将visited[w]标记为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;
}