C# || How To Find All Paths From Source To Target In Graph Using C#

November 28, 2021 admin No comments

The following is a module with functions which demonstrates how to find all paths from source to target in a graph using C#.

1. All Paths Source Target – Problem Statement

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n – 1, find all possible paths from node 0 to node n – 1 and return them in any order.

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

Example 1:

Input: graph = [[1,2],[3],[3],[]] Output: [[0,1,3],[0,2,3]] Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Example 2:

Input: graph = [[4,3,1],[3,2,4],[3],[4],[]] Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

Example 3:

Input: graph = [[1],[]] Output: [[0,1]]

Example 4:

Input: graph = [[1,2,3],[2],[3],[]] Output: [[0,1,2,3],[0,2,3],[0,3]]

Example 5:

Input: graph = [[1,3],[2],[3],[]] Output: [[0,1,2,3],[0,3]]

2. All Paths Source Target – Solution

The following is a solution which demonstrates how to find all paths from source to target in a graph.

This solution uses Breadth First Search and backtracking when looking for paths.





		
		
			2. All Paths Source Target - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 28, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find all paths in a graph
// ============================================================================
public class Solution {
    public IList<IList<int>> AllPathsSourceTarget(int[][] graph) {
        var result = new List<IList<int>>();
        var queue = new Queue<List<int>>();

        queue.Enqueue(new List<int>{0});

        while (queue.Count > 0) {
            var currentPath = queue.Dequeue();
            var currentNode = currentPath[currentPath.Count - 1];

            if (currentNode == graph.Length - 1) {
                result.Add(currentPath);
            } else {
                foreach (var child in graph[currentNode]) {
                    currentPath.Add(child);
                    queue.Enqueue(new List<int>(currentPath));
                    currentPath.RemoveAt(currentPath.Count - 1);
                }
            }
        }
        return result;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 28, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find all paths in a graph
// ============================================================================
public class Solution {
    public IList<IList<int>> AllPathsSourceTarget(int[][] graph) {
        var result = new List<IList<int>>();
        var queue = new Queue<List<int>>();
 
        queue.Enqueue(new List<int>{0});
 
        while (queue.Count > 0) {
            var currentPath = queue.Dequeue();
            var currentNode = currentPath[currentPath.Count - 1];
 
            if (currentNode == graph.Length - 1) {
                result.Add(currentPath);
            } else {
                foreach (var child in graph[currentNode]) {
                    currentPath.Add(child);
                    queue.Enqueue(new List<int>(currentPath));
                    currentPath.RemoveAt(currentPath.Count - 1);
                }
            }
        }
        return result;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

[[0,1,3],[0,2,3]] [[0,4],[0,3,4],[0,1,4],[0,1,3,4],[0,1,2,3,4]] [[0,1]] [[0,3],[0,2,3],[0,1,2,3]] [[0,3],[0,1,2,3]]

Was this article helpful?

👍 YesNo

Posted in: C#, Console Tags: backtracking, breadth first search, c-sharp, leetcode

C# || How To Find All Paths From Source To Target In Graph Using C#

Related

Leave a ReplyCancel reply

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories