Algorithm in Python (depth-first search, dfs)

Introduction

When doing depth-first search with python, I heard that there is anxiety about performance with recursion, so I decided to implement it with stack and left it in the article as a memorandum. I hope it helps you learn, and if you have any advice, please leave a comment!

theme

This time, we will consider the time it takes to start a certain vertex and reach each vertex, which is a typical theme in depth-first search. (Is it an order rather than a time?) At that time, check the arrival time ** going order **, check the last passing time ** returning order **, and record both together with ** time stamp ** We will deal with the three cases. The last pass is just after the search for all vertices below that vertex. I won't go into detail about dfs, but I'll go deeper from the starting point to where I can go, and if I can't go any further, I'll go back to the previous fork and repeat the same thing. Here, suppose that the one with the younger vertex number is searched preferentially.

Input / output

input

Enter the number of vertices on the first line as an integer, then the vertex number, the number of adjacent vertices, and the adjacent vertices on the N line, separated by spaces.

6
1 2 2 3
2 2 3 4
3 1 5
4 1 6
5 1 6
6 0

output

The vertex number, arrival time, and search end time are output on line N, separated by spaces. (Only the former is in the order of going, and only the latter is in the order of returning.)

1 1 12
2 2 11
3 3 8
4 9 10
5 4 7
6 5 6

Implementation

Going order

dfs_1.py


#Depth-first search (going)
import sys
input = sys.stdin.readline
from collections import deque

#Creating a graph(In the undirected graph#Erase)
N = int(input())
graph = [deque([]) for _ in range(N + 1)]
for _ in range(N):
    u, k, * v = [int(x) for x in input().split()] #u is the vertex number, k is the number of adjacent vertices
    v.sort()
    for i in v:
        graph[u].append(i)
        # graph[i].append(u) #Undirected graph

time = 0
arrive_time = [-1] * (N + 1) #Arrival time

#Depth-first search
def dfs(v):
    global time
    time += 1
    stack = [v]
    arrive_time[v] = time
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if arrive_time[w] < 0:
                time += 1
                arrive_time[w] = time
                stack.append(w) 
        else:
            stack.pop()          
    return arrive_time

#Measures against isolated vertices
for i in range(N):
    if arrive_time[i + 1] < 0:
        ans = dfs(i + 1)

#Vertex number, arrival time
for j in range(N):
    temp = [j + 1, ans[j + 1]]
    print(* temp)

First, the graph is represented by an adjacency list. Here, it is considered as a directed graph, but it can also be treated as an undirected graph by removing one # in the code. The time can be treated as a global variable on a common time axis regardless of which vertex is called, and when a new vertex is reached, it is incremented by +1 and recorded in the arrival time arrive_time list. Some directed graphs cannot be reached from the start vertex, so we will perform a depth-first search for all vertices if they have not been reached. Since stack is last-in first-out, it takes out the back element and examines the adjacent vertices. Remove those vertices from the adjacency list so that you can see what you have examined. If the contents are empty, the search for the vertex is finished, so delete it from the stack.

Return order

dfs_2.py


#Depth-first search (return)
import sys
input = sys.stdin.readline
from collections import deque

#Creating a graph(In the undirected graph#Erase)
N = int(input())
graph = [deque([]) for _ in range(N + 1)]
for _ in range(N):
    u, k, * v = [int(x) for x in input().split()] #u is the vertex number, k is the number of adjacent vertices
    v.sort()
    for i in v:
        graph[u].append(i)
        # graph[i].append(u) #Undirected graph

time = 0
arrive = [-1] * (N + 1) #Have you arrived
finish_time = [-1] * (N + 1) #Search end time

#Depth-first search
def dfs(v):
    global time
    stack = [v]
    arrive[v] = 1
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if arrive[w] < 0:
                arrive[w] = 1
                stack.append(w) 
        else:
            time += 1
            finish_time[v] = time
            stack.pop()          
    return finish_time

#Measures against isolated vertices
for i in range(N):
    if arrive[i + 1] < 0:
        ans = dfs(i + 1)

#Vertex number, end time
for j in range(N):
    temp = [j + 1, ans[j + 1]]
    print(* temp)

The variables and ideas used are almost the same, but this time we will record the time when the search ended in finish_time, not the time when it arrived. In other words, when deleting adjacent vertices of a certain vertex from the adjacency list, when it becomes empty, the time advances and the time is recorded.

Going time + returning time

dfs_3.py


#Depth-first search (going, returning)
import sys
input = sys.stdin.readline
from collections import deque

#Creating a graph(In the undirected graph#Erase)
N = int(input())
graph = [deque([]) for _ in range(N + 1)]
for _ in range(N):
    u, k, * v = [int(x) for x in input().split()] #u is the vertex number, k is the number of adjacent vertices
    v.sort()
    for i in v:
        graph[u].append(i)
        # graph[i].append(u) #Undirected graph

time = 0
arrive_time = [-1] * (N + 1) #Arrival time
finish_time = [-1] * (N + 1) #Search end time

#Depth-first search
def dfs(v):
    global time
    time += 1
    stack = [v]
    arrive_time[v] = time
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if arrive_time[w] < 0:
                time += 1
                arrive_time[w] = time
                stack.append(w) 
        else:
            time += 1
            finish_time[v] = time
            stack.pop()          
    return [arrive_time, finish_time]

#Measures against isolated vertices
for i in range(N):
    if arrive_time[i + 1] < 0:
        ans = dfs(i + 1)

#Vertex number, arrival time, end time
for j in range(N):
    temp = [j + 1, ans[0][j + 1], ans[1][j + 1]]
    print(* temp)

Just combine the above two. In other words, when a certain vertex is reached or the search below it is completed, the time advances and they are recorded in arrive_time and finish_time.

Finally

I'm not an information department, so I'm studying by referring to articles and books on the internet. Especially for this depth-first search, although the idea is simple, it was very difficult for me as a beginner to implement it. (The code in this article may also be incorrect), so please give us some advice in the comments or on Twitter! If you have any advice on speeding up, please do not hesitate to contact us.

References

-[DFS (Depth-first Search) Super Introduction! ~ Entrance to the world of graph algorithms ~ [Part 1]](https://qiita.com/drken/items/4a7869c5e304883f539b#3-4-dfs-%E3%81%AE%E6%8E%A2%E7% B4% A2% E9% A0% 86% E5% BA% 8F% E3% 81% AB% E3% 81% A4% E3% 81% 84% E3% 81% A6% E3% 81% AE% E8% A9% B3% E7% B4% B0) This is an article by Kencho. All of them are easy to understand and are always indebted. -[Algorithm and data structure for programming contest capture] (https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E6%94%BB%E7%95%A5%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0-%E6%B8%A1%E9%83%A8-%E6%9C%89%E9%9A%86/dp/4839952957) I referred to the problems and ideas.

Recommended Posts

Algorithm in Python (depth-first search, dfs)
[Python] DFS (Depth-first Search) ATC001A
Algorithm in Python (binary search)
[Python] DFS (Depth-first Search) ABC157D
Algorithm in Python (breadth-first search, bfs)
Write a depth-first search in Python
Depth-first search using stack in Python
Implement Depth-First Search (DFS) and Breadth-First Search (BFS) in python
Algorithm in Python (ABC 146 C Binary 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)
I tried to solve AtCoder's depth-first search (DFS) in Python (result: TLE ...)
Algorithm in Python (primality test)
Search for strings in Python
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
Write a binary search in Python
Python algorithm
Develop an investment algorithm in Python 2
Implementing a simple algorithm in Python 2
Algorithm (segment tree) in Python (practice)
Run a simple algorithm in Python
[Python algorithm] A program that outputs Sudoku answers from a depth-first search
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
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
N-Gram in Python
String search algorithm
Programming in python
Plink in Python
Constant in python
Lifegame in Python.
FizzBuzz in Python