C语言bfs最短路径代码

下面是一个C语言实现的BFS最短路径代码（假设图的邻接表表示如下）：

#include <stdio.h>
#include <stdlib.h>
#define MAXV 1000  // 最大节点数

typedef struct Node *PtrToNode;
struct Node {
    int v;
    PtrToNode next;
};
typedef PtrToNode Graph[MAXV];

typedef struct {
    int data[MAXV];
    int front, rear;
} Queue;

int visited[MAXV];  // 访问标志数组

// 初始化图
Graph createGraph(int n) {
    int i;
    Graph graph = (Graph)malloc(sizeof(struct Node) * n);
    for (i = 0; i < n; i++) {
        graph[i] = (PtrToNode)malloc(sizeof(struct Node));
        graph[i]->v = i;
        graph[i]->next = NULL;
    }
    return graph;
}

// 添加边
void addEdge(Graph graph, int start, int end) {
    PtrToNode node = (PtrToNode)malloc(sizeof(struct Node));
    node->v = end;
    node->next = graph[start]->next;
    graph[start]->next = node;
}

// 初始化队列
void initQueue(Queue *queue) {
    queue->front = queue->rear = 0;
}

// 判断队列是否为空
int emptyQueue(Queue *queue) {
    return queue->front == queue->rear;
}

// 入队
void enQueue(Queue *queue, int x) {
    queue->data[queue->rear++] = x;
}

// 出队
int deQueue(Queue *queue) {
    return queue->data[queue->front++];
}

// BFS
void BFS(Graph graph, int start, int n) {
    int v, w;
    Queue queue;
    PtrToNode p;
    initQueue(&queue);
    visited[start] = 1;
    enQueue(&queue, start);
    while (!emptyQueue(&queue)) {
        v = deQueue(&queue);
        printf("%d ", v);
        p = graph[v]->next;
        while (p) {
            w = p->v;
            if (!visited[w]) {
                visited[w] = 1;
                enQueue(&queue, w);
            }
            p = p->next;
        }
    }
}

int main() {
    int n, m, i, start, end;
    Graph graph;
    scanf("%d %d", &n, &m);
    graph = createGraph(n);
    for (i = 0; i < m; i++) {
        scanf("%d %d", &start, &end);
        addEdge(graph, start, end);
        addEdge(graph, end, start);
    }
    scanf("%d", &start);
    BFS(graph, start, n);
    return 0;
}

在本例中，我们使用邻接表表示图，并使用一个队列来实现BFS算法。具体而言，我们假设图中有`n`个节点和`m`条边，`createGraph(n)`函数用于初始化图，`addEdge(graph, start, end)`函数用于向图中添加一条从`start`节点到`end`节点的边，`BFS(graph, start, n)`函数用于执行BFS算法，其中`start`表示起点。在BFS算法中，我们从起点开始遍历整张图，一旦发现一个未被访问的节点，就将其加入队列中。当队列为空时，遍历结束，所有可到达的节点都被访问了一遍。