蓝桥-图3-深度优先遍历-地图最短路径

刺骨的言语ヽ痛彻心扉 2022-07-12 01:10 125阅读 0赞

package com.jkxy.photo;
    public class CityDeepTraverse {
        static  int[][] e={
       {
       0,0,0,0,0,0},
                            {
       0,0,2,99,99,10},
                            {
       0,99,0,3,99,7},
                            {
       0,4,99,0,4,99},
                            {
       0,99,99,99,0,5},
                            {
       0,99,99,3,99,0}};
         static int book[]={
       0,0,0,0,0,0,0,0,0,0,0,0};
         static int min=999999;
        public static void main(String[] args) {
          book[1]=1;
          dfs(1,0);
          System.out.println(min);
        }
        public static void dfs(int cur,int dis){
            int j;
            //if(dis>min) return;
            if(cur==5){
                if(dis<min) min=dis;
                return;
            }
            for(j=1;j<=5;j++){
                if(e[cur][j]!=99&&book[j]==0){
                    book[j]=1;
                    dfs(j,dis+e[cur][j]);
                    book[j]=0;
                }
            }
            return;
        }
    }
    //深度优先遍历-地图最短路径,前一参数为顶点，后一为总距离
    //(1,0)(2,2)(3,5)(4,9)(5,14)return回去(1,0)(2,2)(5,9)再return(1,0)(5,10)
    //首先定义图对应的二维数组
    //Main：标顶点1为已访问，从顶点1出发dfs(1,0)，坐等dfs()跑完传过来总距离输出
    //dfs(cur,dis)判断边界：是否到终点5，到则把距离赋给min（当前路线距离比前距离近的话）
    //未到则循环（j从1到5）判断cur能否到j，可到则标j为已访，深挖j，取消标记，挖到底则return回去，继续循环判断。

发表评论取消回复

表情：

评论列表（有 0 条评论，125人围观）

还没有评论，来说两句吧...

相关阅读

相关广度优先遍历与最短路径

广度优先遍历从某个顶点 v 出发，首先访问这个结点，并将其标记为已访问过，然后顺序访问结点v的所有未被访问的邻接点 \{vi,..,vj\} ，并将其标记为已访问过，然后将 \

左手的ㄟ右手/ 2024年03月17日 11:46/ 0 赞/ 9 阅读

相关深度优先搜索 - 最短路径

深度优先搜索 - 最短路径 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM

刺骨的言语ヽ痛彻心扉/ 2023年02月10日 03:56/ 0 赞/ 123 阅读

相关蓝桥-最短路径3-Bellman-Ford

package com.jkxy.photoDeep; public class BellmanFord { static int u[]={

川长思鸟来/ 2022年07月12日 03:06/ 0 赞/ 130 阅读

相关蓝桥-图5-广度优先遍历-转机最少

package com.jkxy.photo; import java.util.Hashtable; import java.util.Map;

ゝ一世哀愁。/ 2022年07月12日 02:18/ 0 赞/ 129 阅读

相关蓝桥-图3-深度优先遍历-地图最短路径

package com.jkxy.photo; public class CityDeepTraverse { static int[][]

刺骨的言语ヽ痛彻心扉/ 2022年07月12日 01:10/ 0 赞/ 126 阅读

相关蓝桥-图2-广度优先遍历初识

package com.jkxy.photo; public class WideTraverse { static int e[][]={

短命女/ 2022年07月12日 01:05/ 0 赞/ 104 阅读

相关图的遍历（深度优先遍历和广度优先遍历）

图的遍历就是从图中某个顶点出发，按某种方法对图中所有顶点访问且仅访问一次。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础深度优先遍历（depth-

柔光的暖阳◎/ 2022年04月13日 07:54/ 0 赞/ 338 阅读

相关图的广度优先遍历与深度优先遍历

一. 广度优先遍历(Depth-First Search) 在进行遍历时，从图的深度入手，使用栈从起始顶点遍历到与之相连的某条通路的末尾，没有路时再选择回退，即顶点元素出

港控/mmm°/ 2022年03月15日 06:48/ 0 赞/ 337 阅读

相关图的遍历（广度优先遍历、深度优先遍历）

图的数据结构 [https://blog.csdn.net/weixin\_43093501/article/details/89840219][https_blog.c

小灰灰/ 2022年02月05日 08:45/ 0 赞/ 394 阅读

相关图的深度优先遍历

一图遍历介绍所谓图的遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点，需要特定策略，一般有两种访问策略。 1 深度优先遍历 2 广度优先遍历

心已赠人/ 2021年07月24日 20:09/ 0 赞/ 424 阅读