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