Promoted
Promoted

Path Finding problems using Depth-First-Search DFS

Topic: Algorithms

Pathfinding problems have many applications, from computer games, network routing to AI robots. If we want to explore unknown graphs and want to gather more information, DFS is a good choice. DFS is the most simple path exploration of all algorithms. It is appropriate to use during space restriction in complex state representation and acyclic graphs.

All Paths From Source to Target

0heading

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]).

2paragraph
Input: graph = [[1,2],[3],[3],[]].
3image

Intuition

4subheading
  • In the above example, we need to find all paths from 0 node to n-1 node.
  • We will use recursive DFS.
  • Initialize the visited list to store visited nodes so we don't visit the same node twice.
  • Initialize the result list to store paths.
  • We follow 3 steps: mark node visited, check if the node is the destination, and explore its unvisited neighbors.
  • Our DFS algorithm will first start at node 0 and the destination is 3.
  • Below is the python code
5list
def allPathsSourceTarget(graph): def dfs(visited, vertex, destination): visited.append(vertex) #Mark node visted if destination == vertex: #check if we reached destination res.append(visited[:]) #copy nodes from visited to result for u in graph[vertex]: if u not in visited: #explore its unvisited neighbours dfs(visited, u, destination) visited.remove(vertex) visited = [] # to store visited node res = [] # to store the result dfs(visited, 0, len(graph)-1) return res #res = [[0,1,3],[0,2,3]]
6code
Promoted
Promoted

Path with Maximum Gold

7heading

In a gold mine grid of size m x n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.Return the maximum amount of gold you can collect under the conditions:

9paragraph
Input: grid = [[0,6,0],[5,8,7],[0,9,0]] Output: 24 Explanation: [[0,6,0], [5,8,7], [0,9,0]] Path to get the maximum gold, 9 -> 8 -> 7.
10code
Represent above problem in graph. Red is maximum path..
11image

Intuition

12subheading
  • Here each node is connected to itself and other nodes. We can visualize the grid in the form of a graph as shown in the above figure.
  • This problem can be solved in similar 3 steps as the above problem with little modifications.
  • We not only check visited nodes. But we also need to check we stay in the grid.
  • Since we have asked for maximum gold we will start the path with sum 0 and keep adding new path node values to the sum.
  • Every time we move top, left, right, the bottom cell we check if the node is unvisited and call DFS.
  • We want to choose only nodes in the path which give us the maximum sum. So we take a maximum of neighbors and return that value.
13list
Promoted
Promoted
def getMaximumGold(grid): def dfs(i, j, sum, visited): #return if check i and j are underflow or overflow or (i,j) already visited if i < 0 or i >= m or j < 0 or j >= n or not grid[i][j] or (i, j) in visited: return sum visited.add((i, j)) sum += grid[i][j] #add to current sum mx = 0 for x, y in ((i, j + 1), (i , j - 1), (i + 1, j), (i - 1, j)): #check top, left, right, bottom neighbours mx = max(dfs(x, y, sum, visited), mx) #only choose maximum value visited.discard((i, j)) #remove from visited return mx #return total path value m, n = len(grid), len(grid[0]) maximum_gold = float('-inf') for i in range(m): for j in range(n): #check with every (i,j) node as start node maximum_gold = max(maximum_gold, dfs(i, j, 0, set())) return maximum_gold
14code
Promoted
Promoted

Flood Fill

7heading

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and newColor. You should perform a flood fill on the image starting from the pixel image[sr][sc]. To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with newColor. Return the modified image after performing the flood fill.

9paragraph
Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2 Output: [[2,2,2],[2,2,0],[2,0,1]] Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color. Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.
10code
Flood Fill.
11image

Intuition

12subheading
  • Even this problem is similar to the above problems.
  • Here we don't require a visited list as we check that value of the cell.
  • If the value of the cell is already a new color that means we already visited, we return.
13list
Promoted
Promoted
def floodFill(image, sr, sc, newColor): def dfs(i,j): #if going out grid return if i < 0 or i >= row or j < 0 or j >= col: return #color is not same as orginal color or already colored with new color if image[i][j] != color or image[i][j] == newColor: return image[i][j] = newColor for x,y in ((i, j + 1), (i , j - 1), (i + 1, j), (i - 1, j)): dfs(x,y) row = len(image) col = len(image[0]) color = image[sr][sc] dfs(sr,sc) return image
14code