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

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:

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:

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.

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

Leave a Reply