搜索
第1页共3页深度优先遍历一、实验目的了解深度优先遍历的基本概念以及实现方式。二、实验内容1、设计一个算法来对图的进行深度优先遍历；2、用C语言编程来实现此算法。用下面的实例来调试程序：三、使用环境Xcode编译器四、编程思路深度优先遍历图的方法是，从邻接矩阵出发：访问顶点v；依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；构造一个遍历辅助矩阵visited[]进行比较若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止，并将顶点信息存储在数组Q[]里面。反复搜索可以通过使用函数的嵌套来实现。第2页共3页五、调试过程1.程序代码：//为方便调试，程序清晰直观删除了邻接矩阵的构造函数，//并且修改了main()函数，只保留了DFS函数#includestdio.h#defineN4//定义顶点数inta[N][N]={{0,1,1,1},{1,0,0,0},{1,0,0,1},{1,0,0,1}};//邻接矩阵由之前程序函给出intvisited[N]={0};//遍历比较的辅助矩阵，初始化为0矩阵intQ[N];//用来存储各个顶点的信息staticintlast=-1;voidDFS(intG[][N],ints){visited[s]=1;Q[++last]=s;for(inti=0;iN;i++)//进行遍历{if(G[s][i]==1){if(visited[i]==0)第3页共3页DFS(G,i);//函数嵌套，完成一次搜索，指向下一个顶点}}}intmain(){DFS(a,0);printf(深度优先搜索为\n);for(inti=0;iN;i++)//打印遍历的结果printf(%d,Q[i]+1);return0;}2．运行窗口：输出结果为各顶点按深度优先遍历的排序。