Logo

Programming-Idioms

History of Idiom 130 > diff from v6 to v7

Edit summary for version 7 by bukzor:
[Python] line width
↷

Version 6

2018-04-08, 19:17:47

Version 7

2018-04-08, 19:18:25

Idiom #130 Depth-first traversing in a graph

Call a function f on every vertex accessible for vertex v, in depth-first prefix order

Illustration

Idiom #130 Depth-first traversing in a graph

Call a function f on every vertex accessible for vertex v, in depth-first prefix order

Illustration
Extra Keywords
dfs
Extra Keywords
dfs
Code 
def depth_first(start, f):
  seen = set()
  stack = [start]
  while stack:
    vertex = stack.pop()
    f(vertex)
    seen.add(vertex)
    stack.extend(v for v in vertex.adjacent if v not in seen)
Code 
def depth_first(start, f):
  seen = set()
  stack = [start]
  while stack:
    vertex = stack.pop()
    f(vertex)
    seen.add(vertex)
    stack.extend(
      v for v in vertex.adjacent if v not in seen
    )
Comments bubble
It's best to not recurse in Python when the structure size is unknown, since we have a fixed, small stack size.
Comments bubble
It's best to not recurse in Python when the structure size is unknown, since we have a fixed, small stack size.