DFS(小白式超详细讲解以及代码讲解) |
您所在的位置：网站首页 › 深度优先搜索遍历连通图 › DFS(小白式超详细讲解以及代码讲解) |
DFS(小白式超详细讲解以及代码讲解)
|
图的遍历算法是求解图的连通性，拓扑排序和关键路径等算法的基础。 根剧搜索路径的方向，通常有两条遍历图的路径： 深度优先搜索（DFS）和广度优先搜索（BFS）。 对于有向图和无向图都适用。 DFS DFS类似于树的先序遍历，是树的先序遍历的推广。 那么对于一个联通图来说，深度搜索遍历的过程如下： 1.从图中某个顶点v出发，访问v; 2.找出刚访问过得顶点的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复此步骤，直至访问过的顶点没有未被访问的邻接点为止。 3.返回前一个访问过的且乃有未被访问的邻接点的顶点，找出下一个未被访问的邻接点，访问该顶点。 4.重复（2）（3），直至所以的顶点都被访问过，搜索结束。 代码实现如下： bool visited[maxn];//访问标志数组，初值为false; void DFS(Graph G,int v){//从顶点v出发递归的深度优先遍历图G cout//图G为邻接矩阵类型，从第v个顶点出发深度优先搜索遍历图G cout//边链表非空 w = p -> adjvex;//如果w是v的邻接点 if(!visited[w]) DFS(G,w);//如果w未访问，则递归调用DFS； p = p -> nextarc;//指向下一个边结点 } }好了，最基础的理论知识我们已经了解完了，接下来我们要跟深一步了解这个算法，并写代码做题了 DFS算法思想：一直往深处走，直到找到解或者走不下去为止； 一般DFS使用栈保存未被检测的结点，结点深度优先的次序被访问并被依次压入栈中，并以相反的次序出栈进行新的检测。 深搜解决栗子：走迷宫。不撞南墙不回头！ 下面是我做题的一个基础模板！ #include using namespace std; const int maxn = 100; bool vis[maxn][maxn];//访问标记 int mapp[maxn][maxn];//坐标范围 bool check(int x,int y){//边界条件和约束条件的判断 if(!vis[x][y] && ...)//满足条件 return 1; else return 0; } void DFS(int x,int y){ vis[x][y] = 1;//标记该节点被访问 if(mapp[x][y] == G){//出现目标态G ...//做相应处理 return ; } for(int i=0;i ..... return 0; }DFS实现全排列 思路：我们可以这样来想： 1.首先我们考虑1号盒子，我们约定每到一个盒子面前都按数字递增的顺序摆放扑克牌。于是把1号扑克牌放到1号盒子中。 2.接着考虑2号盒子，现在我们手里剩下2号和3号扑克牌，于是我们可以把2号扑克牌放入2号盒子中。于是在3号盒子只剩一种可能性，我们继续把3号扑克放入3号盒子。此时产生了一种排列——{1,2,3}。 3.接着我们收回3号盒子中的3号扑克牌，尝试一种新的可能，此时发现别无他选。于是选择回到2号盒子收回2号扑克。 4.在2号盒子中我们放入3号扑克，于是自然而然的在3号盒子中只能放入2号扑克。此时产生另一种排列——{1,3,2}； 5.重复以上步骤就能得到数字{123}的全排列。 #include using namespace std; int a[101],b[101],n; void print() { int i; for(i=1;i int j; if(i==n+1) { print(); return; } for(j=1;j a[i]=j; b[j]=1; dfs(i+1); b[j]=0; } } } int main() { ios::sync_with_stdio(false); cin>>n; dfs(1); return 0; }我简单的写了一下运行过程，大家可以自己调试着这段程序理解一下！ |
深度优先搜索遍历连通图 1）从图中某个顶点出发，访问v，并置visited[v]的值为true. 2) 依次检查v的所有的邻接点w，如果visited[w]的值为false,再从w出发进行递归遍历，直至图中所有的顶点都被访问过。
【本文地址】
今日新闻 |
推荐新闻 |