来一个C++广度优先搜索的实例

下面是一个使用C语言实现广度优先搜索的例子，用于寻找一个有向图中两个节点之间的最短路径：

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

// 定义有向图节点的结构体
typedef struct node {
    int data;
    struct node* next;
} Node;

// 创建一个新的节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 添加一条从源节点到目标节点的边
void addEdge(Node* adjList[], int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = adjList[src];
    adjList[src] = newNode;
}

// 执行广度优先搜索
void BFS(Node* adjList[], int source, int dest, int numVertices) {
    bool visited[numVertices];  // 记录节点是否已经被访问过
    int distance[numVertices];  // 记录每个节点到源节点的距离
    int parent[numVertices];    // 记录每个节点在最短路径中的前一个节点
    for (int i = 0; i < numVertices; i++) {
        visited[i] = false;
        distance[i] = -1;
        parent[i] = -1;
    }
    visited[source] = true;
    distance[source] = 0;

    Node* queue = createNode(source);  // 创建一个队列来存储待访问的节点
    while (queue != NULL) {
        int current = queue->data;  // 取出队列头部的节点
        queue = queue->next;
        Node* neighbor = adjList[current];
        while (neighbor != NULL) {
            int next = neighbor->data;
            if (!visited[next]) {  // 如果该节点还没有被访问过
                visited[next] = true;
                distance[next] = distance[current] + 1;
                parent[next] = current;
                if (next == dest) {  // 如果找到了目标节点，立即退出函数
                    printf("Shortest path length is %d\n", distance[dest]);
                    printf("Path is: %d", dest);
                    int p = parent[dest];
                    while (p != -1) {
                        printf(" <- %d", p);
                        p = parent[p];
                    }
                    return;
                }
                Node* newNode = createNode(next);
                newNode->next = queue;
                queue = newNode;
            }
            neighbor = neighbor->next;
        }
    }
    printf("No path found between %d and %d\n", source, dest);
}

int main() {
    int numVertices = 6;
    Node* adjList[numVertices];
    for (int i = 0; i < numVertices; i++) {
        adjList[i] = NULL;
    }
    addEdge(adjList, 0, 1);
    addEdge(adjList, 0, 2);
    addEdge(adjList, 1, 2);
    addEdge(adjList, 2, 3);
    addEdge(adjList, 3, 4);
    addEdge(adjList, 4, 1);
    addEdge(adjList, 4, 5);
    BFS(adjList, 0, 5, numVertices);
    return 0;
}

在上述例子中，我们使用了一个邻接表来表示有向图。邻接表是一个数组，其中每个元素都是一个链表，链表中存储了该节点可以到达的其他节点。

在BFS函数中，我们首先初始化了visited、distance和parent数组。我们将源节点的visited值设为true，distance值设为0，然后将源节点添加到队列中。接下来，我们开始遍历队列，每次取出队列头部的节点，并访问它的所有邻居节点。如果某个邻居节点还没有被访问过，我们将它的visited值设为true，将它的distance值设为当前节点的distance值加1，将它的parent值设为当前节点，然后将它添加到队列中。如果我们在访问某个邻居节点时发现它已经是目标节点了，那么我们就可以退出函数，输出最短路径长度和路径本身。

在本例中，我们使用邻接表来表示有向图。邻接表是一种空间效率比邻接矩阵更高的数据结构，特别适合表示稀疏图。在邻接表中，我们只为每个节点存储它可以到达的其他节点，而不是存储整个图的矩阵。这种方法使得我们可以用O(V+E)的时间复杂度来表示一个有V个节点和E条边的图，其中V是节点数，E是边数。