- #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
- [[email protected] 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 1
- A B D E C G F H -_-
- [[email protected] c]
来源: http://www.bubuko.com/infodetail-3746063.html