Algorithm in Python (breadth-first search, bfs)

Introduction

I will explain the implementation of breadth-first search using python. (Just put the one I always implement.) Breadth-first search often raises the issue of distance, so this time we will implement a function that returns the distance from one vertex to each vertex.

Breadth-first search

I think that a lot of general knowledge about breadth-first search will come out if you look it up, so I will omit it in detail, but I will explain it briefly.    89922.jpg As shown by the blue arrow, follow the vertices in order from the closest one. For the distance to be handled this time, add 1 to the distance to the previous vertex. (In the image, it is shaken from 1, but if it is a distance, you can shake it from 0.) The order of searching for this vertex is managed by the queue. A queue is a first-in, first-out data structure. In this example, the start 0 is entered first. ([0]) Next, take out the contents from the front and examine the adjacent vertices. (1 and 2 this time) If you are visiting for the first time, add it to the queue. ([1, 2]) If you repeat this, you can examine the vertices in the order of the blue arrows. ([2, 3, 4]→[3, 4, 5, 6]→[4, 5, 6, 7]...) The search ends when the queue is empty. thank you for your hard work.

Implementation

input

Given the number of vertices n and the number of edges m, then the adjacent vertices are given over m rows.

11 9
0 1
0 2
1 3
1 4
2 5
2 6
3 7
5 8
8 9

code

import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()] #n is the number of vertices, m is the number of sides
g = [[] for _ in range(n)] #Adjacency list

for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a].append(b)
    g[b].append(a)

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n #Initialization of distance from u
    d[u] = 0 #Distance to myself is 0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d

#Distance of each vertex from 0
d = bfs(0)
print(d)

output

Outputs a list with the distance from vertex 0 in order of vertex number from the left. The distance to you is 0, and the vertices you cannot reach are None.

[0, 1, 1, 2, 2, 2, 2, 3, 3, 4, None]

in conclusion

Please let me know if you have any mistakes! I would be grateful if you could give me some advice!

Recommended Posts

Algorithm in Python (breadth-first search, bfs)
[Python] BFS (breadth-first search) ABC168D
Algorithm in Python (binary search)
[Python] BFS (breadth-first search) ABC007C
Algorithm in Python (depth-first search, dfs)
Implement Depth-First Search (DFS) and Breadth-First Search (BFS) in python
Algorithm in Python (ABC 146 C Binary Search
Python Exercise 1-Breadth-first search
Binary search in Python
Genetic algorithm in python
Algorithm in Python (Bellman-Ford)
Linear search in Python
Binary search in Python (binary search)
Algorithm in Python (Dijkstra's algorithm)
Algorithm in Python (primality test)
Search for strings in Python
Breadth-first search / bidirectional search (Python version)
Search algorithm using word2vec [python]
Binary search in Python / C ++
Reproduce Euclidean algorithm in Python
Implement Dijkstra's Algorithm in python
[Python] Depth-first search and breadth-first search
I implemented breadth-first search in python (queue, drawing self-made)
Write a binary search in Python
Sorting algorithm and implementation in Python
Breadth-first search (BPF) Maybe understood (python)
Python algorithm
Write A * (A-star) algorithm in Python
Develop an investment algorithm in Python 2
Write a depth-first search in Python
Implementing a simple algorithm in Python 2
Algorithm (segment tree) in Python (practice)
Run a simple algorithm in Python
Depth-first search using stack in Python
Algorithm learned with Python 10th: Binary search
Algorithm learned with Python 9th: Linear search
Ant book in python: Sec.2-5 Dijkstra's algorithm
Search and play YouTube videos in Python
Search the maze with the python A * algorithm
Write a simple greedy algorithm in Python
In search of the fastest FizzBuzz in Python
Alignment algorithm by insertion method in Python
Algorithm learned with Python 12th: Maze search
Quadtree in Python --2
Python in optimization
CURL in python
Metaprogramming in Python
Python 3.3 in Anaconda
Geocoding in python
SendKeys in Python
[Python] 01-BFS ARC005C
Meta-analysis in Python
Python memorandum (algorithm)
Unittest in python
Epoch in Python
Discord in Python
Sudoku in Python
DCI in Python
quicksort in python
nCr in python
N-Gram in Python