广度优先遍历求无向图的最短路径c语言

广度优先搜索可以求解无向图的最短路径，具体步骤如下：

1. 定义一个队列，将起始节点加入队列中。
2. 定义一个数组，记录每个节点是否被访问过，起始节点标记为已访问。
3. 定义一个数组，记录每个节点到起始节点的距离，起始节点的距离为0。
4. 对队列中的节点进行遍历，将与该节点相邻且未访问过的节点加入队列中，并更新它们到起始节点的距离。
5. 将已经遍历过的节点标记为已访问。
6. 重复步骤4和5，直到队列为空。

下面是一个求解无向图最短路径的C语言代码示例：

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

#define MAX_VERTICES 100

typedef struct Graph {
    int num_vertices;
    int adj_matrix[MAX_VERTICES][MAX_VERTICES];
} Graph;

typedef struct QueueNode {
    int data;
    struct QueueNode* next;
} QueueNode;

typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
} Queue;

Graph* createGraph(int num_vertices);
void addEdge(Graph* graph, int src, int dest);
Queue* createQueue();
void enqueue(Queue* queue, int data);
int dequeue(Queue* queue);
bool isQueueEmpty(Queue* queue);
bool isVisited[MAX_VERTICES];
int distances[MAX_VERTICES];

int main() {
    Graph* graph = createGraph(6);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);
    addEdge(graph, 4, 5);

    Queue* queue = createQueue();
    enqueue(queue, 0);
    isVisited[0] = true;
    distances[0] = 0;

    while (!isQueueEmpty(queue)) {
        int current_node = dequeue(queue);
        for (int i = 0; i < graph->num_vertices; i++) {
            if (graph->adj_matrix[current_node][i] && !isVisited[i]) {
                enqueue(queue, i);
                isVisited[i] = true;
                distances[i] = distances[current_node] + 1;
            }
        }
    }

    for (int i = 0; i < graph->num_vertices; i++) {
        printf("Distance from node 0 to node %d is %d\n", i, distances[i]);
    }

    return 0;
}

Graph* createGraph(int num_vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->num_vertices = num_vertices;
    for (int i = 0; i < num_vertices; i++) {
        for (int j = 0; j < num_vertices; j++) {
            graph->adj_matrix[i][j] = 0;
        }
    }
    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    graph->adj_matrix[src][dest] = 1;
    graph->adj_matrix[dest][src] = 1;
}

Queue* createQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = NULL;
    queue->rear = NULL;
    return queue;
}

void enqueue(Queue* queue, int data) {
    QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
    new_node->data = data;
    new_node->next = NULL;
    if (queue->rear == NULL) {
        queue->front = new_node;
        queue->rear = new_node;
    } else {
        queue->rear->next = new_node;
        queue->rear = new_node;
    }
}

int dequeue(Queue* queue) {
    if (queue->front == NULL) {
        return -1;
    }
    int data = queue->front->data;
    QueueNode* temp = queue->front;
    queue->front = queue->front->next;
    free(temp);
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    return data;
}

bool isQueueEmpty(Queue* queue) {
    return queue->front == NULL;
}

这个代码的输出结果应该是：

Distance from node 0 to node 0 is 0
Distance from node 0 to node 1 is 1
Distance from node 0 to node 2 is 1
Distance from node 0 to node 3 is 2
Distance from node 0 to node 4 is 3
Distance from node 0 to node 5 is 4