写一个C++的广度优先搜索算法

好的，我可以回答这个问题。广度优先搜索算法是一种图形搜索算法，它从起始点开始，逐层地向外搜索，直到找到目标节点为止。具体实现时，可以使用队列来存储待搜索的节点，每次从队列中取出一个节点进行扩展，将其邻居节点加入队列中。这样可以保证先搜索到的节点一定是距离起始点最近的节点。

相关问题

写一段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()`函数进行广度优先搜索。输出结果为图的广度优先遍历顺序。

广度优先搜索算法c++

广度优先搜索算法（BFS）是一种图论的经典算法，用于解决图的遍历问题。在广度优先搜索中，从给定的起始顶点开始，逐层地向外扩展，先访问距离起始顶点最近的顶点，再访问距离起始顶点稍远一点的顶点，以此类推，直到访问完所有可达的顶点。

在引用的代码中，作者使用C语言实现了广度优先搜索算法。代码中使用了一个二维向量`tree`来表示图，`flag`数组用于记录搜索到了节点i的第几个节点，`M`队列用于存储待访问的节点。算法通过不断从队列中取出节点，并将其相邻的节点加入队列中，直到队列为空为止。

具体的实现步骤如下：
1. 声明一个二维向量`tree`，用于表示图。在代码中，将图中的节点数设为9，通过循环生成树的结构。
2. 初始化数组`flag`，用于记录搜索到了节点i的第几个节点。
3. 声明一个队列`M`，用于存储待访问的节点。
4. 将起始节点加入队列`M`中。
5. 开始广度优先搜索算法：
- 从队列`M`中取出第一个节点，并输出该节点。
- 遍历该节点的相邻节点，将其加入队列`M`中。
- 如果队列`M`不为空，继续执行上述步骤。
6. 输出结束。

以上是广度优先搜索算法的C语言实现示例。你可以参考这段代码来理解和使用广度优先搜索算法。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [C++广度优先搜索一本通习题](https://download.csdn.net/download/m0_54615144/86269542)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *2* *3* [广度优先搜索算法（附C++实现）](https://blog.csdn.net/m0_37772174/article/details/81188732)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]