I am implementing Depth-first search algorithm. There are two requirements: I must use Stack (no Recursion), and it should also returns the discovery time and finish time. Here is the code using recursion I implemented:
def dfs(graph, source):
"""Depth-first search algorithm
This function computes depth-first search and prints the nodes as it travels
Arguments:
graph: List[List[int]], adjacency matrix of the graph
source: int, the starting point
Returns:
None
"""
visited = [False] * len(graph)
time_start = [0] * len(graph) # Time when vertex is discovered
time_finish = [0] * len(graph) # Time when vertex has finished discovering
time = 0
dfs_visit(graph, source, visited, time, time_start, time_finish)
return time_start, time_finish
def dfs_visit(graph, source, visited, time, time_start, time_finish):
time += 1
time_start[source] = time
visited[source] = True
print(source, end = " ")
for i, val in enumerate(graph[source]):
if not visited[i] and val != 0:
dfs_visit(graph, i, visited, time, time_start, time_finish)
time += 1
time_finish[source] = time
Sample input:
graph = [[0, 1, 1, 0],
[1, 0, 1, 0],
[1, 1, 0, 1],
[0, 0, 1, 1]]
Expected output: 2 0 1 3 ([2, 3, 1, 2], [3, 4, 2, 3]) where the first array indicates discovery time and the second indicates finish time (by index).
Taken that idea I implemented the DFS using Stack:
def dfs_stack(graph, source):
"""Depth-first search algorithm using stack
This function computes depth-first search and prints the nodes as it travels
Arguments:
graph: List[List[int]], adjacency matrix of the graph
source: int, the starting point
Returns:
None
"""
visited = [False] * len(graph)
dfs_visit(graph, source, visited)
return time_start, time_finish
def dfs_visit(graph, source, visited):
stack = []
stack.append(source)
while (len(stack)):
s = stack[-1]
stack.pop()
if not visited[s]:
print(s, end = " ")
visited[s] = True
for idx, val in enumerate(graph[s]):
if (not visited[idx]) and val != 0:
stack.append(idx)
I try to put time += 1; time_start[s] = ... to calculate these time but it outputs weird result. Where should I put the time counter correctly?
First a few remarks about your code:
The times that are logged are somewhat confusing, as you have duplicate timestamps (e.g. 3). This is because the increments you make to time are not fed back to the caller, which has its own time variable instance. I would make time a non local variable, so that it keeps incrementing.
So I would change that to:
def dfs(graph, source):
def dfs_visit(graph, source, visited, time_start, time_finish):
nonlocal time
time += 1
time_start[source] = time
visited[source] = True
print(source, end = " ")
for i, val in enumerate(graph[source]):
if not visited[i] and val != 0:
dfs_visit(graph, i, visited, time_start, time_finish)
time += 1
time_finish[source] = time
visited = [False] * len(graph)
time_start = [0] * len(graph)
time_finish = [0] * len(graph)
time = 0
dfs_visit(graph, source, visited, time_start, time_finish)
return time_start, time_finish
Now the output of print(dfs(graph, 2)) will be:
2 0 1 3 ([2, 3, 1, 6], [5, 4, 8, 7])
This makes more sense to me, but maybe I misunderstood what you intended to do with time.
s = stack[-1] followed by stack.pop() can really be written as s = stack.pop()
You are pushing all children of a node unto the stack before processing their children. This means that actually the depth-first traversal will visit children from last-to-first, while your recursive implementation visits them from first-to-last.
Now to the core of your question. If you want to register the finishing time of a visit, you'll need to leave a trace of the node on the stack, and only remove it from that stack when all its children have been processed; not earlier.
One way to achieve that, is to store on the stack which was the last neighbor that was visited from the node. So you would store (node, neighbor) tuples. If no next node had been visited yet from that node, then the initial value for neighbor could be -1.
Here is how that would work:
def dfs_stack(graph, source):
visited = [False] * len(graph)
time_start = [0] * len(graph)
time_finish = [0] * len(graph)
time = 0
stack = [(source, -1)]
while stack:
node, neighbor = stack.pop()
if neighbor == -1:
if visited[node]:
continue
visited[node] = True
print(node, end = " ")
time += 1
time_start[node] = time
try:
neighbor = graph[node].index(1, neighbor + 1)
stack.append((node, neighbor))
if not visited[neighbor]:
stack.append((neighbor, -1))
except ValueError: # no more neighbors...
time += 1
time_finish[node] = time
If we call this with print(dfs_stack(graph, 2)) we also get:
2 0 1 3 ([2, 3, 1, 6], [5, 4, 8, 7])