图---基于邻接矩阵表示的广度优先遍历

6-3 基于邻接矩阵表示的广度优先遍历

实现基于邻接矩阵表示的广度优先遍历。

函数接口定义：

void BFS(Graph G, int v);

其中 G 是基于邻接矩阵存储表示的无向图，v表示遍历起点。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>
#define MVNum 10
                        
int visited[MVNum];
typedef struct{ 
    char vexs[MVNum];                    
    int arcs[MVNum][MVNum]; 
    int vexnum,arcnum;             
}Graph;
 
void CreateUDN(Graph &G);//实现细节隐藏
void BFS(Graph G, int v);
void BFSTraverse(Graph G){ 
    int v;
    for(v = 0; v < G.vexnum; ++v)  visited[v] = 0;    
    for(v = 0; v < G.vexnum; ++v)
        if(!visited[v])  BFS(G, v); 
}
int main(){
    Graph G;
    CreateUDN(G);
    BFSTraverse(G);
    return 0;
}

/* 请在这里填写答案 */

输入样例：

输入第1行为结点数vexnum和边数arcnum。第2行为结点的值，依次输入arcnum行，每行输入两个结点的值表示该两个结点互为邻接点。

8 8
ABCDEFGH
A B
A C
B D
B E
C F
C G
D H
E H

输出样例：

遍历序列。

A B C D E F G H 

#include <string.h>

// 队列结构用于BFS
typedef struct {
    int data[MVNum];
    int front;
    int rear;
} Queue;

void InitQueue(Queue *Q) {
    Q->front = Q->rear = 0;
}

int IsEmpty(Queue Q) {
    return Q.front == Q.rear;
}

void EnQueue(Queue *Q, int e) {
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MVNum;
}

int DeQueue(Queue *Q) {
    int e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MVNum;
    return e;
}

void BFS(Graph G, int v)

{
    Queue Q;
    InitQueue(&Q);
    visited[v] = 1;
    printf("%c ", G.vexs[v]);
    EnQueue(&Q, v);

    while (!IsEmpty(Q))

    {
        int current = DeQueue(&Q);
        for (int i = 0; i < G.vexnum; i++)

        {
            if (G.arcs[current][i] == 1 && !visited[i])

            {
                visited[i] = 1;
                printf("%c ", G.vexs[i]);
                EnQueue(&Q, i);
            }
        }
    }
}