任务描述

本关任务：请你实现 dfs.cpp 里的void DFS( MatGraph* G, VertexType V)函数。 约定：顶点编号小的先输出。

相关知识

为了完成本关任务，你需要掌握：1.如何使用邻接矩阵存储图，2.如何遍历图。

邻接矩阵存储图
一个包含6个顶点的无向图如图所示。

图1 一个包含6个顶点的无向图

图 2 给出了对图 1 的无向图的存储结构图：每个顶点的名称由一个整数描述，顶点的相邻关系保存在邻接矩阵中，矩阵中值为 1 表示i号顶点到j号顶点有边，为 0 表示无边。

图2 图1的无向图的邻接矩阵

图的邻接矩阵定义如下：

typedef struct             //图的定义
{   
    int edges[MAXV][MAXV]; //邻接矩阵
    int n, e;              //顶点数, 边数
    VertexType vexs[MAXV]; //存放顶点信息
}  MatGraph;
给定指向该结构的指针G，就可以对图进行操作。

图的遍历

所谓图的遍历（graph traversal），也称为搜索（search），就是从图中某个顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次。遍历可以采取两种方法进行：深度优先搜索（DFS，depth first search）和广度优先搜索（BFS，breadth first search）。

深度优先遍历过程：

（1）从图中某个初始顶点v出发, 首先访问初始顶点v。
（2）选择一个与顶点v相邻且没被访问过的顶点w, 再从w出发进行深度优先搜索, 直到图中与当前顶点v邻接的所有顶点都被访问过为止。

算法设计思路：

深度优先遍历的过程体现出后进先出的特点：用栈或递归方式实现。

如何确定一个顶点是否访问过? 设置一个visited[] 全局数组,  visited[i]=0表示顶点i没有访问;  visited[i]=1表示顶点i已经访问过。
如果用邻接矩阵存储图（设顶点个数为 n），则 DFS 算法实现的伪代码如下：

DFS(图G, 顶点 i ) //从顶点 i 进行深度优先搜索
{ 
     visited[ i ] = 1; //将顶点 i 的访问标志置为 1 
     for( j=0; j<n; j++ ) //对其他所有顶点 j 
     { 
         //j 是 i 的邻接顶点，且顶点 j 没有访问过
         if( edges[i][j]==1 && !visited[j] ) 
         { 
             //递归搜索前的准备工作需要在这里写代码 
             DFS( j ); //从顶点 j 出发进行 DFS 搜索
             //以下是 DFS 的回退位置，在很多应用中需要在这里写代码  
         } 
     } 
}
对图1运行该算法的结果（从顶点5出发）：  5 0 1 3 2 4。

编程要求

请你在右侧的代码窗口中实现dfs.cpp里的void DFS( MatGraph* G, VertexType V)函数。 注意遵守约定：顶点编号小的先输出。

测试说明

本关的测试过程如下：
1.平台编译 step1/dfs.cpp ；
2.平台运行该可执行文件，并以标准输入方式提供测试输入；
3.平台获取该可执行文件的输出，然后将其与预期输出对比，如果一致则测试通过；否则测试失败。
输入输出格式说明：

输入格式：
输入V，开始遍历的起始顶点编号。

输出格式：
输出对图进行深度优先遍历的顶点序列，每个顶点编号前面有一个空格。

以下是平台对 step1/dfs.cpp 的测试样例：

样例输入：

测试输入：5

样例输出：
预期输出：DFS from 5: 5 1 3 0 2 4 6

测试代码： 

 #include "dfs.h"

/*
 * 从顶点V出发进行深度优先搜索。
 * 函数DFS应从编号为V的顶点出发递归地深度优先遍历图，
 * 遍历访问邻接点时，要求按序号递增的顺序。
 * 题目保证V是图中的合法顶点。
 * 参数G为邻接矩阵存储的图的表示。
 */
void DFS( MatGraph* G, VertexType V)
{
    /**
    * 请在下面的begin..end间编写程序代码，
    * 勿修改begin..end之外的代码。
    */
    /*******************begin*******************/

    

    /*******************end********************/
}

int main()
{
    MatGraph* G;
    VertexType V;

    G = CreateGraph();
    scanf("%d", &V);
    printf("DFS from %d:", V);
    DFS(G, V);

    return 0;
}

补充代码：

 #include "dfs.h"

/*
 * 从顶点V出发进行深度优先搜索。
 * 函数DFS应从编号为V的顶点出发递归地深度优先遍历图，
 * 遍历访问邻接点时，要求按序号递增的顺序。
 * 题目保证V是图中的合法顶点。
 * 参数G为邻接矩阵存储的图的表示。
 */
void DFS( MatGraph* G, VertexType V)
{
    /**
    * 请在下面的begin..end间编写程序代码，
    * 勿修改begin..end之外的代码。
    */
    /*******************begin*******************/
     visited[V]=1;
     printf(" %d",V);
     for(int j=0;j<G->n;j++)
     {
         if(G->edges[V][j]==1&&visited[j]==0)
         {
             DFS(G,j);
         }
     }
    

    /*******************end********************/
}

int main()
{
    MatGraph* G;
    VertexType V;

    G = CreateGraph();
    scanf("%d", &V);
    printf("DFS from %d:", V);
    DFS(G, V);

    return 0;
}