图 - 邻接矩阵广度优先遍历(C语言)
16lz
2021-04-08
#include <stdio.h>#include <stdlib.h>#include <stdbool.h>/* * 邻接矩阵,深度优先遍历 * */#define MAX 100#define INFINITY 65535// 图结构体typedef struct { char vexs[MAX]; // 顶点的数组,顶点类型为了简单使用char int arc[MAX][MAX]; // 边表二维数组,对,行列的下标对应实际存在的顶点,值为1表示两顶点间有边 int numVex, numEdg; // 顶点和边的数量,创建的时候用}GRAPH, *PGRAPH;typedef struct node { int index; // 队列节点数据应该为顶点的下标 struct node *next;}NODE, *PNODE;typedef struct { PNODE front; PNODE rear;}QUEUE, *PQUEUE;int visited[MAX]; // 标记遍历过的顶点下标void create(PGRAPH);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, j; QUEUE Q; init(&Q); // 先初始化标记数组visited for (i=0; i<graph.numVex; i++) { visited[i] = 0; } // 开始遍历 for (i=0; i<graph.numVex; i++) { if (! visited[i]) { visited[i] = 1; printf("%c ", graph.vexs[i]); en_queue(&Q, i); while (Q.front->next) { de_queue(&Q, &i); for (j=0; j<graph.numVex; j++) { if (!visited[j] && graph.arc[i][j] != INFINITY) { visited[j] = 1; printf("%c ", graph.vexs[j]); en_queue(&Q, j); } } } } printf("-_-"); } putchar('\n');}void create(PGRAPH g){ int i, j, k, w; printf("请输入顶点及边的个数:\n"); // 这里输入边的个数也就只有在创建的时候用得着 scanf("%d %d", &g->numVex, &g->numEdg); // 创建顶点 printf("请一次性输入顶点的值:\n"); getchar(); for (i=0; i<g->numVex; i++) { scanf("%c", &g->vexs[i]); } // 初始化边表 for (i=0; i<g->numVex; i++) { for (j=0; j<g->numVex; j++) { g->arc[i][j] = INFINITY; } } // 创建表 for (k=0; k<g->numEdg; k++) { printf("请输入边的顶点下标和权:\n"); // 本例中并没有对权有操作 scanf("%d %d %d", &i, &j, &w); g->arc[i][j] = g->arc[j][i] = w; }}int main(void){ GRAPH graph; create(&graph); traverse_bfs(graph); return 0;}
output
[root@8be225462e66 c]# gcc bfs_adMatrix.c && ./a.out请输入顶点及边的个数:8 9请一次性输入顶点的值:ABCDEFGH请输入边的顶点下标和权:0 1 1请输入边的顶点下标和权:1 2 1请输入边的顶点下标和权:2 5 1请输入边的顶点下标和权:1 4 1请输入边的顶点下标和权:0 4 1请输入边的顶点下标和权:0 3 1请输入边的顶点下标和权:3 6 1请输入边的顶点下标和权:6 4 1请输入边的顶点下标和权:6 7 1A B D E C G F H -_-[root@8be225462e66 c]
©著作权归作者所有:来自51CTO博客作者sndapk的原创作品,如需转载,请注明出处,否则将追究法律责任好知识,才能预见未来
赞赏
0人进行了赞赏支持
更多相关文章
- 图 -邻接表广度优先遍历(C语言)
- vue实现tab选项卡
- C语言练习题
- webgl入门
- HBase基础 | 图数据库HGraphDB介绍
- 关于HashMap的一些思考
- C语言中的择中,二分查找算法解析
- 不得不会的Flink Dataset的DeltaI 迭代操作
- C语言循环分支结构深度总结实践