精华内容
下载资源
问答
  • 6.对无向图的深度优先遍历图解 7.对有向图的深度优先遍历 二:广度优先遍历 1.定义 2.搜索步骤 3.图表达流程 举例: 代码实现: 4.对无向图的广度优先遍历图解 5.对有向图的广度优先遍历图解 三:异同 1....

    目录:

    一:深度优先遍历

    1.定义 

    2.图表达流程

    举例:

    代码实现:

    3.对于连通图

    4.对于非连通图

    5.深度优先搜索

    6.对无向图的深度优先遍历图解

    7.对有向图的深度优先遍历

    二:广度优先遍历

    1.定义 

    2.搜索步骤

    3.图表达流程

    举例:

    代码实现:

    4.对无向图的广度优先遍历图解

    5.对有向图的广度优先遍历图解

    三:异同

    1.同

    2.异

    A:深度优先

    B:而广度优


    图的遍历和树的遍历类似

    我们希望 从图中某一顶点触发,遍历图中其余顶点

    且使每一个顶点仅被访问一次,这一过程就叫做图的遍历(Traversing Graph)

    一:深度优先遍历

    1.定义 

    称为 深度优先搜索,简称 DFS

    二叉树的前序、中序、后序遍历,本质上也可以认为是深度优先遍历,深度优先搜索是先序遍历的推广

    https://www.cnblogs.com/nr-zhang/p/11236369.html

     

     深度优先遍历(Depth First Search)的主要思想是:

    A:首先以一个未被访问过的顶点作为起始顶点

    沿当前顶点的边走未访问过的顶点

    B:没有未访问过的顶点时则回到上一个顶点

    继续试探别的顶点,至所有的顶点都被访问过

    2.图表达流程

    è¿éåå¾çæè¿°

    è¿éåå¾çæè¿°

    è¿éåå¾çæè¿°

    A:1.从v = 顶点1开始出发,先访问顶点1 

    B:2.按深度优先搜索递归访问v的某个未被访问的邻接点2

    C:顶点2结束后,应该访问3或5中的某一个

    D:这里为顶点3,此时顶点3不再有出度,因此回溯到顶点2

    E:再访问顶点2的另一个邻接点5,由于顶点5的唯一一条边的弧头为3,已经访问了

    F:所以此时继续回溯到顶点1,找顶点1的其他邻接点。

     

    举例:

    上图可以用邻接矩阵来表示为:

    int maze[][] = {
        { 0, 1, 1, 0, 0 },
        { 0, 0, 1, 0, 1 },
        { 0, 0, 1, 0, 0 },
        { 1, 1, 0, 0, 1 },
        { 0, 0, 1, 0, 0 }
    };

    代码实现:

    具体的代码如下:

    import java.util.LinkedList;
    import classEnhance.EnhanceModual;
    
    public class DepthFirst extends EnhanceModual {
    
        @Override
        public void internalEntrance() {
            // TODO Auto-generated method stub
            int maze[][] = { { 0, 1, 1, 0, 0 }, { 0, 0, 1, 0, 1 }, { 0, 0, 1, 0, 0 }, { 1, 1, 0, 0, 1 },
                    { 0, 0, 1, 0, 0 } };
    
            dfs(maze, 1);
    
        }
    
        public void dfs(int[][] adjacentArr, int start) {
            int nodeNum = adjacentArr.length;
            if (start <= 0 || start > nodeNum || (nodeNum == 1 && start != 1)) {
                System.out.println("Wrong input !");
                return;
            } else if (nodeNum == 1 && start == 1) {
                System.out.println(adjacentArr[0][0]);
                return;
            }
    
            int[] visited = new int[nodeNum + 1];//0表示结点尚未入栈,也未访问
            LinkedList<Integer> stack = new LinkedList<Integer>();
            stack.push(start);
            visited[start] = 1;//1表示入栈
    
            while (!stack.isEmpty()) {
                int nodeIndex = stack.peek();
                boolean flag = false;
                if(visited[nodeIndex] != 2){
                    System.out.println(nodeIndex);
                    visited[nodeIndex] = 2;//2表示结点被访问
                }
    
                //沿某一条路径走到无邻接点的顶点
                for (int i = 0; i < nodeNum; i++) {
                    if (adjacentArr[nodeIndex - 1][i] == 1 && visited[i + 1] == 0) {
                        flag = true;
                        stack.push(i + 1);
                        visited[i + 1] = 1;
                        break;//这里的break不能掉!!!!
                    }
                }
    
                //回溯
                if(!flag){
                    int visitedNodeIndex = stack.pop();
                }
    
            }
        }
    
    }

     

    3.对于连通图

    A:它从图中某个顶点 触发,访问此顶点

    B:然后从  的未被访问邻接点出发深度优先遍历图

    C:直至图中所有和 有路径相通的顶点都被访问到

    4.对于非连通图

    只需要对它的连通分量分别进行深度优先遍历

    A:即在先前一个顶点进行一次深度优先遍历后

    B:若图中尚未有顶点未被访问

    则另选图中一个未曾被访问的顶点作为起始点

    C:重复上述过程,直至图中所有顶点都被访问到为止

    5.深度优先搜索

    就是选择一个顶点开始走

    期间对于走过的顶点就不在访问其他未被访问的

    一直走到无路可走

    此时有顶点走过,选择一个,重复上述过程

    6.对无向图的深度优先遍历图解

    以下"无向图"为例:

    对上无向图进行深度优先遍历,从A开始:

    第1步:访问A。

    第2步:访问B(A的邻接点)。 在第1步访问A之后,接下来应该访问的是A的邻接点,即"B,D,F"中的一个。但在本文的实现中,顶点ABCDEFGH是按照顺序存储,B在"D和F"的前面,因此,先访问B。

    第3步:访问G(B的邻接点)。 和B相连只有"G"(A已经访问过了)  

    第4步:访问E(G的邻接点)。 在第3步访问了B的邻接点G之后,接下来应该访问G的邻接点,即"E和H"中一个(B已经被访问过,就不算在内)。而由于E在H之前,先访问E。

    第5步:访问C(E的邻接点)。 和E相连只有"C"(G已经访问过了)。

    第6步:访问D(C的邻接点)。 

    第7步:访问H。因为D没有未被访问的邻接点;因此,一直回溯到访问G的另一个邻接点H。

    第8步:访问(H的邻接点)F。

    因此访问顺序是:A -> B -> G -> E -> C -> D -> H -> F

    7.对有向图的深度优先遍历

    有向图的深优先遍历图解:

    对上有向图进行深度优先遍历,从A开始:

    第1步:访问A。

    第2步:访问(A的出度对应的字母)B。 在第1步访问A之后,接下来应该访问的是A的出度对应字母,即"B,C,F"中的一个。但在本文的实现中,顶点ABCDEFGH是按照顺序存储,B在"C和F"的前面,因此,先访问B。

    第3步:访问(B的出度对应的字母)F。 B的出度对应字母只有F。 

    第4步:访问H(F的出度对应的字母)。 F的出度对应字母只有H。 

    第5步:访问(H的出度对应的字母)G。

    第6步:访问(G的出度对应字母)E。 在第5步访问G之后,接下来应该访问的是G的出度对应字母,即"B,C,E"中的一个。但在本文的实现中,顶点B已经访问了,由于C在E前面,所以先访问C。

    第7步:访问(C的出度对应的字母)D。

    第8步:访问(C的出度对应字母)D。 在第7步访问C之后,接下来应该访问的是C的出度对应字母,即"B,D"中的一个。但在本文的实现中,顶点B已经访问了,所以访问D。

    第9步:访问E。D无出度,所以一直回溯到G对应的另一个出度E。

    因此访问顺序是:A -> B -> F -> H -> G -> C -> D -> E

     

    二:广度优先遍历

    1.定义 

    又称为 广度优先搜索,简称 BFS

    广度优先遍历(Depth First Search)的主要思想是:类似于树的层序遍历

    https://www.cnblogs.com/nr-zhang/p/11236369.html

     

    A:广度优先搜索是按层来处理顶点

    B:距离开始点最近的那些顶点首先被访问

    C:最远的那些顶点则最后被访问

    2.搜索步骤

    A :首先选择一个顶点作为起始顶点,并将其染成灰色,其余顶点为白色。 
    B:将起始顶点放入队列中。 
    C:从队列首部选出一个顶点

    并找出所有与之邻接的顶点

    将找到的邻接顶点放入队列尾部

    将已访问过顶点涂成黑色,没访问过的顶点是白色

    如果顶点的颜色是灰色,表示已经发现并且放入了队列

    如果顶点的颜色是白色,表示还没有发现 
    D:按照同样的方法处理队列中的下一个顶点。 
    基本就是出队的顶点变成黑色,在队列里的是灰色,还没入队的是白色。  

    3.图表达流程

    用一副图来表达这个流程如下:

    è¿éåå¾çæè¿°

    A:初始状态,从顶点1开始,队列={1} 

    è¿éåå¾çæè¿°

    B:访问1的邻接顶点,1出队变黑,2,3入队,队列={2,3,} 

    è¿éåå¾çæè¿°

    C:访问2的邻接顶点,2出队,4入队,队列={3,4} 

    è¿éåå¾çæè¿°

    D:访问3的邻接顶点,3出队,队列={4} 

    è¿éåå¾çæè¿°

    E:5.访问4的邻接顶点,4出队,队列={ 空} 

    从顶点1开始进行广度优先搜索: 

     初始状态,从顶点1开始,队列={1} 
      访问1的邻接顶点,1出队变黑,2,3入队,队列={2,3,} 
      访问2的邻接顶点,2出队,4入队,队列={3,4} 
      访问3的邻接顶点,3出队,队列={4} 
      访问4的邻接顶点,4出队,队列={ 空} 
      顶点5对于1来说不可达

    举例:

    上面图可以用如下邻接矩阵来表示:

    int maze[][] = {
        { 0, 1, 1, 0, 0 },
        { 0, 0, 1, 1, 0 },
        { 0, 1, 1, 1, 0 },
        { 1, 0, 0, 0, 0 },
        { 0, 0, 1, 1, 0 }
    };

    代码实现:

    具体的代码如下,这段代码有两个功能,bfs()函数求出从某顶点出发的搜索结果,minPath()函数求从某一顶点出发到另一顶点的最短距离:

    import java.util.LinkedList;
    
    import classEnhance.EnhanceModual;
    
    public class BreadthFirst extends EnhanceModual {
    
        @Override
        public void internalEntrance() {
            // TODO Auto-generated method stub
            int maze[][] = {
                { 0, 1, 1, 0, 0 }, 
                { 0, 0, 1, 1, 0 }, 
                { 0, 1, 1, 1, 0 },
                { 1, 0, 0, 0, 0 },
                { 0, 0, 1, 1, 0 }
            };
    
            bfs(maze, 5);//从顶点5开始搜索图
    
            int start = 5;
            int[] result = minPath(maze, start);
            for(int i = 1; i < result.length; i++){
                if(result[i] !=5 ){
                    System.out.println("从顶点" + start +"到顶点" + i + "的最短距离为:" + result[i]);
                }else{
                    System.out.println("从顶点" + start +"到顶点" + i + "不可达");
                }
            }
        }
    
        public void bfs(int[][] adjacentArr, int start) {
            int nodeNum = adjacentArr.length;
            if (start <= 0 || start > nodeNum || (nodeNum == 1 && start != 1)) {
                System.out.println("Wrong input !");
                return;
            } else if (nodeNum == 1 && start == 1) {
                System.out.println(adjacentArr[0][0]);
                return;
            }
    
            int[] visited = new int[nodeNum + 1];//0表示顶点尚未入队,也未访问,注意这里位置0空出来了
            LinkedList<Integer> queue = new LinkedList<Integer>();
            queue.offer(start);
            visited[start] = 1;//1表示入队
    
            while (!queue.isEmpty()) {
                int nodeIndex = queue.poll();
                System.out.println(nodeIndex);
                visited[nodeIndex] = 2;//2表示顶点被访问
    
                for (int i = 0; i < nodeNum; i++) {
                    if (adjacentArr[nodeIndex - 1][i] == 1 && visited[i + 1] == 0) {
                        queue.offer(i + 1);
                        visited[i + 1] = 1;
                    }
                }
            }
        }
    
        /*
         * 从start顶点出发,到图里各个顶点的最短路径
         */
        public int[] minPath(int[][] adjacentArr, int start) {
    
            int nodeNum = adjacentArr.length;
    
            LinkedList<Integer> queue = new LinkedList<Integer>();
            queue.offer(start);
            int path = 0;
            int[] nodePath = new int[nodeNum + 1];
            for (int i = 0; i < nodePath.length; i++) {
                nodePath[i] = nodeNum;
            }
            nodePath[start] = 0;
    
            int incount = 1;
            int outcount = 0;
            int tempcount = 0;
    
            while (path < nodeNum) {
                path++;
                while (incount > outcount) {
                    int nodeIndex = queue.poll();
                    outcount++;
    
                    for (int i = 0; i < nodeNum; i++) {
                        if (adjacentArr[nodeIndex - 1][i] == 1 && nodePath[i + 1] == nodeNum) {
                            queue.offer(i + 1);
                            tempcount++;
                            nodePath[i + 1] = path;
                        }
                    }
                }
    
                incount = tempcount;
                tempcount = 0;
                outcount = 0;
            }
    
            return nodePath;
        }
    
    }

    运行结果:

    //5
    //3
    //4
    //2
    //1
    //从顶点5到顶点1的最短距离为:2
    //从顶点5到顶点2的最短距离为:2
    //从顶点5到顶点3的最短距离为:1
    //从顶点5到顶点4的最短距离为:1
    //从顶点5到顶点5的最短距离为:0

     

    4.对无向图的广度优先遍历图解

    A:从A开始,有4个邻接点,“B,C,D,F”,这是第二层;

    B:在分别从B,C,D,F开始找他们的邻接点,为第三层。以此类推。

    因此访问顺序是:A -> B -> C -> D -> F -> G -> E -> H

    5.对有向图的广度优先遍历图解

    因此访问顺序是:A -> B -> C -> F -> D -> H -> G -> E

     

    三:异同

    1.同

    深度优先遍历与广度优先遍历算法在时间复杂度上是一样的

    2.异

    不同之处仅仅在于对顶点访问的顺序不同

    A:深度优先

    更适合目标比较明确,以找到目标为主要目的的情况

     

    B:而广度优

    先更适合在不断扩大遍历范围时找到相对最优解的情况

    参考地址:

    1.图的深度优先遍历(DFS)和广度优先遍历(BFS)算法分析

    https://www.cnblogs.com/zxrxzw/p/11528482.html

    2.图的深度优先遍历和广度优先遍历

    https://www.cnblogs.com/nr-zhang/p/11236369.html

    3.深度优先遍历(DFS)和广度优先遍历(BFS)

    https://blog.csdn.net/yimixgg/article/details/90023121

    展开全文
  • 图的深度优先遍历

    2019-03-15 16:07:00
    深度优先遍历 深度就是不断往下渗透, 然后标记是否访问过,如果没有就继续往下渗透,然后再往上回到当初位置 就和树递归差不多 这是一个 我们从中可以看到 0有四个连接点 0 1 2 5 6 我们要把遍历出来...

    深度优先遍历

    深度就是不断往下渗透,

    然后标记是否访问过,如果没有就继续往下渗透,然后再往上回到当初的位置

    就和树递归差不多

     

    这是一个图

    我们从图中可以看到 0有四个连接点 0 1 2 5 6 我们要把遍历出来

    遍历流程(红色没有访问过 蓝色是标记 访问 最后都会变成红色 )

    我们从零开始,然后往下渗透到1,没有元素了 然后再往上回溯, 再往2

     

    0 1遍历了

    然后1 回到0

    1颜色变回红色

    0 然后再去遍历2

    又回到0 颜色变回红色

    然后

    又去5节点,

    5的节点有0 3 4

    但是0是蓝色 所以已经遍历过了

    所以就不在遍历0 往下继续遍历

    下一个是3 我们就遍历她

    3有4 5 但是5 已经遍历了 所以我们继续往下遍历 4

     

    4遍历了继续往下遍历 在遍历 6

    已经遍历完了

     

     

     

    最后就是这样的了

     

     

     

    联通分量就是 看多少个图

    看的是连通性

    这就是三个图

    需要标记是否被访问过 visited来访问

    //图的深度优先遍历
        void dfs(int v){
            
            visited[v]=true;
            id[v]=ccount;
            
            for(int i:G.adj(v)){
                if(!visited[i])
                    dfs(i);
            }
        }

    package com.binglian.Graph;
    
    //求无权图的联通分量
    public class Components {
    
    	Graph G;					//图的引用
    	private boolean[] visited;	//记录dfs的过程中节点是否被访问
    	private int ccount;			//记录联通分量个数
    	private int[] id;			//每个节点对应的联通分量标记
    	
    	
    	//图的深度优先遍历
    	void dfs(int v){
    		
    		visited[v]=true;
    		id[v]=ccount;
    		
    		for(int i:G.adj(v)){
    			if(!visited[i])
    				dfs(i);
    		}
    	}
    	
    	//构造函数,求出无权图的联通分量
    	public Components(Graph graph){
    		
    		//算法初始化
    		G=graph;
    		visited=new boolean[G.V()];
    		id=new int[G.V()];
    		ccount=0;
    		for(int i=0;i<G.V();i++){
    			visited[i]=false;
    			id[i]=-1;
    		}
    		
    		//求图的联通分量
    		for(int i=0;i<G.V();i++)
    			if(!visited[i]){//判断是否访问没有 如果没有访问就进行递归dfs
    				dfs(i);
    				ccount++;
    			}
    	}
    	
    	
    	//返回图的联通分量个数
    	int count(){
    		return ccount;
    		
    	}
    	
    	//查询点v和w是否联通
    	boolean isConnected(int v,int w){
    		assert v>=0 && v<G.V();
    		assert w>=0 && w<G.V();
    		
    		return id[v]==id[w];
    	}
    	
    }
    

     

    展开全文
  • 遍历流程 以无向为例 邻接矩阵,该邻接矩阵纵坐标(i)为访问起点,而横坐标(j)代表访问终点 (1)起点为2,先将Visited数组(Bool)当中,表示为2结点,标记为1,代表已经访问 (2)查看纵坐标i=2行,...

    遍历流程

    以无向图为例
    邻接矩阵,该邻接矩阵纵坐标(i)为访问的起点,而横坐标(j)代表访问终点
    在这里插入图片描述

    (1)起点为2,先将Visited数组(Bool)当中,表示为2的结点,标记为1,代表已经访问
    (2)查看纵坐标i=2的行,其中横坐标j=1的列,发现邻接矩阵对应值为1,说明点2的邻接点1,还没有被访问,于是我们访问点1
    (4)访问点1,Visited数组(Bool)当中,表示为2的结点,标记为1,再跳转到i=1的行,横坐标i=2,但点2已经被访问,而i=3,点3还没有被访问
    (4)访问点3,同理,重复步骤(邻接矩阵中,值为1,但没有被访问的点)
    (5)访问点5 ,但i=5的行中,j=2,3(点2,点3)均被访问过,回退到i=3的行
    (6)i=3的行,也全访问了,回退到i=1的行,发现j=4还没有被访问过
    (7)访问点4
    (8)访问点6,访问完i=6的行,发现全访问过了,回退到点4,点1,点2的行
    (9)回到点2的行后,发现全访问了,深度优先遍历结束

    在这里插入图片描述
    对于上图中AMGraph G(图的邻接矩阵存储结构)定义如下:

    # define MaxVertexNum 100     //顶点(结点)数目的最大值
    typedef char VertexType;      //顶点的数据类型
    typedef int EdgeType;         //带权图中边上权值的数据类型(这里指邻接矩阵的权值的数据类型,如0,1)
    typedef struct{
      VertexType Vex[MaxVertexNum];    //顶点表,结点的值,如结点值为1
      EdgeType Edge[MaxVertexNum][MaxVertexNum];   //邻接矩阵,描述边关系的表
      int vexnum,arcnum;        //图当前顶点数和边(弧)数
    }AMGragh
    

    参考链接
    https://www.bilibili.com/video/BV1qt411171s?from=search&seid=3497279112733240296

    此文章,图的定义代码实现,有所不同
    https://blog.csdn.net/qq_35385687/article/details/90453458?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param

    展开全文
  • 操作结果:对图进行深度优先遍历,在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit()失败,则操作失败 BFSTraverse(G,Visit()) 初始条件:G存在,Visit是顶点应用函数 操作结果:对图进行广度优先...
  • DFS是被广泛运用搜索算法,它属于一种盲目...3、若此时中尚有顶点未被访问,则再选其中一个顶点作为起始顶点并访问之,转 2; 反之,遍历结束。 大多数时候我们用dfs时会采用递归方式,但是非递归方式更...

    DFS是被广泛运用的搜索算法,它属于一种盲目搜索,定义如下:

    1、起始访问的顶点是指定的;

    2、若当前访问的顶点的邻接顶点有未被访问的,则任选一个访问;反之,退回到最近访问过的顶点;直到与起始顶点相通的全部顶点都访问完毕;

    3、若此时图中尚有顶点未被访问,则再选其中一个顶点作为起始顶点并访问之,转 2; 反之,遍历结束。

        大多数时候我们用dfs时会采用递归的方式,但是非递归的方式更加直观,思路更清晰,更便于我们去理解”深度“的思想。这篇文章主要介绍如何用unity引擎来可视化模拟非递归的dfs算法。为了方便理解,给出一个经典的红黑格题目,要求如下:

        有一个长方形的房间,房间里的地面上布满了正方形的瓷砖,瓷砖要么是红色的,要么是黑色的。一个人站在其中一块黑色的瓷砖上,他可以向四周的瓷砖上移动,但是不能移动到红色的瓷砖上,只能在黑色的瓷砖上移动,用深度优先搜索的思想模拟该过程。

        输入数据有三个,分别是房间的长和宽,以及一个字符串。字符串含有房间中砖块的颜色信息,例如“#”表示黑色瓷砖,“*”表示红色瓷砖,“@”表示该位置的黑色瓷砖,那么字符串可以是

    "***#**######@#***##**#***##***#***#****##*###*#**"

    (注意,长和宽的乘积应该和字符串字符数相同。)

    脚本代码如下(c#):

    using System.Collections;
    using System.Collections.Generic;
    using UnityEngine;
    using System.Threading;
    using System;
    using UnityEditor;
    
    public class NewBehaviourScript : MonoBehaviour
    {
        public GameObject redcube, blackcube, yellowcube, origncube, Ethan;
        public string Str1;
        public int weight, height;
        private int k = 0;
        public char[,] map;
        public int[] path;//记录走过的坐标
        private int[] dx = { 1, -1, 0, 0 }, dy = { 0, 0, 1, -1 };
        public int[,] visited;//记录每一块砖走过的次数
        private int cnt = 0, row = 0, cnt2 = 0;
        private int sx = 0, sy = 0;
        public float time = 0;
        private bool moved = false, isbacking = false, once = false;
        private float deltaposxy = 4.2f, deltaposz = 0.27f;
        void Start()
        {
            //初始化map 生成地图
            Transform temp = transform;
            temp.position = new Vector3(orign.transform.position.x, 0, orign.transform.position.z);
            visited = new int[weight, height];
            map = new char[weight, height];
            path = new int[weight * height * 100];
            for (int j = 0; j < height; j++)
            {
                for (int i = 0; i < weight; i++)
                {
                    if (Str1[k] == '*')
                    {
                        map[i, j] = Str1[k];
                        temp.position = new Vector3(orign.transform.position.x + i * deltaposxy, 0, orign.transform.position.z + j * deltaposxy);
                        GameObject ared = Instantiate(red, temp.position, temp.rotation);
                        k++;
                        continue;
                    }
                    if (Str1[k] == '#')
                    {
    
                        map[i, j] = Str1[k];
                        temp.position = new Vector3(orign.transform.position.x + i * deltaposxy, 0, orign.transform.position.z + j * deltaposxy);
                        GameObject ablack = Instantiate(black, temp.position, temp.rotation);
                        k++;
                        continue;
                    }
                    if (Str1[k] == '@')
                    {
                        map[i, j] = Str1[k];
                        sx = i; sy = j;
                        temp.position = new Vector3(orign.transform.position.x + i * deltaposxy, 0, orign.transform.position.z + j * deltaposxy);
                        GameObject ayellow = Instantiate(yellow, temp.position, temp.rotation);
                        k++;
                        continue;
                    }
                }
            }
            k = 0;
            gameObject.transform.position = new Vector3(orign.transform.position.x + sx * deltaposxy, deltaposz, orign.transform.position.z + sy * deltaposxy);
            dfs();
        }
        private int j = 0;
        void Update()
        {
            time++;
            if (time % 30 == 0)
            {
                if (cnt2 > 0)
                {
                    Transform temp = transform;
                    temp.position = new Vector3(orign.transform.position.x + path[j] * deltaposxy, deltaposz, orign.transform.position.z + path[j + 1] * deltaposxy);
                    GameObject aethan = Instantiate(Ethan, temp.position, temp.rotation);
                    j += 2;
                    Destroy(aethan, 0.35f);
                    cnt2--;
                }
            }
        }
        void dfs()
        {
            visited[sx, sy] = 1;//标记1表示Ethan走过此砖一次
            cnt++;
            while (true)
            {
                for (int i = 0; i < 4; i++)
                {
                    int nx = sx + dx[i], ny = sy + dy[i];//前后左右选择一个方向判断
    
                    if (nx >= 0 && nx < weight && ny >= 0 && ny < height)
                    {
                        if (visited[nx, ny] == 0 && map[nx, ny] != '*')//找到了某一方向有从未走过的砖,前进
                        {
                            path[row] = nx; row++;
                            path[row] = ny; row++;
                            moved = true;
                            //在返回的途中发现没走过的砖,将现在脚下拐弯的砖标记为1(原本应该标记为2),因为后面一定还会至少再经过一次
                            if (isbacking == true) visited[sx, sy] = 1; //
                            isbacking = false;
                            sx = nx; sy = ny;
                            visited[sx, sy] = 1;//将走过一次的砖标记为1
                            cnt++;
                            cnt2++;
                            time = 0;
                            break;
                        }
                    }
    
                }
                if (moved == true)
                {
                    moved = false;
                    continue;
                }
                //前后左右都不存在没走过的砖,此时找走过一次的砖
                for (int i = 0; i < 4; i++)
                {
                    int nx = sx + dx[i], ny = sy + dy[i];//前后左右选择一个方向判断
                    if (nx >= 0 && nx < weight && ny >= 0 && ny < height)
                    {
                        if (visited[nx, ny] == 1 && map[nx, ny] != '*')//找到了某一方向有走过一次的砖,前进
                        {
                            path[row] = nx; row++;
                            path[row] = ny; row++;
                            moved = true;
                            sx = nx; sy = ny;
                            visited[sx, sy] = 2;//将走过两次的砖标记为2
                            isbacking = true;
                            time = 0;
                            cnt2++;
                            break;
                        }
                    }
                }
                if (moved == true)
                {
                    moved = false;
                    continue;
                }
                Debug.Log(cnt);
                break;
            }
        }
    }
    

    将此脚本挂在一个空物体上,并在unity中给脚本的每一个数据成员赋上初始值,点击开始就可以开到模拟出的dfs算法思路。效果如下:

     


    谢谢观看:)

     

     

     

     

     

    展开全文
  • 深度优先遍历

    2020-08-17 16:46:16
    深度优先遍历的非递归需要借助栈来实现,如下图的 正确遍历顺序是AGFBCED。 栈S正确的工作流程是下图: 下面用ADL语言 DFS(Head v0,visited,visited) DFS[初始化] CREATE[S]; FOR i=1 TO n DO visited[vi]<–0 ...
  • 深度优先遍历的实现分两种一种是递归的,一种是非递归的。递归比较简单,这里我说一下非递归的实现。注:这种对树形数据的深度遍历在开发中比较常见,于是封装过程中业务逻辑部分尽量自定义。便阿里的流程写死。 ...
  • 流程: 1,利用栈实现 2,从源节点开始把节点按照深度放入栈,然后弹出 3,每弹出一个点,把该节点下一个没有进过栈的邻接点放入栈 4,直到栈变空图的表示和生成见:点击打开链接import java.util.HashSet;...
  • 这里写自定义目录标题排序二叉树c++实现新改变功能快捷键合理创建标题,有助于目录生成如何改变文本样式插入链接与图片如何插入一段漂亮代码片...,丰富你文章UML 图表FLowchart流程图导出与导入导出导入...
  • 二叉树深度优先遍历的非递归算法

    千次阅读 2011-09-04 23:49:53
    void PreOrder(BiTree T) { // 基于方法一,流程图如右,当型循环  InitStack(S);  while ( T!=NULL || !StackEmpty(S))  {  while ( T != NULL )  {
  • 图的深度优先遍历 深度优先搜索基本思想 从图中某个顶点V0出发,首先访问V0; 找出刚访问过的顶点的第一个未被访问的邻接点,然后访问该顶点。以该顶点为新顶点,重复此步骤,直到刚访问过的顶点没有未被访问的邻...
  • 深广度优先遍历

    2020-08-21 15:35:30
    游戏中可以用来做寻路算法,以为深度优先遍历不一定是最短路径,所以最好还是用A*算法去做寻路 步骤: //简称为DFS(depth first search) //流程:沿着一条路走到底,如果走不通,退回到上一个节点继续走下一个方向。...
  • 技术类项目-选品:为方便各业务模块在做营销活动时能够根据...整体流程图: 3、执行筛选流程 (1) 调用筛选服务启动筛选任务: ADMarketingSelectionServiceImpl.executeSelection(long id, ADMarketingSelec...
  • 2、深度优先搜索生成树:8会。 流程图: 实验六可能会停更了。 #include<stdio.h> #include<stdlib.h> #define TRUE 1 /*状态码预定义*/ #define FALSE 0 #define OK 1 #define ERROR 0 #define ...
  • C语言实现,用栈n皇后问题源码+流程图 深度优先遍历
  • 这个流程图的拓扑结构,如果采用图形深度优先遍历算法来遍历一遍,遍历顺序的部分应该是 开始活动-> A-1=>B-4=>E-5=>NEXT 这种运行顺序在实际流程运行过程中显然有问题,实际运行过程中从流程A-1...
  • 利用DFS遍历有向

    2021-03-25 23:35:06
      以下使用图的遍历算法来举例说明。 DFS 基本流程 深度优先搜索在搜索过程中访问某个顶点后,需要递归地访问此顶点的所有未访问过的相邻顶点。 初始条件下所有节点为白色,选择一个作为起始顶点,按照如下..
  • 今天在普元工作流的论坛上面,有一个帖子,上面有一个流程图,如下 这个流程图的拓扑结构,如果采用图形深度优先遍历算法来遍历一遍,遍历顺序的部分应该是 开始活动-> A-1=>B-4=>E-5=>NEXT 这种运行顺序在实际...
  • 编写一个程序,输出下面带权有向图的邻接表,并根据该邻接表,实现图的深度优先遍历算法,具体要求如下: (1)从顶点0开始的深度优先遍历序列(递归算法) (2)从顶点0开始的深度优先遍历序列(非递归算法) 三、实验...
  • 采用深度优先遍历图的方法,解决农夫过河的问题,有代码,有可执行文件和流程图
  • 图论——遍历算法

    2020-01-18 11:59:15
    深度优先搜索,以深度优先,直到走不下去,回退,对应数据结构stack 对于上dfs的流程如下 第一个节点0入栈,把0标记为已访问 遍历0所有邻接顶点,如果没有被访问就入栈,1入栈,1已访问 遍历1所有邻接...
  • 图像处理之基于图的广度优先搜索组件标记算法一:图的遍历与广度优先搜索算法图的遍历算法最常用是广度优先搜索算法(BFS)与深度优先搜索算法(DFS),从一个的节点开始,访问相邻的所有子节点,接着从这些子节点出发...
  • 深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来...
  • 4、掌握深度优先遍历和广度优先遍历算法在路径搜索问题中应用; 5、深入掌握遍历算法在求解实际问题中应用。 二、使用仪器、器材 微机一台 操作系统:WinXP 编程软件:C/C++编程软件 三、实验内容及原理 填...
  • 1 什么是结点的连通性?...深度优先遍历得到的是图的一个连通分量。 算法流程: 从某个结点 v 出发,访问结点 v,并令 vis[v] = 1; 查找 v 的所有邻接点 i,若结点 i 并未被访问过(vis[i] = 0),则从结点 i
  • 数据结构-

    2016-03-16 22:25:20
    本篇涉及到的知识点也比较多在图的遍历中介绍了深度优先遍历、广度优先遍历;在最小生成树节介绍了普利姆算法和克鲁斯卡尔算法;最短路径中介绍了迪杰斯特拉算法、佛洛依德算法;本篇后边还介绍了拓扑排序以及关键...
  • 2.掌握图的深度优先和广度优先遍历算法。 3.掌握克鲁斯卡尔算法生成最小生成树的方法。 4.掌握狄克斯特拉算法计算最短路径和最短路径长度的方法。 二、实验内容(或实验原理、实验拓扑) 1.采用克鲁斯卡尔...
  • 大话数据结构-

    2013-07-13 11:01:00
    本篇涉及到的知识点也比较多在图的遍历中介绍了深度优先遍历、广度优先遍历;在最小生成树节介绍了普利姆算法和克鲁斯卡尔算法;最短路径中介绍了迪杰斯特拉算法、佛洛依德算法;本篇后边还介绍了拓扑排序以及关键...

空空如也

空空如也

1 2 3
收藏数 60
精华内容 24
关键字:

图的深度优先遍历流程图