🌵
Christian's Wiki
/
📖
Data Structures & Algorithms
/
Algorithm
/
Depth First Search

Depth First Search

‣
Provide a recursive implementation for DFS on a class Graph
‣
Provide an iterative implementation for DFS on a class Graph
  • Adjacency List,
  • https://leetcode.com/problems/pacific-atlantic-water-flow/discuss/90739/Python-DFS-bests-85.-Tips-for-all-DFS-in-matrix-question
  • Adjacency Matrix, Recursive
  • https://leetcode.com/problems/pacific-atlantic-water-flow/discuss/90739/Python-DFS-bests-85.-Tips-for-all-DFS-in-matrix-question
  • https://www.geeksforgeeks.org/applications-of-depth-first-search/
‣
Provide a recursive implementation for DFS on an n×m Adj. matrixn \times m\ Adj.\ matrixn×m Adj. matrix
‣
Provide a iterative implementation for DFS on an n×m Adj. matrixn \times m\ Adj.\ matrixn×m Adj. matrix
‣
What are the applications of DFS?

Finding connected components

Finding strongly connected components

Topological sorting

Mazes

Cycle existence

Path existence

‣
Give the space complexity of DFS

O(∣V∣)O(|V|)O(∣V∣)

‣
Give the runtime of DFS

O(∣V∣+∣E∣)O(|V|+|E|)O(∣V∣+∣E∣)

‣
Provide the algorithm (pseudocode) for DFS

DFS(G):          ∀v∈G:                   if v∉visited:                              DFSUtil(G, v, visited)DFS(G):\\ \ \ \ \ \ \ \ \ \ \ \forall v \in G:\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ if\ v\notin visited:\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ DFSUtil(G,\ v,\ visited)DFS(G):          ∀v∈G:                   if v∈/visited:                              DFSUtil(G, v, visited)

DFSUtil(G,s,visited):          stack=[s]          while stack:                    v=stack.pop()                    if n∉visited:                              print(v) #additional operations here                              visited={v} ∪ visited                    for ∀n∈neighbors:                               if n∉visited:                                     stack.append(v)DFSUtil(G, s, visited):\\ \ \ \ \ \ \ \ \ \ \ stack = [s]\\ \ \ \ \ \ \ \ \ \ \ while\ stack:\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ v=stack.pop()\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ if\ n \notin visited:\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ print(v)\ \#additional\ operations\ here\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ visited=\{v\}\ \cup\ visited\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ for\ \forall n \in neighbors:\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ if\ n \notin visited:\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ stack.append(v)DFSUtil(G,s,visited):          stack=[s]          while stack:                    v=stack.pop()                    if n∈/visited:                              print(v) #additional operations here                              visited={v} ∪ visited                    for ∀n∈neighbors:                               if n∈/visited:                                     stack.append(v)

such that: visited=[ ] or {}such\ that: \ visited = [\ ] \ or\ \{\}such that: visited=[ ] or {}

‣
What does DFS do?

It visits all reachable nodes from v in depth first order.

class Graph:
    __init__(self):
        self.graph = defaultdict(list)

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def DFS(self):
        V = self.graph  #total vertices
# Mark all the vertices as not visited
        visited =[False]*len(V)

        # Call the recursive helper function to print
# DFS traversal starting from all vertices one
# by one for i in V:
            if not visited[i]:
                self.DFSUtil(i, visited)

    ##### Recursive #####
		def DFSUtil(self, v, visited):
        # Mark the current node as visited and print it
        visited[v]= True
        print(v) # additional logic here!
				# Recur for all the neighbors
        neighbors = self.graph[v]
        for n in neighbors:
            if not visited[n]:
                self.DFSUtil(n, visited)


class Graph:
    __init__(self):
        self.graph = defaultdict(list)

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def DFS(self):
        V = self.graph  #total vertices
				# Mark all the vertices as not visited
        visited =[False]*len(V)

        # Call the recursive helper function to print
				# DFS traversal starting from all vertices one
				# by one for i in V:
            if not visited[i]:
                self.DFSUtil(i, visited)


		##### Iterative #####
		def DFSUtil(self, v, visited):
        # Create a stack for DFS
        stack = []
        # Push the current source node.
        stack.append(v)

        while stack:

            # Pop a vertex from stack and print it
            v = stack.pop()

            # Stack may contain same vertex twice.
						# So we need to print popped item only
						# if it is not visited.
						if (not visited[v]):
                print(v) # additional logic here!
                visited[v] = True

            # Get neighbors of v. If neighbor has not
						# been visited, then push it to the stack.
            neighbors = self.graph[v]
            for n in neighbors:
                if not visited[n]:
                    stack.append(n)



# graph is m x n matrix
# m = len(graph), n = len(graph[0])
# visited = [[False for _ in range(n)] for _ in range(m)]
# self.dir = [[0,1][1,0],[0,-1],[-1,0]]

def dfs(self, graph, m, n, i, j, visited):
    if(visited[i][j]):
        return

    visited[i][j] = True

    for d in self.dir:
        x, y = d[0] + i, d[1] + j
        if (0 <= x < m and 
						0 <= y < n and 
						graph[i][j] <= graph[x][y]):

            self.dfs(graph, m, n, x, y, visited)

# graph is m x n matrix
# m = len(graph), n = len(graph[0])
# visited = [[False for _ in range(n)] for _ in range(m)]
# self.dir = [[0,1][1,0],[0,-1],[-1,0]]
def dfs(self, graph, m, n, i, j, visited):
        if(visited[i][j]):
            return
        stack = [[i, j]]

        while stack:
            i, j = stack.pop()
            visited[i][j] = True

            for d in self.dir:
                x, y = d[0] + i, d[1] + j
                if (0 <= x < m and 
										0 <= y < n and 
										graph[i][j] <= graph[x][y] and not 
										visited[x][y]):
                    stack.append([x, y])