Non-recursive Depth-First Search (DFS) Using a Stack

int stackk[100];
int top=-1;
void graph::dfs(int v){
 stackk[++top]=v;
// visited[v]=1;
 while(top!=-1){
   int x=stackk[top--];
   if(!visited[x])
    {visited[x]=1;
     cout<<x<<endl;
    }
   for(int i=V-1;i>=0;i--)
   {
        if(!visited[i]&&adj[x][i])
        {   //visited[i]=1;
            stackk[++top]=i;
        }
   }
 }
}
void graph::Dfs_Traversal(){
 for(int i=0;i<V;i++)
  visited[i]=0;
 for(int i=0;i<V;i++)
  if(!visited[i])
    g.dfs(i);

I think I managed to write a much simpler pseudo-code.

but first a few remarks to make things a bit clear:

1. v.pDescendant - a pointer to a vertex descendant given by its adjacency list.
2. in the adjacency list, i assumed each element has a field "pNext" that points to the next element on the linked list.
3. I've used some C++ syntax, mainly "->" and "&" to emphasize what is a pointer and what is not.
4. Stack.top() returns a pointer to the first element of the stack. but unlike pop(), it does not remove it.

The algorithm is based on the following observation: a vertex is pushed into the stack when visited. and removed (popped) only when we are done examining (blackening) all its descendants.

DFS(G)
1. for all vertices v in G.V do
2.   v.color = WHITE; v.parent = NIL; v.d = NIL; v.f = NIL; v.pDescendant = adj[v].head
3. time = 0 
4. Initialize Stack
5. for all vertices v in G.V s.t. v.color == WHITE do
6.   time++
7.   Stack.push(&v)
8.   v.color = GRAY 
9.   v.d = time 
10.   DFS-ITERATIVE(G,v)

DFS-ITERATIVE(G,s) 
1. while Stack.Empty() == FALSE do
2.   u = Stack.top();
3.   if u.pDescendant == NIL // no Descendants to u || no more vertices to explore
4.      u.color = BLACK
5.      time++
6.      u.f = time
7.      Stack.pop()
8.   else if (u.pDescendant)->color == WHITE
9.      Stack.push(u.pDescendant)
10.     time++
10.     (u.pDescendant)->d = time
11.     (u.pDescendant)->color = GRAY
12.     (u.pDescendant)->parent = &u
12.     u.pDescendant= (u.pDescendant)->pNext // point to next descendant on the adj list      
13.  else
14.     u.pDescendant= (u.pDescendant)->pNext // not sure about the necessity of this line      

Both algorithms are fine. The second one is a direct translation from recursive to stack-based. All mutating state are stored in the stack. G never changes during the execution of the algorithm.

The algorithms will produce a spanning tree for each disconnected region, based on the order the algorithm visited each node. The trees will be represented both with references to the parent-nodes (u.π), and as segment trees (u.d and u.f).

A child will have a reference to its parent node (or NULL if it is a root), as well as having it's range (child.d .. child.f) contained within it's parent's range.

parent.d < child.d < child.f < parent.f

child.π = parent

---

Edit: I found a mistake in the translation. You are not actually pushing the current state into the stack, but a future method argument. In addition, you are not coloring the popped nodes GRAY and setting the f field.

Here is a rewrite of the original first algorithm:

algorithm Stack-DFS(G)
    for each vertex u ∈ G.V
        u.color ← WHITE
        u.π ← NIL
    time ← 0
    S ← empty stack
    for each vertex u ∈ G.V
        if u.color = WHITE
            # Start of DFS-VISIT
            step ← 1
            index ← 0
            loop unconditionally
                if step = 1
                    # Before the loop
                    u.color ← GRAY
                    time ← time + 1
                    u.d ← time
                    step ← 2
                if step = 2
                    # Start/continue looping
                    for each vertex v ∈ G.Adj[u]
                        i ← index of v
                        if i ≥ index and v.color = WHITE
                            v.π ← u
                            # Push current state
                            push((u, 2, i + 1), S)
                            # Update variables for new call
                            u = v
                            step ← 1
                            index ← 0
                            # Make the call
                            jump to start of unconditional loop
                    # No more adjacent white nodes
                    step ← 3
                if step = 3
                    # After the loop
                    u.color ← BLACK
                    time ← time + 1
                    u.right ← time
                    # Return
                    if S is empty
                        break unconditional loop
                    else
                        u, step, index ← pop(S)

There is probably a few places that could be optimized, but should at least work now.

Result:

Name   d    f   π
q      1   16   NULL
s      2    7   q
v      3    6   s
w      4    5   v
t      8   15   q
x      9   12   t
z     10   11   x
y     13   14   t
r     17   20   NULL
u     18   19   r