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

Breadth First Search

‣
Provide an implementation for BFS

Given an adjacency list [self.graph = defaultdict(list)],

m×nm \times nm×n Adjacency Matrix [self.graph = matrix],

Implement BFS (iteratively), and give its run time

Search:

  1. Initialize a visited array/map/matrix/table and queue with source node
  2. For all vertices in graph, do BFS on unvisited vertices while maintaining record of visited graph

BFS:

  1. Pop vvv from queue and mark vertex vvv as visited, if not already visited
  2. Do operations (such as print or compare)
  3. For ∀\forall∀ edges of vertex, on unvisited neighbors

https://www.geeksforgeeks.org/applications-of-breadth-first-traversal/

‣
What are the applications of BFS?

Shortest path

Finding the minimum spanning tree

Level order tree traversal

‣
Give the space complexity of BFS

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

‣
Give the runtime of BFS

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

‣
Provide the algorithm (pseudocode) for BFS
image
‣
What does BFS do?

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

class Graph:

    # Constructor
		def __init__(self):

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

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

    # function to print a BFS of graph
		def BFS(self, v):
        V = self.graph
        # Mark all the vertices as not visited
        visited = [False] * (len(V))

        # Create a queue for BFS
        queue = []

        # Mark the source node as
				# visited and enqueue it
        queue.append(v)
        visited[v] = True

        while queue:

            # Dequeue a vertex from
						# queue and print it
            s = queue.pop(0)
            print (s, end = " ") # additional logic here!
						# Get all adjacent vertices of the
						# dequeued vertex s. If a adjacent
						# has not been visited, then mark it
						# visited and enqueue it
            neighbors = self.graph[n]
            for n in neighbors:
                if not visited[n]:
                    queue.append(n)
                    visited[v] = True


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

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

		def BFS(self, v):
        V = self.graph

        visited = [False] * (len(V))

        queue = []
        queue.append(v)
        visited[v] = True

        while queue:
            s = queue.pop(0)
            print (s, end = " ") 
						# additional logic here!
            neighbors = self.graph[n]

            for n in neighbors:
                if not visited[n]:
                    queue.append(n)
                    visited[v] = True