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!
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.
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
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
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.
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.
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.
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.
-[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