- #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
- [[email protected] 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 7
- create edge done.
- A D E B C F G H
- [[email protected] c]#
图 - 邻接表广度优先遍历(C 语言)
来源: http://www.bubuko.com/infodetail-3746047.html