第2关：图的深度优先遍历

编程要求

根据提示，在右侧编辑器补充代码，实现以邻接矩阵作为存储结构的图深度优先遍历算法:

• void DFS(MGraph G,int v); // 从第v个顶点出发递归地深度优先遍历图G
• void DFSTraverse(MGraph G); // 图G存在，从第1个顶点起，深度优先遍历图G，并对每个顶点调用函数visit一次且仅一次

测试说明

平台会对你编写的代码进行测试：

测试输入： 0 lt2.txt

输入说明： 第一行输入0，表示输入图的类型为有向图。 第二行输入文件名，该文件里保存了图的数据信息，内容如下：

第1行为图的顶点的个数n； 第2行为图的边的条数m； 第3行至第n+2行是n个顶点的数据； 第n+3行至第n+m+2行是m条边的数据；

预期输出： 有向图 7个顶点9条边。顶点依次是: 高等数学 程序设计基础 C语言 离散数学 数据结构 编译原理 操作系统 图的邻接矩阵: 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 深度优先遍历序列： 高等数学 C语言 数据结构 编译原理 操作系统 离散数学 程序设计基础

#include 
#include 
#include
#include 
 
#include"MGraph.h"
 
void DFS(MGraph G,int v);// 从第v个顶点出发递归地深度优先遍历图G 
void DFSTraverse(MGraph G);// 图G存在，从第1个顶点起，深度优先遍历图G，并对每个顶点调用函数visit一次且仅一次 
 
int visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量) 
 
int main()
{
   MGraph g;
	VertexType v1,v2;
	CreateGraphF(g); /* 利用数据文件创建无向图*/
	Display(g); /* 输出无向图*/  
	printf("深度优先遍历序列：\n"); 
	DFSTraverse(g);
	return 0;
}
 
 
 
void DFS(MGraph G,int v)
{
	// 从第v个顶点出发递归地深度优先遍历图G 
	/********** Begin **********/
	int w;
	visited[v]=1;
	visit(G.vexs[v]);
	for(w=FirstAdjVex(G,G.vexs[v]);w>=0;w=NextAdjVex(G,G.vexs[v],G.vexs[w]))
		if(!visited[w])
			DFS(G,w);
	/********** End **********/
}
 
void DFSTraverse(MGraph G)
{   //图G存在，从第1个顶点起，深度优先遍历图G，并对每个顶点调用函数visit一次且仅一次 
	/********** Begin **********/
	int v;
	for(v=0;v
		visited[v]=0;
	for(v=0;v
		if(!visited[v])
			DFS(G,v);
	printf("\n");
	/********** End **********/
}

输出说明： 第一行输出图的类型。 第二行起输出图的顶点和边的数据信息。 最后一行为从“高等数学”出发进行深度优先遍历的序列。