图论基础 :: labuladong的算法小抄

[labuladong]

文章链接点这里：图论基础

评论礼仪 见这里，违者直接拉黑。

[labuladong]

收到，已修改

[moustacheyummy]

这句话：注意 Java 的语言特性，向 res 中添加 path 时需要拷贝一个新的列表，否则最终 res 中的列表都是空的。
是为什么呢，可以说具体一点吗，或者给我一个具体的方向我去看

[dwdw666]

不拷贝的话传的是引用

[Jingzhenzxz]

不拷贝的话传的是引用，然后path会不断地removeLast，所以最后path会变成空。

[moustacheyummy]

已从回溯的公众号知道了答案！！
如果res.add(new LinkedList(track))，不用新变量做拷贝的话，写成res.add(track)的话，最后得到的会是全部为空的列表。
原因：变量 track所指向的列表 在深度优先遍历的过程中只有一份 ，深度优先遍历完成以后，回到了根结点，成为空列表。
在 Java 中，参数传递是 值传递，对象类型变量在传参的过程中，复制的是变量的地址。这些地址被添加到 res 变量，但实际上指向的是同一块内存地址，因此我们会看到 6 个空的列表对象。

[labuladong]

@moustacheyummy 是的，经典的传值和传引用的问题。

[henanwg]

小菜鸡放一下自己照着写的c++版本

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 
    {
        buildGraph(numCourses,prerequisites);
        visited.resize(numCourses,0);
        onpath.resize(numCourses,0);
        for(int i=0;i<numCourses;i++)
            traverse(i);
            
        return !hasCycle;
    }
    void traverse(int i)
    // 这个地方不能用参数传递
    // 该函数会被多次递归调用，如果采用参数传递的话，每次值传递时的拷贝时间会过长
    // 最终会报超时错误
    // 出错原因：当时参照的是labuladong的java代码，
    // java中 当参数类型为基本类型时，传递值进去。当参数为对象时，传递对象的引用地址值进去。
    {
        if(onpath[i])
            hasCycle=true;
        if(visited[i]||hasCycle)
            return;

        visited[i]=true;
        onpath[i]=true;
        for(int t:graph[i])
            traverse(t);
        onpath[i]=false;
    }

    void buildGraph(int numCourses, vector<vector<int>>& prerequisites)
    {
        graph.resize(numCourses);
        for(auto& edge:prerequisites)
        {
            int from=edge[1],to=edge[0];
            graph[from].push_back(to);
        }
    }
private:
    vector<vector<int>> graph;
    vector<bool> visited{0};
    vector<bool> onpath{0};
    bool hasCycle=0;
};

[henanwg]

啊发错位置了，上面对应-->207 课程表

[Jackwong0716]

leetcode那道题，图遍历函数那个结束条件为什么是n-1结束呢？？有的图节点并不会指向n-1, 有点没想明白。 然后结束的if操作中， 为什么也要remove一次呢？？ 好抽象，二叉树遍历root == null结束比较形象，这里有点迷糊。。

[lee666-lee]

@Jackwong0716 你好，我的理解是这样的，希望可以帮到你。1.traverse()函数返回值是void，所以不存在什么结束条件哦，这个if(s==n-1)判断的真正目的是当遍历到目的结点n-1时，将整个路径加到res中。2.没错，有的图节点不会指向n-1，这个时候就是for循环执行完，再执行函数最后一行的path.removeLast()就退出以该节点（此处该节点就是指，那些没指向n-1的图节点）的traverse函数，路径里面不需要该节点，因为他们无法到达n-1。3.如果if(s==n-1)判断里不path.removeLast()，即不把n-1节点从当前路径中删除，那么返回上层节点的时候，路径的末尾仍带着n-1节点，那么接下来新构造的路径就会出错，因为这是个递归的过程。

[KaihuaS]

@Jackwong0716 我的理解是，因为题中让你找到n - 1 的路径，其实不加 path.remove和 return也可以，因为n - 1没有后继节点了，n -1 这个点，没有for循环的选择了, 对于n -1 来说不会进入递归。 而这种写法是可以处理target还有后序节点的，直接跳出，不需要再次进入递归加入不相干的后继节点。 然后回溯是为了，如果有另一条路径能到达n - 1，比如1有两条路径能到达4， 1 - > 2 - > 4, 回溯 1 - > 2 - > 3 - > 4，这样进行回溯，就可以把两条路径都找出来。

[labuladong]

@lee666-lee @KaihuaS 你们理解的没问题，这道题给定的图中不存在环，所以省去很多麻烦。如果在找到目标节点时 return，则需要正确维护 path，因为函数开头 addLast 了一次，所以需要 removeLast 再 return，否则 path 的就会多出一个节点；当然也可以不 return，这样函数结尾会进行 removeLast 正确维护 path，同时图中不包含环，不会出现无限递归，也可以正常结束。

[Yuanheng-glitch]

感觉onPath 在遍历中没起作用啊，有人可以给个解释码

[NozomiMizore]

@https://github.com/Yuanheng-glitch 记录经过的路径

[Yuanheng-glitch]

@https://github.com/Yuanheng-glitch 记录经过的路径
谢谢，我学习后续的章节也弄明白了

[lan-dian]

内存超出了，有大佬帮我看看为什么吗？

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<Integer> sup = new ArrayList<>();
        sup.add(0);
        getPath(0,graph,sup);
        return res;
    }

    List<List<Integer>> res=new ArrayList<>();

    public void getPath(int point,int[][] graph,List<Integer> sup){
        boolean hasRount=false;
        for (int i = 0; i < graph[point].length; i++) {
            if(graph[point][i]!=0){
                hasRount=true;
                List<Integer> temp=new ArrayList<>(sup);
                temp.add(i);
                getPath(i,graph,temp);
            }
        }
        if(!hasRount){
            res.add(sup);
        }
    }

}

[chendazhang]

老师写的太好了 看了将近三分之二的内容 收获甚多 感谢！

[lihuagang03]

打卡，感谢楼主！

[LebronHarden1]

谢谢,有了干迪杰斯特拉算法的信心

[wercyle]

C++版本

class Solution {
private:
    vector<vector<int>> rvalue;
    vector<int> path;
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        /* 
        解法一：
        return AllThePath(graph,0);
        解法二：
        vector<int> path;
        DFS(graph,path,0);
        return rvalue;
        */
        //解法三：
        DFS2(graph,0);
        return rvalue;
    }

    //递归解法：定义一个函数，可以返回从VertexStart→n-1的所有可能路径(递归解法)
    vector<vector<int>> AllThePath(vector<vector<int>>& graph,int VextexStart){
        vector<vector<int>> result;

        if(VextexStart==graph.size()-1){
            vector<vector<int>> res;
            vector<int> k(1,VextexStart);
            res.push_back(k);
            return res;
        }

        for(int i=0;i<graph[VextexStart].size();i++){
            vector<vector<int>> re=AllThePath(graph,graph[VextexStart][i]);
            for(int i=0;i<re.size();i++){
                re[i].insert(re[i].begin(),VextexStart);
                result.push_back(re[i]);
            }
        }

        return result;
    }

    //遍历解法---用形参path记录当前路径，空间复杂度较高
    void DFS1(vector<vector<int>>& graph,vector<int> path,int s){
        path.push_back(s);
        if(s==graph.size()-1) rvalue.push_back(path);

        for(int v:graph[s]){
            DFS1(graph,path,v);
        }
    }

    //遍历解法------不用形参记录路径，直接用全局变量path,记录当前路径，需要正确的进行维护
    void DFS2(vector<vector<int>>& graph,int s){
        path.push_back(s);
        if(s==graph.size()-1) rvalue.push_back(path);

        for(int v:graph[s]){
            DFS2(graph,v);
        }
        path.pop_back();
    }
};

[daixiongming]

这个非常好！

[mengbingrock]

发现弹栈的时机有两种，本文和力扣官方解答分别用到了这两种。
调用者弹栈

class Solution:
    def dfs(self, node, graph, path, endnote):
        path += [node]
        if path and path[-1] == endnote:
            self.ans.append(path[:])
            
            return
        
        for nodeNext in graph[node]:
            self.dfs(nodeNext, graph, path, endnote)
            path.pop()

    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        path = list()
        self.ans = list()
        self.dfs(0,graph,path, len(graph)-1)

        return self.ans

被调用者自己弹栈：

class Solution:
    def dfs(self, node, graph, path, endnote):
        path += [node]
        if path and path[-1] == endnote:
            self.ans.append(path[:])
            path.pop()
            return
        
        for nodeNext in graph[node]:
            self.dfs(nodeNext, graph, path, endnote)
        path.pop()
        
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        path = list()
        self.ans = list()
        self.dfs(0,graph,path, len(graph)-1)

        return self.ans

[xuyangm]

C++

class Solution {
public:
    int n;
    vector<vector<int>> paths;

    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        n = graph.size();
        vector<int> path;
        traverse(graph, 0, path);
        return paths;
    }

    void traverse(vector<vector<int>>& graph, int s, vector<int>& path) {
        path.push_back(s);
        if(s == n-1) {
            paths.push_back(path);
            path.erase(path.end()-1);
            return;
        }
        for(auto node: graph[s]) {
            traverse(graph, node, path);
        }
        path.erase(path.end()-1);
    }

};

[cwdelphi]

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    
    int n = 0;
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        n = graph.size();
        //用DFS还是回溯都是可以的！
        //backtrack(graph, 0);
        traverse(graph, 0);
        return res;
    }

    void backtrack(vector<vector<int>>& graph, int s){
        if(s == n - 1){
            path.push_back(s);
            res.push_back(path);
            path.pop_back();
            return;
        }
        
        for (int v : graph[s]) {
            path.push_back(s);
            backtrack(graph, v);
            path.pop_back();
        }
    }

    void traverse(vector<vector<int>>& graph, int s){
        path.push_back(s);
        if(s == n - 1){
            res.push_back(path);
            path.pop_back();
            return;
        }
        
        for (int v : graph[s]) {
            traverse(graph, v);
        }
        path.pop_back();
    }
};

[hscspring]

太妙了

[xiaopeiyi0704]

东哥，
“”如果图包含环，遍历框架就要一个 visited 数组进行辅助“。但我觉得（不一定对）
判断有无环不是应该靠onPath吗?
visited看起来像是避免重复判断的啊

另外onPath会回撤，从而可以判断有无环。visited并没有回撤啊。请指教。谢谢

[labuladong]

visited 和 onPath 都要有，它俩的作用不同，你可以看下 拓扑排序详解及运用 这篇。

[Yyhan-1998]

@xiaopeiyi0704 我和你想的一样， 如果说图是有环的情况下，就只需要定义一个onepath数组，因为onepath里边只是代表这一条路径，不要visited数组，因为要visited的话，最后得到的路径是不全的，如果我说的有错 请纠正我

[labuladong]

visited 和 onPath 都要有，它俩的作用不同，你可以看下 拓扑排序详解及运用 这篇。

[xiaopeiyi0704]

@Yyhan-1998 我上面的留言只想想针对东哥那句话产生了歧义。我现在理解东哥想表达的有没有环并不是指当前路径上的环，而是说整幅图的。整幅图上的环会导致做重复的事，一条路径上有没有环是为了得到答案。(假设问题是问有没有环) 。换句话说如果一道题求的不是问有没有环，而就是让你遍历图从而求得一些其他的值，他们如果整幅图有环，重复遍历不就stackoverflow了。

另外到底需不需要visited？- 因题而异。你提到“因为要visited的话，最后得到的路径是不全的”
我认为这句话是不对的，如果你觉得路径不是全的，那么你要考虑的是否要撤销选择-visited[node] = false，而不是弃用visited，不然同一路径出现环就傻了。

那有没有情况可以不用visited也能提交成功的题? 一定有。我记得我之前做过一道题有没有visited对最后效率影响不大。但我发现其实还是有重复的，只是非常少量的重复不太影响结果。但是面试的时候还是加上好。

我也刚刚开始学习刷题，所说的都是个人理解，甚至都不一定对。如有错误，请指出，并多包涵。请多指教。

[labuladong]

visited 是防止你递归遍历进入死循环永不结束的，多刷刷题就明白了，加油

[Yyhan-1998]

@labuladong 感谢回答，我有个问题， 比如力扣中的示例2，我的想法是，无论有环没环，加上visited数组都会导致结果不全。
比如我们经过0->1->2->3->4这条路径到达终点，路上的0，1，2，3全部被标记为visited，然后回溯到3，没有其他路径，回溯到2，没有其他路径，回溯到1，发现可以走1->3这个路径，但是3已经表示为visited过了，那么这条路径就行不通了，同理，0->3->4这个路径也行不通。 如果我想法错误的话，请指出。 感谢！

[lpdswing]

克隆图

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        
        visited = {}

        def traverse(node):
            if not node:
                return
            if node in visited:
                return
            cloned = Node(node.val)
            visited[node] = cloned

            for neighbor in node.neighbors:
                traverse(neighbor)
                cloned.neighbors.append(visited[neighbor])
            
            return cloned

        return traverse(node)

[NoOneHero]

打卡

func allPathsSourceTarget(graph [][]int) [][]int {
	var res [][]int

	var traverse func(onPath []int, i int)
	traverse = func(onPath []int, i int) {
		n := len(graph)
		onPath = append(onPath, i)
		if i == n-1 {
			res = append(res, append([]int{}, onPath...))
			//这里因为是有向无环图，不会出现无限递归，无需return
			//onPath = onPath[:len(onPath)-1]
			//return
		}
		for _, j := range graph[i] {
			traverse(onPath, j)
		}
	}
	traverse([]int{}, 0)
	return res
}

[Tiger32828]

为什么在这道题中 path.addLast(s) 这个做选择的动作被放在判断结束的条件if (s == n - 1)之前， 而非放在递归每个相邻节点的前一行。我这么理解是因为在课程表里，OnPath这个做选择的动作是放在判断结束条件之后的。有点想不清楚。
还有就是visited数组在这道题内并不需要用，因为题目告诉了图是没有环的。既然visited数组只是为了判断是不是有内部环而进行的剪枝操作，那么对于没有环时使用visited数组应该只是无用而非有害罢了，那为什么这道题使用visited数组反而会造成错误答案

[lemonzeng]

捉个虫，“他们的区别可以这样反应到代码上”中的“反应”可改为“反映”