fucking-algorithm 图论基础 :: labuladong的算法小抄

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

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

Feb 05 '22 07:02 labuladong

一个小错误,第三个代码框的第一行是邻接表

Feb 23 '22 19:02 Pgao4

收到，已修改

Feb 25 '22 06:02 labuladong

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

Mar 06 '22 08:03 moustacheyummy

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

Mar 07 '22 00:03 moustacheyummy

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

Mar 07 '22 15:03 labuladong

小菜鸡放一下自己照着写的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;
};

Mar 10 '22 06:03 henanwg

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

Mar 10 '22 06:03 henanwg

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

Mar 18 '22 10:03 Jackwong0716

@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节点，那么接下来新构造的路径就会出错，因为这是个递归的过程。

Mar 24 '22 01:03 lee666-lee

@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，这样进行回溯，就可以把两条路径都找出来。

Mar 26 '22 17:03 KaihuaS

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

Mar 27 '22 04:03 labuladong

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

Mar 29 '22 13:03 Yuanheng-glitch

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

Mar 31 '22 08:03 NozomiMizore

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

Mar 31 '22 08:03 Yuanheng-glitch

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

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);
        }
    }

}

Apr 21 '22 03:04 lan-dian

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

Apr 29 '22 13:04 chendazhang

@langar294 你的for下if下的最后两行，temp.add()和getPath()参数应该是graph[point][i]，而不是i

May 07 '22 21:05 saw008

Python的BFS解法

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        def bfs(starting_node):
            queue = [(starting_node, [starting_node])]
            while queue:
                idx, route = queue.pop(0)
                if idx == len(graph)-1:
                    ans.append(route)
                for child in graph[idx]:
                    queue.append((child, route+[child]))
                print(queue)
                    
        ans = []
        bfs(0)
        return ans

May 07 '22 21:05 saw008

打卡，感谢楼主！

Jun 04 '22 09:06 lihuagang03

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

Jun 06 '22 01:06 LebronHarden1

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();
    }
};

Jun 16 '22 02:06 wercyle

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

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

Aug 05 '22 16:08 mengbingrock

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);
    }

};

Aug 15 '22 02:08 xuyangm

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();
    }
};

Aug 18 '22 07:08 cwdelphi

太妙了

Aug 24 '22 16:08 hscspring

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

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

Aug 24 '22 20:08 xiaopeiyi0704

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

Sep 05 '22 19:09 Yyhan-1998

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

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

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

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

Sep 05 '22 23:09 xiaopeiyi0704