爱站程序员基地
#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]#
