图 - 邻接矩阵广度优先遍历(C语言)

#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 1

A B D E C G F H -_-
[root@8be225462e66 c]

图 - 邻接矩阵广度优先遍历(C语言)

原文：https://blog.51cto.com/sndapk/2693068