不知道用这种方法实现单源路径问题是否可以

首页课程实战体系课手记专栏慕课教程

不知道用这种方法实现单源路径问题是否可以

来源：4-5 单源路径问题的编程实现

scanf莺曲

2019-07-28

（不好意思第一次提问可能表达不清还请老师见谅）
这是老师的源代码提的问题在注释里

public SingleSourcePath(Graph G, int s){

        G.validateVertex(s);

        this.G = G;
        this.s = s;
        visited = new boolean[G.V()];
        pre = new int[G.V()]; //在这里预设pre的值为-1

        dfs(s, s);
    }

    private void dfs(int v, int parent){  //这里不需要参数parent

        visited[v] = true;
        pre[v] = parent; // 删除这行代码
        for(int w: G.adj(v))
            if(!visited[w])
	            // pre[w] = v // 在这里添加代码
                dfs(w, v);
    }

不晓得这个方法是否可以

写回答

1回答

liuyubobobo

liuyubobobo

2019-07-29

已采纳

赞！完全没有问题：）

不过这样做，相当于对初始点s没有操作，所以需要在外面递归调用前，写一句 pre[s] = s（如果pre的初始值是-1，且你需要保证pre的语义的话：））

我在课程中的写法，在dfs每次遍历到一个顶点的时候，对当前顶点的pre赋值；

你的做法是在搜索相邻顶点的时候，对相邻顶点的pre赋值。但是，初始点不是任何点的相邻顶点，所以要单独考虑一下。

另外，在这里，我引用parent这个参数，也是为后续我们写环检测的代码打基础：）

其他没有任何问题：）大赞！：）

继续加油！：）

1

1

scanf莺曲

首先感谢bobo老师的回答对于我目前的学习来说看到parent这一参数可能会有些多余，既然是为了接下来环检测的课程做一个基础，那我非常期待接下来的课程，也相信它会更好谢谢老师晚安：)

2019-07-29

共1条回复

玩转算法系列--图论精讲（Java版）

30+小时系统学习，bobo带你克服被图论支配的恐惧

1591 学习 · 324 问题

相似问题

单源路径问题

回答 1

遍历两点之间所有路径问题

回答 1

不进行状态压缩实现水桶问题的疑问

回答 1

关于有向图的数据结构（实现）

回答 1

求TSP问题的算法

回答 1

打开慕课网App查看更多内容