无向图的广度优先遍历c语言

以下是无向图的广度优先遍历的 C 语言实现：

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

#define MAX_VERTICES 100

typedef struct {
    int v;
    int w;
} Edge;

typedef struct {
    int n;
    Edge edges[MAX_VERTICES*MAX_VERTICES];
} Graph;

void init_graph(Graph* g, int n) {
    int i;
    g->n = n;
    for (i = 0; i < n*n; i++)
        g->edges[i].v = -1;
}

void add_edge(Graph* g, int u, int v, int w) {
    int i;
    for (i = 0; i < g->n*g->n; i++) {
        if (g->edges[i].v < 0) {
            g->edges[i].v = u;
            g->edges[i].w = w;
            g->edges[i+1].v = v;
            g->edges[i+1].w = w;
            return;
        }
    }
    printf("Too many edges\n");
}

int bfs(Graph* g, int start_vertex, int target_vertex) {
    int queue[MAX_VERTICES];
    int visited[MAX_VERTICES] = { 0 };
    int front = 0, rear = 0;
    int v, i;

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

    while (front != rear) {
        v = queue[front++];
        if (v == target_vertex)
            return 1;

        for (i = 0; i < g->n*g->n; i++) {
            if (g->edges[i].v == v && !visited[g->edges[i].w]) {
                queue[rear++] = g->edges[i].w;
                visited[g->edges[i].w] = 1;
            }
        }
    }

    return 0;
}

int main() {
    Graph g;
    int n = 5;

    init_graph(&g, n);
    add_edge(&g, 0, 1, 1);
    add_edge(&g, 0, 4, 1);
    add_edge(&g, 1, 2, 1);
    add_edge(&g, 1, 3, 1);
    add_edge(&g, 1, 4, 1);
    add_edge(&g, 2, 3, 1);
    add_edge(&g, 3, 4, 1);

    printf("%d\n", bfs(&g, 0, 3));

    return 0;
}

以上代码实现了一个无向图的广度优先遍历，其中 `Graph` 结构体用于存储图的信息，包括顶点数和边，`init_graph` 和 `add_edge` 分别用于初始化图和添加边。 `bfs` 函数实现了广度优先遍历，其中使用队列来存储待访问的顶点，使用 `visited` 数组来记录已访问的顶点。在 `main` 函数中，我们创建了一个无向图，并使用 `bfs` 函数从顶点 `0` 开始遍历，查找是否存在到顶点 `3` 的路径。