写一段广度优先搜索的代码

答：def bfs(graph, start):
visited = set()
queue = [start]

while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)

return visited

相关问题

写一段c语言广度优先搜索的代码

当我在前面对你说了什么时，为了让你更好地了解人工智能，我给你讲个笑话：为什么人工智能会成为最懒的工程师？因为它只需要输入一次代码，就可以无限复制自己！现在回答你的问题，以下是一段基于C语言的广度优先搜索代码：

#include <stdio.h>
#define MAXSIZE 100    // 定义队列最大长度

int visited[MAXSIZE];   // 定义访问标记数组
int matrix[MAXSIZE][MAXSIZE];   // 定义邻接矩阵存储图

void BFSTraverse(int G[][MAXSIZE], int n, int v)
{
    int queue[MAXSIZE];   // 定义队列
    int front = 0, rear = 0;   // 队列指针
    int i, j, k;

    // 初始化访问标记数组
    for (i = 0; i < n; i++)
        visited[i] = 0;

    // 将起始顶点v入队，标记为已访问
    queue[rear++] = v;
    visited[v] = 1;

    // 开始进行广度优先搜索
    while (front != rear) {
        // 从队头出队一个顶点，打印并记录访问
        i = queue[front++];
        printf("%d ", i);

        // 将所有未访问的邻接顶点入队，标记为已访问
        for (j = 0; j < n; j++) {
            if (G[i][j] == 1 && visited[j] == 0) {
                queue[rear++] = j;
                visited[j] = 1;
            }
        }
    }
}

int main()
{
    int n, e, i, j, k;

    // 读入顶点数和边数
    printf("请输入图的顶点数和边数：");
    scanf("%d %d", &n, &e);

    // 初始化邻接矩阵
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            matrix[i][j] = 0;
        }
    }

    // 读入每条边并构建邻接矩阵
    printf("请输入每条边（按“起点 终点”格式）：\n");
    for (k = 0; k < e; k++) {
        scanf("%d %d", &i, &j);
        matrix[i][j] = 1;
        matrix[j][i] = 1;
    }

    // 从顶点0开始进行广度优先搜索
    printf("\n从顶点0开始遍历：\n");
    BFSTraverse(matrix, n, 0);

    return 0;
}

写一段c++ 广度优先搜索的代码

### 回答1：
好的，下面是一段用 C 语言实现的广度优先搜索代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 100
#define MAX_NEIGHBORS 100

int n;  // number of nodes
int m;  // number of edges
int adjacency_matrix[MAX_NODES][MAX_NEIGHBORS];  // adjacency matrix to store the graph
int visited[MAX_NODES];  // an array to keep track of the visited nodes

void breadth_first_search(int start) {
    int queue[MAX_NODES];  // a queue to store the next node to be visited
    int head = 0;  // the head of the queue
    int tail = 0;  // the tail of the queue
    int current_node;  // the current node being processed
    int i;  // loop variable

    // initialize all nodes as not visited
    for (i = 0; i < n; i++) {
        visited[i] = 0;
    }

    // mark the starting node as visited
    visited[start] = 1;
    queue[tail] = start;
    tail++;

    // continue searching until the queue is empty
    while (head < tail) {
        current_node = queue[head];
        head++;
        for (i = 0; i < m; i++) {
            if (adjacency_matrix[current_node][i] == 1 && visited[i] == 0) {
                visited[i] = 1;
                queue[tail] = i;
                tail++;
            }
        }
    }
}

int main() {
    int i, j;  // loop variables
    int start;  // the starting node for the search

    // read the number of nodes and edges
    scanf("%d %d", &n, &m);

    // read the adjacency matrix
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            scanf("  

### 回答2：
广度优先搜索（BFS）是一种经典的图搜索算法，它从图的起始点开始，逐层地向外扩展，直到找到目标节点或者遍历完整个图。以下是一段用C语言编写的广度优先搜索算法的代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100 // 图的最大顶点数

typedef struct Node {
int vertex; // 顶点
struct Node* next; // 指向下一个邻接点的指针
} Node;

Node* graph[MAX_SIZE];
int visited[MAX_SIZE]; // 记录顶点是否被访问过

void initGraph() {
for (int i = 0; i < MAX_SIZE; i++) {
graph[i] = NULL;
visited[i] = 0;
}
}

void addEdge(int from, int to) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = to;
newNode->next = graph[from];
graph[from] = newNode;
}

void BFS(int start) {
int queue[MAX_SIZE];
int front = 0, rear = 0;

queue[rear++] = start;
visited[start] = 1;

while (front < rear) {
int vertex = queue[front++];

printf("%d ", vertex);

Node* currentNode = graph[vertex];

while (currentNode != NULL) {
int nextVertex = currentNode->vertex;

if (!visited[nextVertex]) {
queue[rear++] = nextVertex;
visited[nextVertex] = 1;
}

currentNode = currentNode->next;
}
}
}

int main() {
initGraph();

addEdge(0, 1);
addEdge(0, 2);
addEdge(1, 3);
addEdge(1, 4);
addEdge(2, 5);
addEdge(2, 6);
addEdge(3, 7);
addEdge(4, 7);
addEdge(5, 7);
addEdge(6, 7);

printf("BFS traversal: ");
BFS(0);

return 0;
}

该代码首先定义了一个图的数据结构，使用邻接表的方式表示图。`initGraph()`函数用于初始化图的邻接表和访问数组。`addEdge()`函数用于添加边到图中。`BFS()`函数实现了广度优先搜索算法，通过维护一个队列来逐层遍历图。最后，在`main()`函数中，我们创建了一个图，并调用了`BFS()`函数进行广度优先搜索。输出结果为图的广度优先遍历顺序。