6-2 邻接表存储图的广度优先遍历 c语言代码实现

以下是使用邻接表存储图并进行广度优先遍历的 C 语言代码实现：

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

#define MAXV 1000    // 最大顶点数

// 定义邻接表结构体
typedef struct node
{
    int v;    // 邻接点编号
    struct node* next;    // 指向下一个邻接点的指针
}Node;

// 定义图结构体
typedef struct Graph
{
    int V;    // 顶点数
    int E;    // 边数
    Node* adj[MAXV];    // 邻接表数组
}Graph;

// 创建新结点
Node* newNode(int v)
{
    Node* p = (Node*)malloc(sizeof(Node));
    p->v = v;
    p->next = NULL;
    return p;
}

// 添加边
void addEdge(Graph* G, int u, int v)
{
    Node* p = newNode(v);
    p->next = G->adj[u];
    G->adj[u] = p;
    G->E++;
}

// 展示邻接表
void showAdjList(Graph* G)
{
    for (int i = 0; i < G->V; i++)
    {
        printf("顶点 %d 的邻接点有：", i);
        Node* p = G->adj[i];
        while (p != NULL)
        {
            printf("%d ", p->v);
            p = p->next;
        }
        printf("\n");
    }
}

// 定义队列结构体
typedef struct Queue
{
    int front, rear;
    int data[MAXV];
}Queue;

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

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

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

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

// 广度优先遍历
void BFS(Graph* G, int s)
{
    int visited[MAXV] = { 0 };    // 标记数组
    Queue q;    // 定义队列
    initQueue(&q);    // 初始化队列
    visited[s] = 1;    // 标记起始点已访问
    enqueue(&q, s);    // 起始点入队
    printf("%d ", s);    // 输出起始点

    while (!isEmptyQueue(&q))    // 队列非空
    {
        int u = dequeue(&q);    // 取队头元素
        Node* p = G->adj[u];    // 取出其邻接链表
        while (p != NULL)
        {
            int v = p->v;    // 取出邻接点
            if (!visited[v])    // 如果邻接点未被访问
            {
                visited[v] = 1;    // 标记邻接点已访问
                enqueue(&q, v);    // 邻接点入队
                printf("%d ", v);    // 输出邻接点
            }
            p = p->next;
        }
    }
    printf("\n");
}

int main()
{
    Graph G;
    int V, E;

    scanf("%d%d", &V, &E);
    G.V = V;
    G.E = 0;

    // 初始化邻接表
    for (int i = 0; i < G.V; i++)
        G.adj[i] = NULL;

    // 添加边
    for (int i = 0; i < E; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        addEdge(&G, u, v);
        addEdge(&G, v, u);    // 无向图要连回去
    }

    showAdjList(&G);

    BFS(&G, 0);

    return 0;
}