- 任务要求
- 参考答案
- 评论2
- 任务描述
- 相关知识
- 编程要求
- 测试说明
任务描述
本关任务:以邻接表存储图,要求编写程序实现图的深度优先遍历。
相关知识
图的深度优先遍历类似于树的先序遍历, 是树的先序遍历的推广,其基本思想如下:
- 访问顶点v;
- 选择一个与顶点v相邻且没被访问过的顶点w,从w出发深度优先遍历。
- 直到图中与v相邻的所有顶点都被访问过为止
在程序里完成遍历需要在函数体外定义全局访问标志数组,记录顶点是否被访问过,初始时,所有元素均为0
,表示所有顶点未被访问过:
int visited[MAX_VERTEX_NUM] = {0};
访问每个顶点时,定义输出顶点数据的专用函数:
void visit(VertexType i)
{
printf("%s ",i); // VertexType是char [20]类型
}
以邻接表作为存储结构进行深度优先遍历的算法如下:
深度优先遍历的代码分为两部分,遍历的图可能是非连通图,从一个顶点出发,可能不能遍历所有顶点,故对于每个顶点都要检查一次,是否被访问过,如果没有,从这个没被访问的顶点出发执行一次深度优先遍历,算法如下:
void DFSTraverse(ALGgraph G)
{
// 初始条件:图G存在,vi是顶点的输出函数的指针。
// 操作结果:从第1个顶点起,深度优先遍历图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); // 对尚未访问的顶点v调用DFS
printf("\n");
}
编程要求
根据提示,在右侧编辑器补充代码,实现以邻接表作为存储结构的图深度优先遍历算法:
-
void DFS(ALGraph G,int v); //从第v个顶点出发递归地深度优先遍历图G
-
void DFSTraverse(ALGraph G); // 对图G作深度优先遍历
测试说明
平台会对你编写的代码进行测试:
测试输入: 0
lt2.txt
输入说明: 第一行输入
0
,表示输入图的类型为有向图。 第二行输入文件名,该文件里保存了图的数据信息,内容如下:
第1行为图的顶点的个数n; 第2行为图的边的条数m; 第3行至第n+2行是n个顶点的数据; 第n+3行至第n+m+2行是m条边的数据;
预期输出: 有向图
7个顶点:
高等数学 程序设计基础 C语言 离散数学 数据结构 编译原理 操作系统
9条弧(边):
高等数学→离散数学 高等数学→C语言
程序设计基础→C语言 程序设计基础→数据结构
C语言→数据结构
离散数学→编译原理 离散数学→数据结构
数据结构→操作系统 数据结构→编译原理
深度优先遍历序列:
高等数学 离散数学 编译原理 数据结构 操作系统 C语言 程序设计基础
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#include"ALGraph.h"
void DFS(ALGraph G,int v); //从第v个顶点出发递归地深度优先遍历图G
void DFSTraverse(ALGraph G); // 对图G作深度优先遍历
int visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量)
int main()
{
ALGraph g;
CreateGraphF (g); // 利用数据文件创建图
Display(g); // 输出图
printf("深度优先遍历序列:\n");
DFSTraverse(g);
return 0;
}
void DFS(ALGraph G,int v)
{ //从第v个顶点出发递归地深度优先遍历图G
/********** Begin **********/
ArcNode *p;
p=G.vertices[v].firstarc;
visited[v]=1;
visit(G.vertices[v].data);
for(int w=FirstAdjVex(G,G.vertices[v].data);w>=0;w=NextAdjVex(G,G.vertices[v].data,G.vertices[w].data)){
if(!visited[w])
DFS(G,w);
}
/********** End **********/
}
void DFSTraverse(ALGraph G)
{ // 对图G作深度优先遍历
/********** Begin **********/
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);
printf("\n");
/********** End **********/
}
输出说明: 第一行输出图的类型。 第二行起输出图的顶点和边的数据信息。 最后一行为从“高等数学”出发进行深度优先遍历的序列。