程序填空题：基于邻接表表示的广度优先遍历
基于邻接表表示的广度优先遍历。
```c++
#include
#include
#define MVNum 100
#define MAXQSIZE 100
int 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){
int Q[MAXQSIZE],f=0,r=0,u,w;
printf("%c ",G.vertices[v].data); visited[v] = 1;
Q[r++]=v;
while(@@[f!=r](2)){
@@[u=Q[f++]](2);
ArcNode *p = G.vertices[u].firstarc;
while(p != NULL){
@@[int w = p->adjvex](2);
if(!visited[w]){
printf("%c ",G.vertices[w].data); visited[w] = 1;
@@[Q[r++]=w](2);
}
p = p->nextarc;
}
}
}
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空：f!=r
第2空：u=Q[f++]
第3空：int w = p->adjvex
第4空：Q[r++]=w
```c++
#include
#include
#define MVNum 100
#define MAXQSIZE 100
int 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){
int Q[MAXQSIZE],f=0,r=0,u,w;
printf("%c ",G.vertices[v].data); visited[v] = 1;
Q[r++]=v;
while(@@[f!=r](2)){
@@[u=Q[f++]](2);
ArcNode *p = G.vertices[u].firstarc;
while(p != NULL){
@@[int w = p->adjvex](2);
if(!visited[w]){
printf("%c ",G.vertices[w].data); visited[w] = 1;
@@[Q[r++]=w](2);
}
p = p->nextarc;
}
}
}
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空：f!=r
第2空：u=Q[f++]
第3空：int w = p->adjvex
第4空：Q[r++]=w
