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

以下是 C 语言实现邻接表存储图的广度优先遍历的代码示例：

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

#define MAX_VERTEX_NUM 100  // 最大顶点数

// 邻接表中表示边的结构体
typedef struct ArcNode {
    int adjvex;  // 邻接点的下标
    struct ArcNode* next;  // 指向下一条边的指针
} ArcNode;

// 邻接表中表示顶点的结构体
typedef struct VNode {
    int data;  // 顶点的数据信息
    ArcNode* firstarc;  // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MAX_VERTEX_NUM];

// 图的结构体，包含邻接表和顶点数、边数等信息
typedef struct {
    AdjList vertices;  // 邻接表
    int vexnum, arcnum;  // 顶点数和边数
} ALGraph;

// 初始化邻接表
void InitGraph(ALGraph* G, int vexnum) {
    G->vexnum = vexnum;
    G->arcnum = 0;
    for (int i = 0; i < vexnum; i++) {
        G->vertices[i].data = i;  // 顶点的数据信息为下标
        G->vertices[i].firstarc = NULL;  // 初始化指向第一条边的指针为 NULL 
    }
}

// 添加一条边
void AddArc(int tail, int head, ALGraph* G) {
    ArcNode* newarc = (ArcNode*)malloc(sizeof(ArcNode));
    newarc->adjvex = head;
    newarc->next = G->vertices[tail].firstarc;
    G->vertices[tail].firstarc = newarc;
    G->arcnum++;
}

// 广度优先遍历
void BFS(ALGraph G, int start) {
    int visited[MAX_VERTEX_NUM] = {0};  // 标记数组，用于记录各个顶点是否已经被访问
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0;  // 队列
    printf("%d ", start);
    visited[start] = 1;  // 标记顶点已被访问
    queue[rear++] = start;  // 将当前顶点入队

    while (front < rear) {  // 队列不为空时
        int curr_v = queue[front++];  // 取出队头顶点
        ArcNode* curr_arc = G.vertices[curr_v].firstarc;
        while (curr_arc) {  // 遍历 curr_v 的所有邻接顶点
            int adj_v = curr_arc->adjvex;
            if (!visited[adj_v]) {  // 该邻接顶点未被访问过
                printf("%d ", adj_v);
                visited[adj_v] = 1;
                queue[rear++] = adj_v;
            }
            curr_arc = curr_arc->next;
        }
    }
}

int main() {
    ALGraph G;
    int vexnum = 6;  // 创建一个有 6 个顶点的图
    InitGraph(&G, vexnum);
    AddArc(0, 1, &G);
    AddArc(0, 2, &G);
    AddArc(1, 2, &G);
    AddArc(1, 3, &G);
    AddArc(2, 1, &G);
    AddArc(2, 3, &G);
    AddArc(2, 4, &G);
    AddArc(3, 4, &G);
    AddArc(3, 5, &G);
    AddArc(4, 3, &G);
    AddArc(4, 5, &G);
    BFS(G, 0);  // 从下标为 0 的顶点开始遍历
    return 0;
}

注意，这里的 `ChitGPT` 只是一个类 ChatGPT 的 AI，只能回答与图、算法等相关的问题，并不能真正理解你的话语，所以需要遵守特定的提问方式。