图 -邻接表广度优先遍历(C语言)

#include <stdio.h>#include <stdlib.h>#include <stdbool.h># define MAX 100// 边节点typedef struct enode {    int adIndex; // 节点下标    int weight; // 权,本代码中并未用到    struct enode *next; // 下一个节点}ENODE, *PE;// 顶点typedef struct vnode {    char name;    PE firstEdge; // 单链表}VNODE, *PV, VLIST[MAX];// 图(网)typedef struct graph {   VLIST vlist;   int numVnodes, numEdges;}GRAPH, *PG;typedef struct node {    int index; // 队列节点数据应该为顶点的下标    struct node *next;}NODE, *PNODE;typedef struct {    PNODE front;    PNODE rear;}QUEUE, *PQUEUE;// 保存已遍历顶点int visited[MAX];void create(PG);void traverse_bfs(GRAPH);void init(PQUEUE pQ);void en_queue(PQUEUE, int);bool de_queue(PQUEUE, int *);bool de_queue(PQUEUE pQ, int *pVal){    //printf("de_queue...");    PNODE tmp;    if (pQ->front->next == NULL) {        printf(" failed, queue empty!\n");        return false;    }    tmp = pQ->front->next;     *pVal = tmp->index;    pQ->front->next = tmp->next;    // 最后一个节点出队特殊处理    if (tmp->next == NULL)        pQ->rear = pQ->front;    free(tmp);    //printf("success, value: %d\n", *pVal);    return true;}void en_queue(PQUEUE pQ, int val){    //printf("en_queue %d", val);    PNODE pNew;    pNew = (PNODE)malloc(sizeof(NODE));    if (!pNew) {        printf(" en_queue malloc error!\n");        exit(-1);    }    pNew->index = val;    pNew->next = NULL;    pQ->rear->next = pNew;    pQ->rear = pNew;    //printf(" success.\n");}void init(PQUEUE pQ){    // front, rear都指向头节点    pQ->front = pQ->rear = (PNODE)malloc(sizeof(NODE));    if (! pQ->front) {        printf("init malloc error!\n");        exit(-1);    }    pQ->front->next = NULL;}void traverse_bfs(GRAPH graph){    int i;    PE p;    QUEUE Q;    init(&Q);    // 初始化所有顶点为未访问状态    for (i=0; i<graph.numVnodes; i++) {        visited[i] = 0;    }    // 开始遍历    for (i=0; i<graph.numVnodes; i++) {        if (!visited[i]) {            en_queue(&Q, i);            while (Q.front->next) {                de_queue(&Q, &i);                   if (!visited[i]) {                    printf("%c ", graph.vlist[i].name);                    visited[i] = 1;                    p = graph.vlist[i].firstEdge;                    while (p) {                        if (!visited[p->adIndex]) {                            printf("%c ", graph.vlist[p->adIndex].name);                            visited[p->adIndex] = 1;                            en_queue(&Q, p->adIndex);                        }                        p = p->next;                    }                }            }        }     }       putchar('\n');}void create(PG g){    int i, j, k;    PE e;    printf("请输入顶点数和边数:\n");    scanf("%d %d", &g->numVnodes, &g->numEdges);    getchar();    // 根据顶点数创建顶点表（VLIST一维数组）    printf("请一次性输入顶点的值: ");    for (i=0; i<g->numVnodes; i++) {        scanf("%c", &g->vlist[i].name);        g->vlist[i].firstEdge = NULL;    }    // 边节点单链表填充（创建边）    for (k=0; k<g->numEdges; k++) {        printf("请输入第%d条边(vi, vj)对应下标:\n", k+1);        scanf("%d %d", &i, &j);        // 创建i的边表节点j（双向）        e = (PE)malloc(sizeof(ENODE));        e->adIndex = j;        e->next = g->vlist[i].firstEdge; // 头插法        g->vlist[i].firstEdge = e;        // 创建j的边表节点i（双向）        e = (PE)malloc(sizeof(ENODE));        e->adIndex = i;        e->next = g->vlist[j].firstEdge;        g->vlist[j].firstEdge = e;    }    printf("create edge done.\n");}int main(void){    GRAPH graph;    create(&graph);    traverse_bfs(graph);    return 0;}

output

[root@8be225462e66 c]# gcc bfs_adList.c && ./a.out请输入顶点数和边数:8 9请一次性输入顶点的值: ABCDEFGH请输入第1条边(vi, vj)对应下标:0 1请输入第2条边(vi, vj)对应下标:1 2请输入第3条边(vi, vj)对应下标:2 5请输入第4条边(vi, vj)对应下标:1 4请输入第5条边(vi, vj)对应下标:0 4请输入第6条边(vi, vj)对应下标:0 3请输入第7条边(vi, vj)对应下标:3 6请输入第8条边(vi, vj)对应下标:6 4请输入第9条边(vi, vj)对应下标:6 7create edge done.A D E B C F G H[root@8be225462e66 c]#