BFS and DFS in Graph

  • Use queue (use deque or list in Python)

  • Since graph may contain cycles (a node may be visited twice), we need a visited (list or set) to record visited nodes.

  • Time Complexity: O(V+E), where V is the number of nodes and E is the number of edges.

  • Auxiliary Space: O(V)

BFS template code (using deque and set):

# Python3 Program to print BFS traversal
# from a given source vertex. BFS(int s)
# traverses vertices reachable from s.
from collections import defaultdict
from collections import deque


# This class represents a directed graph
# using adjacency list representation
class Graph:

    # Constructor
    def __init__(self):
        # Default dictionary to store graph
        self.graph = defaultdict(list)

    # Function to add an edge to graph
    def addEdge(self, u, v):
        self.graph[u].append(v)

    # Function to print a BFS of graph
    def BFS(self, s):

        # Mark all the vertices as not visited
        visited = set()

        # Create a queue for BFS
        queue = deque()

        # Mark the source node as
        # visited and enqueue it
        queue.append(s)
        visited.add(s)

        while queue:
            # Dequeue a vertex from
            # queue and print it
            s = queue.popleft()
            print(s)
            # Get all adjacent vertices of the
            # dequeued vertex s.
            # If an adjacent has not been visited,
            # then mark it visited and enqueue it
            for i in self.graph[s]:
                if i not in visited:
                    queue.append(i)
                    visited.add(i)


# Driver code
if __name__ == '__main__':
    # Create a graph given in
    # the above diagram
    g = Graph()
    g.addEdge(0, 1)
    g.addEdge(0, 2)
    g.addEdge(1, 2)
    g.addEdge(2, 0)
    g.addEdge(2, 3)
    g.addEdge(3, 3)
    print("Following is Breadth First Traversal"
          " (starting from vertex 2)")
    g.BFS(1)
  • 为什么以下图中在 visit(v) 之前要 check if not marked[v], 而上面的算法实现没有。
    • 因为上面的算法在把节点加入queue中时，就算visited了，而下图中时把节点从queue 中取出来后才算visited了，按照逻辑上来讲下图的算法更清晰。

image-20230823014325081

BFS Application

  • Flood Fill Problem

image-20230823015107217

image-20230823015531722

DFS template code (using deque and set):

# Python3 program to print DFS traversal
# from a given graph
from collections import defaultdict


# This class represents a directed graph using
# adjacency list representation
class Graph:

	# Constructor
	def __init__(self):

		# Default dictionary to store graph
		self.graph = defaultdict(list)

	
	# Function to add an edge to graph
	def addEdge(self, u, v):
		self.graph[u].append(v)

	
	# A function used by DFS
	def DFSUtil(self, v, visited):

		# Mark the current node as visited
		# and print it
		visited.add(v)
		print(v)

		# Recur for all the vertices
		# adjacent to this vertex
		for neighbour in self.graph[v]:
			if neighbour not in visited:
				self.DFSUtil(neighbour, visited)

	
	# The function to do DFS traversal. It uses
	# recursive DFSUtil()
	def DFS(self, v):

		# Create a set to store visited vertices
		visited = set()

		# Call the recursive helper function
		# to print DFS traversal
		self.DFSUtil(v, visited)


# Driver's code
if __name__ == "__main__":
	g = Graph()
	g.addEdge(0, 1)
	g.addEdge(0, 2)
	g.addEdge(1, 2)
	g.addEdge(2, 0)
	g.addEdge(2, 3)
	g.addEdge(3, 3)

	print("Following is Depth First Traversal (starting from vertex 2)")
	
	# Function call
	g.DFS(2)

The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

Recursion version process:

image-20230823005258012

Figure source: Depth First Search (DFS) Explained: Algorithm, Examples, and Code

Iterative version process:

image-20230823005847800

image-20230823011133119

  • Recursive implementation is the more standard implementation of DFS since is cleaner and easier to read.
  • Iterative implementation is more generalizable to other grash traversal algorithms that require an iterative approach.

image-20230823011316607

  • Postorder only output the vertex which has no more neighbors to explore.

Code implementation:

image-20230823011706204

  • Topological Sort

image-20230823012810706

image-20230823013311837

DFS Application

  • Cycle detection
  • Finding Connected Components
  • Topological Sort. (directed acyclic graph)
  • Maze Generation.

References