数据结构与算法特训365天—深度优先搜索

一、知识点概述

       深度优先搜索（Depth First Search，DFS），是最常见的图搜索方法之一。深度优先搜索沿着一条路径一直走下去，无法进行时，回退到刚刚访问的结点，似不撞南墙不回头，不到黄河心不死。深度优先遍历是按照深度优先搜索的方式对图进行遍历。

二、深度优先遍历秘籍

        后被访问的顶点，其邻接点先被访问

        根据深度优先遍历秘籍，后来先服务，可以借助于栈实现。递归本身就是使用栈实现的，因此使用递归方法更方便。

三、算法步骤

1. 初始化图中所有顶点未被访问；

2. 从图中的某个顶点v出发，访问v并标记已访问；

3. 依次检查v的所有邻接点w，如果w未被访问，则从w出发进行深度优先遍历（递归调用，重复2-3步）。

四、算法实现

void DFS_AM(AMGraph G, int v)  //基于邻接矩阵的深度优先遍历
{
    int w;
    cout<"\t";
    visited[v]=true;
    for(w=0; w//依次检查v的所有邻接点
        if(G.Edge[v][w] && !visited[w])  //v、w邻接而且w未被访问
            DFS_AM(G,w);  //从w顶点开始递归深度优先遍历
}

void DFS_AL(ALGraph G,int v)  //基于邻接表的深度优先遍历 
{
	int w;
	AdjNode *p;
	cout<"\t";
	visited[v]=true;
	p=G.Vex[v].first;
	while(p)  //依次检查v的所有邻接点 
	{
		w=p->v;  //w为v的邻接点 
		if(!visited[w])  //w未被访问 
		  DFS_AL(G,w);  //从w出发，递归深度优先遍历 
		p=p->next;
	} 
}

void DFS_AL(ALGraph G)
{
	for(int i=0; i
	if(!visited[i])
	   DFS_AL(G,i);
}

五、完整代码

5.1 基于邻接矩阵的深度优先遍历

#include 
using namespace std;
#define MaxVnum 100  //顶点数最大值
bool visited[MaxVnum];  //访问标志数组，其初值为“false” 
typedef char VexType;  //顶点的数据类型，根据需要定义 //typedef:专门起外号的 
typedef int EdgeType;  //边上权值的数据类型，若不带权值的图，则为0或1
typedef struct{
	VexType Vex[MaxVnum];  //顶点数组 
	EdgeType Edge[MaxVnum][MaxVnum];  //二维数组 
	int vexnum,edgenum;  //顶点数，边数 
}AMGraph;
 
int locatevex(AMGraph G,VexType x)
{
	for (int i=0; i//查找顶点信息的下标 
		if(x==G.Vex[i])
			return i;
		return -1;  //没找到 
}
 
void CreateAMGraph(AMGraph &G) 
{
	int i,j;
	VexType u, v;
	cout<<"请输入顶点数："<
	cin>>G.vexnum;
	cout<<"请输入边数："<
	cin>>G.edgenum;
	cout<<"请输入顶点信息："<
	for(int i=0; i//输入顶点信息，存入顶点信息数组
		cin>>G.Vex[i];
	for(int i=0; i//初始化邻接矩阵所有值为0，如果是网，则初始化为无穷大
	  for(int j=0; j
	  	 G.Edge[i][j]=0;
	cout<<"请输入每条边依附的两个顶点："<
	while(G.edgenum--)
	{
		cin>>u>>v;
		i=locatevex(G,u);  //查找顶点u的存储下标 
		j=locatevex(G,v);  //查找顶点v的存储下标 
		if(i!=-1&&j!=-1)
	      G.Edge[i][j]=G.Edge[i][j]=1;  //邻接矩阵储置1 
	    else
	    {
	    	cout<<"讨厌！你个大笨居输错了啦！！！"<
	    	G.edgenum++;  //本次输入不算 
		}
	}
}
 
void print(AMGraph G)  //输出邻接矩阵
{
	cout<<"图的邻接矩阵为："<
	for(int i=0; i,G.vexnum; i++)
	{
		for(int j=0; j
		 cout<"\t";
		cout<
	} 
}
 
void DFS_AM(AMGraph G, int v)  //基于邻接矩阵的深度优先遍历
{
    int w;
    cout<"\t";
    visited[v]=true;
    for(w=0; w//依次检查v的所有邻接点
        if(G.Edge[v][w] && !visited[w])  //v、w邻接而且w未被访问
            DFS_AM(G,w);  //从w顶点开始递归深度优先遍历
}
 
int main()
{
	int v;
	VexType c; 
	AMGraph G;
	CreateAMGraph(G);
	print(G);
	cout<<"请输入连通图的起始点："<
	cin>>c;
	v=locatevex(G,c); //查找顶点u的存储下标 
	if(v!=-1)
	{
		cout<<"深度优先搜索遍历连通图结果："<
		DFS_AM(G,v); 
	}
	else
		cout<<"输出顶点信息出错！请重新输入！"<
	return 0;
}

5.2 基于邻接表的深度优先遍历

#include 
using namespace std;
const int MaxVnum=100;  //顶点数最大值
bool visited[MaxVnum];  //访问标志数组，其初值为“false”
 
typedef char VexType;  //顶点的数据类型为字符型
typedef struct AdjNode{  //定义邻接点类型
	int v;
	struct AdjNode *next;  //指向下一个邻接点 
}AdjNode;
 
typedef struct VexNode{  //定义定点类型 
	VexType data;  //VerType为顶点的数据类型，根据需要定义 
	AdjNode *first;  //指向第一个邻接点 
}VerNode;
 
typedef struct{  //定义邻接表类型
	VexNode Vex[MaxVnum];
	int vexnum,edgenum;  //顶点数，边数 
}ALGraph;
 
int locatevex(ALGraph G,VexType x)
{
	for(int i=0; i
		if(x==G.Vex[i].data)
		return i;
	return -1;  //没找到 
}
 
void insertedge(ALGraph &G, int i, int j)  //头插法插入一条边 
{
	AdjNode *s;
	s=new AdjNode;
	s->v-j;
	s->next=G.Vex[i].first;
	G.Vex[i].first=s;
}
 
void print(ALGraph G)  //输出邻接表
{
	cout<<"------邻接表如下------"<
	for(int i=0; i
	{
		AdjNode *t=G.Vex[i].first;
		cout<"：";
		while(t!=NULL)
		{
			cout<<"["<v<<"] ";
			t=t->next;
		}
		cout<
	} 
} 
 
void CreateALGraph(ALGraph &G)  //创建有向图邻接表
{
	int i,j;
	VexType u,v;
	cout<<"请输入顶点数和边数："<
	cin>>G.vexnum>>G.edgenum;
	cout<<"请输入顶点信息："<
	for(i=0; i//输入顶点信息，存入顶点信息数组
		cin>>G.Vex[i].data;
	for(i=0; i
		G.Vex[i].first=NULL;
	cout<<"请依次输入每条边的两个顶点u,v"<
	while(G.edgenum--)
	{
		cin>>u>>v;
		i=locatevex(G,u);  //查找顶点u的存储下标 
		j=locatevex(G,v);  //查找顶点v的存储下标 
		if(i!=-1&&j!=-1)
			insertedge(G,i,j);
		else
		{
			cout<<"输入顶点信息错！请重新输入！"<
			G.edgenum++;//本次输入不算 
		}
	} 
} 
 
void DFS_AL(ALGraph G,int v)  //基于邻接表的深度优先遍历 
{
	int w;
	AdjNode *p;
	cout<"\t";
	visited[v]=true;
	p=G.Vex[v].first;
	while(p)  //依次检查v的所有邻接点 
	{
		w=p->v;  //w为v的邻接点 
		if(!visited[w])  //w未被访问 
		  DFS_AL(G,w);  //从w出发，递归深度优先遍历 
		p=p->next;
	} 
}
 
void DFS_AL(ALGraph G)
{
	for(int i=0; i
	if(!visited[i])
	   DFS_AL(G,i);
}
 
int main()
{
	ALGraph G;
	int v;
	VexType c; 
	CreateALGraph(G);
	print(G);
	cout<<"请输入连通图的起始点："<
	cin>>c;
	v=locatevex(G,c); //查找顶点u的存储下标 
	if(v!=-1)
	{
		cout<<"深度优先搜索遍历连通图结果："<
		DFS_AL(G,v); 
	}
	else
		cout<<"输出顶点信息出错！请重新输入！"<
	return 0;
}