All Paths From Source to Target(2 Methods) | LeetCode | Java

04614

Method 1 : Using Visited Array – DFS 

<span>class</span> <span>Solution</span> <span>{</span>
    <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>resList</span><span>;</span>
    <span>public</span> <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>allPathsSourceTarget</span><span>(</span><span>int</span><span>[][]</span> <span>graph</span><span>)</span> <span>{</span>
        <span>int</span> <span>len</span> <span>=</span> <span>graph</span><span>.</span><span>length</span><span>;</span>
        <span>List</span><span><</span><span>Integer</span><span>></span> <span>path</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
        <span>resList</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
        <span>boolean</span> <span>visited</span><span>[]</span> <span>=</span> <span>new</span> <span>boolean</span><span>[</span><span>len</span><span>];</span>
        <span>dfs</span><span>(</span><span>graph</span><span>,</span> <span>0</span><span>,</span> <span>len</span><span>-</span><span>1</span><span>,</span> <span>visited</span><span>,</span> <span>path</span><span>);</span>
        <span>return</span> <span>resList</span><span>;</span>
    <span>}</span>
      <span>void</span> <span>dfs</span><span>(</span><span>int</span> <span>graph</span><span>[][],</span> <span>int</span> <span>src</span><span>,</span> <span>int</span> <span>dest</span><span>,</span> <span>boolean</span> <span>visited</span><span>[],</span> <span>List</span><span><</span><span>Integer</span><span>></span> <span>path</span><span>)</span> <span>{</span>
        <span>visited</span><span>[</span><span>src</span><span>]</span> <span>=</span> <span>true</span><span>;</span>
        <span>path</span><span>.</span><span>add</span><span>(</span><span>src</span><span>);</span>
        <span>if</span> <span>(</span><span>src</span> <span>==</span> <span>dest</span><span>)</span> <span>{</span>
            <span>resList</span><span>.</span><span>add</span><span>(</span><span>new</span> <span>ArrayList</span><span><>(</span><span>path</span><span>));</span>
        <span>}</span>
        <span>for</span> <span>(</span><span>int</span> <span>ele</span> <span>:</span> <span>graph</span><span>[</span><span>src</span><span>])</span> <span>{</span>
            <span>if</span> <span>(!</span><span>visited</span><span>[</span><span>ele</span><span>])</span> 
                <span>dfs</span><span>(</span><span>graph</span><span>,</span> <span>ele</span><span>,</span> <span>dest</span><span>,</span> <span>visited</span><span>,</span> <span>path</span><span>);</span>
        <span>}</span>
        <span>path</span><span>.</span><span>remove</span><span>(</span><span>path</span><span>.</span><span>size</span><span>()</span> <span>-</span> <span>1</span><span>);</span>
        <span>visited</span><span>[</span><span>src</span><span>]</span> <span>=</span> <span>false</span><span>;</span>
    <span>}</span>
<span>}</span>
<span>class</span> <span>Solution</span> <span>{</span>
    <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>resList</span><span>;</span>
    <span>public</span> <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>allPathsSourceTarget</span><span>(</span><span>int</span><span>[][]</span> <span>graph</span><span>)</span> <span>{</span>
        <span>int</span> <span>len</span> <span>=</span> <span>graph</span><span>.</span><span>length</span><span>;</span>
        <span>List</span><span><</span><span>Integer</span><span>></span> <span>path</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
        <span>resList</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
        <span>boolean</span> <span>visited</span><span>[]</span> <span>=</span> <span>new</span> <span>boolean</span><span>[</span><span>len</span><span>];</span>
        <span>dfs</span><span>(</span><span>graph</span><span>,</span> <span>0</span><span>,</span> <span>len</span><span>-</span><span>1</span><span>,</span> <span>visited</span><span>,</span> <span>path</span><span>);</span>
        <span>return</span> <span>resList</span><span>;</span>
    <span>}</span>
      <span>void</span> <span>dfs</span><span>(</span><span>int</span> <span>graph</span><span>[][],</span> <span>int</span> <span>src</span><span>,</span> <span>int</span> <span>dest</span><span>,</span> <span>boolean</span> <span>visited</span><span>[],</span> <span>List</span><span><</span><span>Integer</span><span>></span> <span>path</span><span>)</span> <span>{</span>
        <span>visited</span><span>[</span><span>src</span><span>]</span> <span>=</span> <span>true</span><span>;</span>
        <span>path</span><span>.</span><span>add</span><span>(</span><span>src</span><span>);</span>

        <span>if</span> <span>(</span><span>src</span> <span>==</span> <span>dest</span><span>)</span> <span>{</span>
            <span>resList</span><span>.</span><span>add</span><span>(</span><span>new</span> <span>ArrayList</span><span><>(</span><span>path</span><span>));</span>
        <span>}</span>

        <span>for</span> <span>(</span><span>int</span> <span>ele</span> <span>:</span> <span>graph</span><span>[</span><span>src</span><span>])</span> <span>{</span>
            <span>if</span> <span>(!</span><span>visited</span><span>[</span><span>ele</span><span>])</span> 
                <span>dfs</span><span>(</span><span>graph</span><span>,</span> <span>ele</span><span>,</span> <span>dest</span><span>,</span> <span>visited</span><span>,</span> <span>path</span><span>);</span>
        <span>}</span>

        <span>path</span><span>.</span><span>remove</span><span>(</span><span>path</span><span>.</span><span>size</span><span>()</span> <span>-</span> <span>1</span><span>);</span>
        <span>visited</span><span>[</span><span>src</span><span>]</span> <span>=</span> <span>false</span><span>;</span>
    <span>}</span>
<span>}</span>
class Solution {
    List<List<Integer>> resList;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int len = graph.length;
        List<Integer> path = new ArrayList<>();
        resList = new ArrayList<>();
        boolean visited[] = new boolean[len];
        dfs(graph, 0, len-1, visited, path);
        return resList;
    }
      void dfs(int graph[][], int src, int dest, boolean visited[], List<Integer> path) {
        visited[src] = true;
        path.add(src);

        if (src == dest) {
            resList.add(new ArrayList<>(path));
        }

        for (int ele : graph[src]) {
            if (!visited[ele]) 
                dfs(graph, ele, dest, visited, path);
        }

        path.remove(path.size() - 1);
        visited[src] = false;
    }
}

Enter fullscreen mode Exit fullscreen mode

Method 2 : Using Backtracking 

<span>class</span> <span>Solution</span> <span>{</span>
    <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>resList</span><span>;</span>
    <span>public</span> <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>allPathsSourceTarget</span><span>(</span><span>int</span><span>[][]</span> <span>graph</span><span>)</span> <span>{</span>
        <span>resList</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
        <span>int</span> <span>n</span> <span>=</span> <span>graph</span><span>.</span><span>length</span><span>;</span>
        <span>int</span> <span>src</span> <span>=</span> <span>0</span><span>;</span>
        <span>int</span> <span>dest</span> <span>=</span> <span>n</span><span>-</span><span>1</span><span>;</span>
        <span>List</span><span><</span><span>Integer</span><span>></span> <span>path</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
        <span>path</span><span>.</span><span>add</span><span>(</span><span>0</span><span>);</span>
        <span>getPaths</span><span>(</span><span>graph</span><span>,</span> <span>src</span><span>,</span> <span>dest</span><span>,</span> <span>path</span><span>);</span>
        <span>return</span> <span>resList</span><span>;</span>
    <span>}</span>
    <span>void</span> <span>getPaths</span><span>(</span><span>int</span> <span>graph</span><span>[][],</span> <span>int</span> <span>src</span><span>,</span> <span>int</span> <span>dest</span><span>,</span> <span>List</span><span><</span><span>Integer</span><span>></span> <span>path</span><span>){</span>
        <span>if</span><span>(</span><span>src</span><span>==</span><span>dest</span><span>){</span>
            <span>resList</span><span>.</span><span>add</span><span>(</span><span>new</span> <span>ArrayList</span><span><>(</span><span>path</span><span>));</span>
            <span>return</span><span>;</span>
        <span>}</span>
        <span>else</span><span>{</span>
              <span>for</span><span>(</span><span>int</span> <span>ele</span> <span>:</span> <span>graph</span><span>[</span><span>src</span><span>]){</span>
                  <span>path</span><span>.</span><span>add</span><span>(</span><span>ele</span><span>);</span>
                  <span>getPaths</span><span>(</span><span>graph</span><span>,</span> <span>ele</span><span>,</span> <span>dest</span><span>,</span> <span>path</span><span>);</span>
                  <span>path</span><span>.</span><span>remove</span><span>(</span><span>path</span><span>.</span><span>size</span><span>()-</span><span>1</span><span>);</span>
              <span>}</span>
        <span>}</span>
    <span>}</span>
<span>}</span>
<span>class</span> <span>Solution</span> <span>{</span>
    <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>resList</span><span>;</span>
    <span>public</span> <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>allPathsSourceTarget</span><span>(</span><span>int</span><span>[][]</span> <span>graph</span><span>)</span> <span>{</span>

        <span>resList</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
        <span>int</span> <span>n</span> <span>=</span> <span>graph</span><span>.</span><span>length</span><span>;</span>
        <span>int</span> <span>src</span> <span>=</span> <span>0</span><span>;</span>
        <span>int</span> <span>dest</span> <span>=</span> <span>n</span><span>-</span><span>1</span><span>;</span>
        <span>List</span><span><</span><span>Integer</span><span>></span> <span>path</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
        <span>path</span><span>.</span><span>add</span><span>(</span><span>0</span><span>);</span>

        <span>getPaths</span><span>(</span><span>graph</span><span>,</span> <span>src</span><span>,</span> <span>dest</span><span>,</span> <span>path</span><span>);</span>
        <span>return</span> <span>resList</span><span>;</span>
    <span>}</span>

    <span>void</span> <span>getPaths</span><span>(</span><span>int</span> <span>graph</span><span>[][],</span> <span>int</span> <span>src</span><span>,</span> <span>int</span> <span>dest</span><span>,</span> <span>List</span><span><</span><span>Integer</span><span>></span> <span>path</span><span>){</span>

        <span>if</span><span>(</span><span>src</span><span>==</span><span>dest</span><span>){</span>
            <span>resList</span><span>.</span><span>add</span><span>(</span><span>new</span> <span>ArrayList</span><span><>(</span><span>path</span><span>));</span>
            <span>return</span><span>;</span>
        <span>}</span>

        <span>else</span><span>{</span>
              <span>for</span><span>(</span><span>int</span> <span>ele</span> <span>:</span> <span>graph</span><span>[</span><span>src</span><span>]){</span>
                  <span>path</span><span>.</span><span>add</span><span>(</span><span>ele</span><span>);</span>
                  <span>getPaths</span><span>(</span><span>graph</span><span>,</span> <span>ele</span><span>,</span> <span>dest</span><span>,</span> <span>path</span><span>);</span>
                  <span>path</span><span>.</span><span>remove</span><span>(</span><span>path</span><span>.</span><span>size</span><span>()-</span><span>1</span><span>);</span>
              <span>}</span>
        <span>}</span>

    <span>}</span>
<span>}</span>
class Solution {
    List<List<Integer>> resList;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {

        resList = new ArrayList<>();
        int n = graph.length;
        int src = 0;
        int dest = n-1;
        List<Integer> path = new ArrayList<>();
        path.add(0);

        getPaths(graph, src, dest, path);
        return resList;
    }

    void getPaths(int graph[][], int src, int dest, List<Integer> path){

        if(src==dest){
            resList.add(new ArrayList<>(path));
            return;
        }

        else{
              for(int ele : graph[src]){
                  path.add(ele);
                  getPaths(graph, ele, dest, path);
                  path.remove(path.size()-1);
              }
        }

    }
}

Enter fullscreen mode Exit fullscreen mode

Thanks for reading 🙂
Feel free to comment and like the post if you found it helpful
Follow for more 🤝 && Happy Coding

If you enjoy my content, support me by following me on my other socials:
https://linktr.ee/tanujav7

原文链接：All Paths From Source to Target(2 Methods) | LeetCode | Java

展开阅读全文
© 版权声明
文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END
Java（EN）
# java# beginners# algorithms# leetcode
喜欢就支持一下吧
点赞14 分享
Do not find excuses for failure, to chase success reasons.
不要找失败的借口，去追成功的理由
评论 抢沙发

请登录后发表评论

    暂无评论内容

kity的头像-拾光赋
今日剩余 55.0%
本周剩余 50.7%
本月剩余 45.2%
本年剩余 70.8%
最近评论
杀人蜂的头像-拾光赋

杀人蜂3天前0

我很好奇这个网站能提供什么
Vito的头像-拾光赋

Vito6个月前2

你就是我心中的那首忐忑，总是让我惊心动魄
Jason.Meng的头像-拾光赋钻石会员

Jason.Meng徽章-人气大使-拾光赋6个月前2

总是会在人生的不同阶段反复爱上大佬的文章~
每日一言
Life is the flower for which love is the honey.
生命如花，爱情是蜜