## Tag Archives: backtracking

## 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:**

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.

```
```
12345678910111213141516171819202122232425262728293031
// ============================================================================// 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]]