fork download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. namespace Rextester
  5. {
  6.     public class Program
  7.     {
  8.         public static void Main(string[] args)
  9.         {
  10.                                 // 0  1  2  3  4  5  6
  11.             int[,] matrix = {     {0, 1, 1, 0, 0, 0, 0},
  12.                                   {1, 0, 0, 1, 1, 1, 0},
  13.                                   {1, 0, 0, 0, 0, 0, 1},
  14.                                   {0, 1, 0, 0, 0, 0, 1},
  15.                                   {0, 1, 0, 0, 0, 0, 1},
  16.                                   {0, 1, 0, 0, 0, 0 ,0},
  17.                                   {0, 0, 1, 1, 1, 0, 0}  };
  18.  
  19.             bool[] visitMatrix = new bool[matrix.GetLength(0)];
  20.             Program ghDemo = new Program();
  21.  
  22.             for (int lpRCnt = 0; lpRCnt < matrix.GetLength(0); lpRCnt++)
  23.             {
  24.                 for (int lpCCnt = 0; lpCCnt < matrix.GetLength(1); lpCCnt++)
  25.                 {
  26.                     Console.Write(string.Format(" {0}  ", matrix[lpRCnt, lpCCnt]));
  27.                 }
  28.                 Console.WriteLine();
  29.             }
  30.  
  31.             Console.Write("\nDFS Recursive : ");
  32.             ghDemo.DftRecursive(matrix, visitMatrix, 0);
  33.             Console.Write("\nDFS Iterative : ");
  34.             ghDemo.DftIterative(matrix, 0);
  35.  
  36.             Console.Read();
  37.         }
  38.  
  39.         //====================================================================================================================================
  40.  
  41.         public void DftRecursive(int[,] srcMatrix, bool[] visitMatrix, int vertex)
  42.         {
  43.             visitMatrix[vertex] = true;
  44.             Console.Write(vertex + "  ");
  45.  
  46.             for (int neighbour = 0; neighbour < srcMatrix.GetLength(0); neighbour++)
  47.             {
  48.                 if (visitMatrix[neighbour] == false && srcMatrix[vertex, neighbour] == 1)
  49.                 {
  50.                     DftRecursive(srcMatrix, visitMatrix, neighbour);
  51.                 }
  52.             }
  53.         }
  54.  
  55.         public void DftIterative(int[,] srcMatrix, int srcVertex)
  56.         {
  57.             bool[] visited = new bool[srcMatrix.GetLength(0)];
  58.  
  59.             Stack<int> vertexStack = new Stack<int>();
  60.             vertexStack.Push(srcVertex);
  61.  
  62.             while (vertexStack.Count > 0)
  63.             {
  64.                 int vertex = vertexStack.Pop();
  65.  
  66.                 if (visited[vertex]) continue;
  67.                 Console.Write(vertex + "  ");
  68.                 visited[vertex] = true;
  69.  
  70.  
  71.                 for (int neighbour = srcMatrix.GetLength(0) - 1; neighbour >= 0; neighbour--)
  72.                 //for (int neighbour = 0; neighbour < srcMatrix.GetLength(0); neighbour++)
  73.                 {
  74.                     if (srcMatrix[vertex, neighbour] == 1 && visited[neighbour] == false)
  75.                     {
  76.                         vertexStack.Push(neighbour);
  77.                         // Try jumping to neighbour, will miss other neighbour in the current loop, here recursion wins with backtracing.  
  78.                         //vertex = neighbour; 
  79.                     }
  80.                 }
  81.             }
  82.         }
  83.     }
  84. }
Success #stdin #stdout 0s 132160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 0   1   1   0   0   0   0  
 1   0   0   1   1   1   0  
 1   0   0   0   0   0   1  
 0   1   0   0   0   0   1  
 0   1   0   0   0   0   1  
 0   1   0   0   0   0   0  
 0   0   1   1   1   0   0  

DFS Recursive : 0  1  3  6  2  4  5  
DFS Iterative : 0  1  3  6  2  4  5
https://ideone.com/OW7JhS
language:
C# (gmcs 5.20.1)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!