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

1-4 基于邻接表表示的广度优先遍历

分数 4

作者 王东

单位 贵州师范学院

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

函数接口定义：

1
void BFS(ALGraph 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
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
#define MVNum 10
#define MAXQSIZE 100

bool visited[MVNum]; 
typedef struct ArcNode{
    int adjvex;
    struct ArcNode *nextarc;
    int info; 
}ArcNode; 

typedef struct VNode{ 
    char data;
    ArcNode *firstarc;
}VNode, AdjList[MVNum];

typedef struct{ 
    AdjList vertices; 
    int vexnum, arcnum;
}ALGraph;

int CreateUDG(ALGraph &G);//实现细节隐藏
void BFS(ALGraph G, int v);

void BFSTraverse(ALGraph 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(){
 ALGraph G;
 CreateUDG(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 C B G F E D H

QQ截图20191125133700.png

我的正确答案

  • 注意无论是否是访问过的，p指针都要往后挪
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
#include <iostream>
#include <queue>
using namespace std;
void BFS(ALGraph G, int v) {
    queue<int> queue;
    if (!visited[v]) {
        queue.push(v);
        visited[v] = 1;
        cout << G.vertices[v].data;
        // 当队列不空
        while (!queue.empty()) {
            int num = queue.front();
            queue.pop();
            ArcNode *p = G.vertices[num].firstarc;
            // 依次遍历顶点邻接边
            while (p != NULL) {
                if (!visited[p->adjvex]){
                    queue.push(p->adjvex);
                    visited[p->adjvex] = 1;
                    cout  << " " << G.vertices[p->adjvex].data;
                }
                p = p->nextarc;
            }
        }
    }
    cout << " ";
}