爱站程序员基地
#include <stdio.h>#include <stdlib.h>#include <stdbool.h>/** 邻接矩阵，深度优先遍历**/#define MAX 100#define INFINITY 65535// 图结构体typedef struct {char vexs[MAX]; // 顶点的数组，顶点类型为了简单使用charint 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);// 先初始化标记数组visitedfor (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]
