Published in

Geek Culture

Important Points

1. BFS Refresher- Traditional BFS starts with a single source i.e, a single node at level 1 (distance 0). Let’s look at the logic for BFS for distance mapping
`Initialize queue QInitialize array d[N] = [INF]*len(Nodes) #for distances from sourceQ.enqueue(a)distance = 0d[a] = 0while Q is not empty:  n = Q.dequeue  distance = distance + 1  for each neighbor n_i of n:    if d[n_i] is infinity:      d[n_i] = distance      Q.enqueue(n_i)`
1. Multi-Source BFS- As the name suggests, we change the sources. The source node is the original node we start from (a in the pseudo code). If we have multiple starting locations for our BFS, there is nothing stopping us from appending all those locations into our starting queue. Everything else is usual.
2. If you’re confused- If this is confusing you, feel to take a breather. Consider your vanilla BFS. Once you have populated your queue with the neighbors of your source, you can basically treat the queue as a list of sources starting on the subgraph. This is because graphs and BFS are inherently recursive. The only difference between the vanilla and a multi-source BFS is that the latter has a populated queue at time/distance 0. This is one of the coolest properties of recursive structures. Even more complex variants of a simple recursive structure can be reduced to your simple structure easily. This is why recursive code is often called elegant. There’s a cool topic to bring up at parties where you’re surrounded by nerds.
3. Code for you- If you’re having trouble with this concept, it might be helpful to see how it is implemented. Here you can see the Python code for the Microsoft favorite question, Rotting Oranges, which we covered here. Try to break the code into different chunks to differentiate it into steps. This will help you build up your familiarity with this idea.
`from collections import dequeclass Solution:    def orangesRotting(self, grid: List[List[int]]) -> int:        rotten_orange = deque()        minutes = 0        fresh_orange = 0                rows, cols = len(grid), len(grid[0])                for r in range(rows):            for c in range(cols):                orange = grid[r][c]                if orange == 2:                    rotten_orange.append((r,c))                elif orange == 1:                    fresh_orange += 1                            directions = [(1,0), (-1,0), (0, 1), (0,-1)]        while rotten_orange and fresh_orange > 0:            minutes += 1                        for _ in range(len(rotten_orange)):                r, c = rotten_orange.popleft()                for dr, dc in directions:                    row = r + dr                    col = c + dc                    if row >= 0 and row < rows and col >= 0 and col < cols and grid[row][col] == 1:                        fresh_orange -= 1                        grid[row][col] = 2                        rotten_orange.append((row, col))                                return minutes if fresh_orange == 0 else -1`

Reach out to me

--

--

More from Geek Culture

A new tech publication by Start it up (https://medium.com/swlh).

Get the Medium app

Deep Insights about Artificial Intelligence (AI), Machine Learning, Software Engineering, and the Tech Industry. Follow me to come out on top