Databases
StackOverflow2013
Postsdbo
PONon-recursive Depth-First Search (DFS) Using a Stack
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PONon-recursive Depth-First Search (DFS) Using a Stack
    primarykey
    data
    text
    <p>Ok this is my first post on Stack Overflow I have been reading for a little while and really admire the site. I am hoping this is something that will be acceptable to ask. So I have been reading through Intro to Algorithms (Cormen. MIT Press) all the way through and I am up to the graph algorithms. I have been studying the formal algorithms laid out for breadth and depth first search in very fine detail.</p> <p>Here is the psuedo-code given for depth-first search:</p> <pre><code>DFS(G) ----------------------------------------------------------------------------------- 1 for each vertex u ∈ G.V 2 u.color ← WHITE // paint all vertices white; undiscovered 3 u.π ← NIL 4 time ← 0 // global variable, timestamps 5 for each vertex u ∈ G.V 6 if u.color = WHITE 7 DFS-VISIT(G,u) DFS-VISIT(G, u) ----------------------------------------------------------------------------------- 1 u.color ← GRAY // grey u; it is discovered 2 time ← time + 1 3 u.d ← time 4 for each v ∈ G.Adj[u] // explore edge (u,v) 5 if v.color == WHITE 6 v.π ← u 7 DFS-VISIT(G,v) 8 u.color ← BLACK // blacken u; it is finished 9 time ← time + 1 10 u.f ← time </code></pre> <p>This algorithm is recursive and it proceeds from multiple sources (will discovered every vertex in unconnected graph). It has several properties that most language specific implementations might leave out. It distinguishes between 3 different 'colors' of vertices. It initially paints all of them white, then when they are 'discovered' (visited in DFS-VISIT) they are then painted gray. The DFS-VISIT algorithm runs a loop recursively calling itself on the adjacency list of the current vertex and only paints a vertex black when it has no more edges to any white node.</p> <p>Also two other attributes of each vertex are maintained u.d and u.f are the time stamps to when the vertex was discovered (painted gray) or when a vertex is finished (painted black). The first time a node is painted it has a time stamp of one and it is incremented to the next integer value for each time another is painted (whether it be grey or black). u.π is also maintained which is just a pointer to the node from which u was discovered.</p> <pre><code>Algorithm Non-Recursive-DFS(G) ----------------------------------------------------------------------------------- 1 for each vertex u ∈ G.V 2 u.color ← WHITE 3 u.π ← NIL 4 time = 0 5 for each vertex u ∈ G.V 6 if u.color = WHITE 7 u.color ← GRAY 8 time ← time + 1 9 u.d ← time 7 push(u, S) 8 while stack S not empty 9 u ← pop(S) 10 for each vertex v ∈ G.Adj[u] 11 if v.color = WHITE 12 v.color = GRAY 13 time ← time + 1 14 v.d ← time 15 v.π ← u 16 push(v, S) 17 u.color ← BLACK 18 time ← time + 1 19 u.f ← time </code></pre> <p><strong>* EDIT 10/31/12 *</strong> This is embarrassing that my algorithm has been incorrect for so long, it would work in most cases, but not all. I just got a popular question badge for the question and I saw where Irfy had spotted the problem in his answer below, so that is where the credit goes. I am just fixing it here for anyone that needs this in the future.</p> <p>Does anyone see a flaw with the above algorithm? I am by far no expert on graph theory, but I think I have a pretty good grasp on recursion and iteration and I believe this should work the same. I am looking to make it functionally equivalent to the recursive algorithm. It should maintain all the attributes of the first algorithm even if they are not needed.</p> <p>When I began writing it I did not think I would have a triply loops but that's the way it turned out. I have seen other iterative algorithms when I looked around Google that only have a doubly nested loop, however, they do not appear to proceed from multiple sources. (i.e. they will not discover every vertex of unconnected graph)</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCory Gross
    1. USCory Gross
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. PONon-recursive Depth-First Search (DFS) Using a Stack
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PONon-recursive Depth-First Search (DFS) Using a Stack
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PONon-recursive Depth-First Search (DFS) Using a Stack
      1. This table or related slice is empty.
      1. VTUpMod
    1. COPlease correct indentation after `if` statement in second loop in second algorithm. Ideally also the indentation after first `for` loop
      singulars
      1. PONon-recursive Depth-First Search (DFS) Using a Stack
      1. USIrfy
    2. COMade the edit just now, this is what I had originally.
      singulars
      1. PONon-recursive Depth-First Search (DFS) Using a Stack
      1. USCory Gross
    3. COThe finish times computed by the non-recursive version will be wrong. u.f <-time can only be set after all descendants have their finish time set. If one takes the same example in CLRS, then the node u would have a finish time=3, whereas the actual value should have been 8.
      singulars
      1. PONon-recursive Depth-First Search (DFS) Using a Stack
      1. USGuru Devanla
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload