How to implement depth first search for graph with a non-recursive approach

by

A DFS without recursion is basically the same as BFS – but use a stack instead of a queue as the data structure.

The thread Iterative DFS vs Recursive DFS and different elements order handles with both approaches and the difference between them (and there is! you will not traverse the nodes in the same order!)

The algorithm for the iterative approach is basically:

DFS(source):
  s <- new stack
  visited <- {} // empty set
  s.push(source)
  while (s is not empty):
    current <- s.pop()
    if (current is in visited):
        continue
    visited.add(current)
    // do something with current
    for each node v such that (current,v) is an edge:
        s.push(v)

More Related Contents:

  1. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  2. Cycles in an Undirected Graph
  3. Breadth First Vs Depth First
  4. Millions of 3D points: How to find the 10 of them closest to a given point?
  5. Graph auto-layout algorithm
  6. Find connected components in a graph [closed]
  7. Finding all the shortest paths between two nodes in unweighted undirected graph
  8. What are the practical factors to consider when choosing between Depth-First Search (DFS) and Breadth-First Search (BFS)? [closed]
  9. Algorithm for “nice” grid line intervals on a graph
  10. Iterative DFS vs Recursive DFS and different elements order
  11. Longest acyclic path in a directed unweighted graph
  12. help in the Donalds B. Johnson’s algorithm, i cannot understand the pseudo code (PART II)
  13. Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?
  14. What algorithm to use to determine minimum number of actions required to get the system to “Zero” state?
  15. Enumerating all paths in a directed acyclic graph
  16. How does Dijkstra’s Algorithm and A-Star compare?
  17. Why DFS and not BFS for finding cycle in graphs
  18. Find cycle of shortest length in a directed graph with positive weights
  19. graph – Dijkstra for The Single-Source Longest Path
  20. Why is depth-first search claimed to be space efficient?
  21. Planar Graph Layouts
  22. Bridges in a connected graph
  23. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  24. Finding connected components of adjacency matrix graph
  25. Complete graph with only two possible costs. What’s the shortest path’s cost from 0 to N – 1
  26. Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction)
  27. How to compute Discrete Fourier Transform?
  28. search for interval overlap in list of intervals?
  29. Is there ever a good reason to use Insertion Sort?
  30. Can an array be grouped more efficiently than sorted?

Leave a Comment