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

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

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

#define MAX_VERTEX_NUM 20  // 最大顶点数

typedef char VertexType;   // 顶点数据类型
typedef struct ArcNode {
    int adjvex;            // 邻接点在数组中的位置下标
    struct ArcNode *next;  // 指向下一个邻接点的指针
} ArcNode;

typedef struct {
    VertexType data;       // 顶点数据
    ArcNode *firstarc;     // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;      // 顶点数组
    int vexnum, arcnum;    // 图的顶点数和边数
} ALGraph;

typedef int Boolean;
Boolean visited[MAX_VERTEX_NUM];  // 访问标记数组

void CreateGraph(ALGraph *G) {
    int i, j, k;
    ArcNode *p;
    printf("请输入图的顶点数和边数：");
    scanf("%d %d", &(G->vexnum), &(G->arcnum));
    printf("请输入各个顶点的名称：");
    for (i = 0; i < G->vexnum; ++i) {
        getchar();
        scanf("%c", &(G->vertices[i].data));
        G->vertices[i].firstarc = NULL;
    }
    for (k = 0; k < G->arcnum; ++k) {
        printf("请输入第%d条边依附的两个顶点的编号：", k + 1);
        getchar();
        scanf("%d %d", &i, &j);
        p = (ArcNode *) malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->next = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p;
        p = (ArcNode *) malloc(sizeof(ArcNode));
        p->adjvex = i;
        p->next = G->vertices[j].firstarc;
        G->vertices[j].firstarc = p;
    }
}

void BFS(ALGraph *G, int v) {
    int i;
    ArcNode *p;
    int que[MAX_VERTEX_NUM];
    int front = 0, rear = 0;
    printf("%c ", G->vertices[v].data);
    visited[v] = 1;
    que[rear++] = v;
    while (front != rear) {
        i = que[front++];
        p = G->vertices[i].firstarc;
        while (p != NULL) {
            if (!visited[p->adjvex]) {
                printf("%c ", G->vertices[p->adjvex].data);
                visited[p->adjvex] = 1;
                que[rear++] = p->adjvex;
            }
            p = p->next;
        }
    }
}

int main() {
    ALGraph G;
    int i;
    CreateGraph(&G);
    printf("请输入遍历起点的编号：");
    scanf("%d", &i);
    printf("广度优先遍历序列为：");
    BFS(&G, i);
    printf("\n");
    return 0;
}

这是一个实现了邻接表存储图的广度优先遍历的C语言代码。通常情况下，我们使用队列来辅助实现广度优先遍历。该程序采用了一个整型数组作为队列，并用两个指针front和rear分别指向队列的队头和队尾。在遍历时，我们首先将起点加入队列中，然后依次从队列中取出每个顶点，并访问它的所有未访问邻接点，并将其加入队列中，直到队列为空。在访问邻接点时，我们需要注意判断它是否已经被访问过，以避免重复访问。

希望对您有所帮助，如有疑问请留言。