程序填空题：基于邻接表表示的深度优先遍历
基于邻接表表示的深度优先遍历。
```c++
#include
#include
#define MVNum 100
typedef struct ArcNode{
int adjvex;
struct ArcNode * nextarc;
}ArcNode;
typedef struct VNode{
char data;
ArcNode * firstarc;
}VNode, AdjList[MVNum];
typedef struct{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
int visited[MVNum];
int CreateUDG(ALGraph &G);//实现细节隐藏
void DFS(ALGraph G, int v){
printf("%c ",G.vertices[v].data);
@@[visited[v] = 1](2);
ArcNode *p = G.vertices[v].firstarc;
while(@@[p != NULL](2)){
int w = p->adjvex;
if(!visited[w]) @@[DFS(G, w)](2);
@@[p = p->nextarc](2);
}
}
void DFSTraverse(ALGraph G){
int v;
for(v = 0; v < G.vexnum; ++v) visited[v] = 0;
for(v = 0; v < G.vexnum; ++v)
if(!visited[v]) @@[DFS(G, v)](2);
}
int main(){
ALGraph G;
CreateUDG(G);
DFSTraverse(G);
return 0;
}
```
答案：
第1空：visited[v] = 1
第2空：p != NULL
第3空：DFS(G, w)
第4空：p = p->nextarc
第5空：DFS(G, v)
```c++
#include
#include
#define MVNum 100
typedef struct ArcNode{
int adjvex;
struct ArcNode * nextarc;
}ArcNode;
typedef struct VNode{
char data;
ArcNode * firstarc;
}VNode, AdjList[MVNum];
typedef struct{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
int visited[MVNum];
int CreateUDG(ALGraph &G);//实现细节隐藏
void DFS(ALGraph G, int v){
printf("%c ",G.vertices[v].data);
@@[visited[v] = 1](2);
ArcNode *p = G.vertices[v].firstarc;
while(@@[p != NULL](2)){
int w = p->adjvex;
if(!visited[w]) @@[DFS(G, w)](2);
@@[p = p->nextarc](2);
}
}
void DFSTraverse(ALGraph G){
int v;
for(v = 0; v < G.vexnum; ++v) visited[v] = 0;
for(v = 0; v < G.vexnum; ++v)
if(!visited[v]) @@[DFS(G, v)](2);
}
int main(){
ALGraph G;
CreateUDG(G);
DFSTraverse(G);
return 0;
}
```
答案：
第1空：visited[v] = 1
第2空：p != NULL
第3空：DFS(G, w)
第4空：p = p->nextarc
第5空：DFS(G, v)
