PTA（图）1-3 基于邻接矩阵表示的广度优先遍历

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

分数 4

作者 王东

单位 贵州师范学院

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

函数接口定义：

1
void BFS(Graph G, int v);

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

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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行，每行输入两个结点的值表示该两个结点互为邻接点。

1
2
3
4
5
6
7
8
9
10
8 8
ABCDEFGH
A B
A C
B D
B E
C F
C G
D H
E H

输出样例：

遍历序列。

1
A B C D E F G H

QQ截图20191125133700.png

我的正确答案

  • 注意行末有空格
  • 注意遍历所有顶点，寻找邻接且未访问的顶点——一定要先确定是邻接的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <queue>
using namespace std;

// 全局变量 visited 已在裁判程序中定义，无需重复声明

void BFS(Graph G, int v) {
    queue<int> q;
    if (!visited[v]) {
        visited[v] = 1;
        // 输出起点顶点值（第一个顶点无前置空格）
        cout << G.vexs[v];
        q.push(v);
        
        while (!q.empty()) {
            int num = q.front();
            q.pop();
            
            // 遍历所有顶点，寻找邻接且未访问的顶点
            for (int i = 0; i < G.vexnum; ++i) {
                if (G.arcs[num][i] == 1 && !visited[i]) {
                    visited[i] = 1;
                    // 非第一个顶点，先输出空格再输出顶点值
                    cout << " " << G.vexs[i];
                    q.push(i);
                }
            }
        }
    }
    cout << " ";
}