non recursive depth first search behaving almost like c#

Question

I'm trying to implementnon recursive DFS algorithm in c# here is my method code

public void dfs(int vertex)
{
   int length = matrix.GetLength(0);
   bool[] visited = new bool[length]; 
   for (int k = 0; k < length; k++)
   {
     visited[k] = false; 
   }
   Stack<int> vertexStack = new Stack<int>();
   vertexStack.Push(vertex);
   visited[vertex] = true;
   Console.Write((vertex) + " ");
   while (vertexStack.Count() != 0)
   {
        int tempVertex = vertexStack.Peek();
        for (int j = 0; j < length; j++)
        {
            if (matrix[tempVertex, j] == 1 && !visited[j])
            {
                Console.Write(j + " ");
                visited[j] = true;
                vertexStack.Push(j);
            }
        }
        vertexStack.Pop();    
   }
}

and here is my graph code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
   {
    static void Main(string[] args)
    {

        int[,] matrix2 = {
        {0,1,1,1,0,0},
        {1,0,0,0,1,1},
        {1,0,0,0,0,1},
        {1,0,0,0,0,0},
        {0,1,0,0,0,0},
        {0,1,1,0,0,0},
                         };
        Graphs g2 = new Graphs(matrix2);
        g2.dfs(0);
       // Console.ReadKey();
     }
   }
}

for this graph the result of the dfs shoud be 0 1 4 5 2 3

but they are 0 1 2 3 5 4 which is almost like BFS for this graph 0 1 2 3 4 5

can anyone tell me What's wrong here ?

Answer 1

Firstly, after your loop you pop the last element that has been pushed. Instead pop the element before entering the loop.

Secondly, handle the elements as you take them from the stack, not when you push them onto it.

Thirdly, to achieve the order you want, iterate the children nodes backwards (so smaller children will be on top of the stack):

public void dfs(int vertex)
{
    int length = matrix.GetLength(0);
    bool[] visited = new bool[length];
    for (int k = 0; k < length; k++)
    {
        visited[k] = false;
    }
    Stack<int> vertexStack = new Stack<int>();
    vertexStack.Push(vertex);

    while (vertexStack.Count() != 0)
    {
        int tempVertex = vertexStack.Pop();
        if (!visited[tempVertex])
        {
            visited[tempVertex] = true;
            Console.Write((tempVertex) + " ");
            for (int j = length - 1; j >= 0; j--)
            {
                if (matrix[tempVertex, j] == 1 && !visited[j])
                {
                    vertexStack.Push(j);
                }
            }
        }
    }
}