【数据结构】课前测试_R6-1 实现基于邻接表表示的深度优先遍历 (20 分)

博主： Fivk
发布时间：2021 年 11 月 17 日
1298 次浏览
暂无评论
1189字数
分类：代码笔记

这个测试，，，题目一样，代码改了一点。我当时看到这个题目时还挺高兴，想想复制粘贴就行了。没想到这么坑。再来！！

### R6-1 实现基于邻接表表示的深度优先遍历 (20 分)

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

### 函数接口定义：

```c
void DFS(ALGraph G, int v);
```

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

![](https://blog.fivk.cn/usr/uploads/2021/11/1450622894.png)

### 裁判测试程序样例：

```c
#include <stdio.h>
#include <stdlib.h>
#define MVNum 10
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 DFS(ALGraph G, int v);

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);
}

int main(){
 ALGraph G;
 CreateUDG(G);
 DFSTraverse(G);
 return 0;
}

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

### 输入样例：

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

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

### 输出样例：

遍历序列。

```out
A C G F B E H D 
```

### 我的程序

最后修改：2021 年 11 月 17 日