Pseudokod

Lekcja 4 z 9 w kursie Przeszukiwanie w głąb — algorytmy grafowe w Coddy.

buildAdjacency(n, edges):
   adj = n empty lists
   for each pair (u, v) in edges:
      adj[u].add(v)
      adj[v].add(u)         # undirected
   sort every adj[i] ascending

dfs(n, edges, start):
   build adjacency
   visited = all false
   stack = [start]
   order = []
   while stack not empty:
      node = stack.pop()
      if visited[node]: continue
      visited[node] = true
      order.add(node)
      for nb in adj[node] from last to first:
         if not visited[nb]: stack.push(nb)
   return order

Lista sąsiedztwa przekształca płaską tablicę krawędzi w posortowaną listę sąsiadów dla każdego wierzchołka.
Dodawanie sąsiadów od końca do początku sprawia, że stos zwraca najpierw najmniejszego sąsiada, dzięki czemu kolejność odwiedzania jest deterministyczna.

Spróbuj swoich sił

Ta lekcja nie zawiera wyzwania z kodem.