BFS(Breadth-First Search) with python

BFS&DFS are probably one of the most frequent and important types of questions in various interviews and coding tests. I’ve also encountered this type every time through several coding tests so far.

In this post, I would like to post about the BFS (Breadth-First Search) algorithm. I try to make it as simple as possible with Python, so I hope it helps a lot of people!🙏

BFS (Breadth-First Search) algorithm

from collections import deque


def bfs(graph, start, visited):
    q = deque([start])
    visited[start] = True
    # 1. Basic
    while q:
        v = q.popleft()
        for i in graph[v]:
            if not visited[i]:
                q.append(i)
                visited[i] = True

    # 2. Check by distance
    dist = 0
    while q:
        dist += 1
        # You can check the client by dist by hanging the for statement 
        # inside the while statement in this way.
        for _ in range(len(q)):
            x, y = q.popleft()
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if 0 <= nx < N and 0 <= ny < N and (visited[nx][ny] == False) and B[nx][ny] != 1:
                    q.append((nx, ny))
                    visited[nx][ny] = True
                    if B[nx][ny] == -1:
                        heapq.heappush(client_pq, (nx, ny, dist))

This post is part of Python-Team-Notes for coding test posting that I posted. If you have any questions or mistakes regarding the code, please point it out!