C Depth First Search Algorithm

  • 2021-12-21 04:47:04
  • OfStack

In this paper, we share the specific code of C # depth-first search algorithm for your reference. The specific contents are as follows


// The paper will use its improved algorithm, first of all demo Test 1 Under 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DFS
{
  class Program
  {
    public int[,] map = new int[100, 100];
    public int[] road = new int[120];
    public int n, x, y;
    public int m = 1;
    public int[] visited = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
    static void Main(string[] args)
    {
      Program pro = new DFS.Program();
      int i, j;
      pro.n = int.Parse(Console.ReadLine());
      pro.x= int.Parse(Console.ReadLine());
      pro.y= int.Parse(Console.ReadLine());
    
      for (i = 0; i < pro.n; i++)
      {
        for (j = 0; j < pro.n; j++)
        {
          pro.map[i,j]= int.Parse(Console.ReadLine());
        }
      }
      pro.road[0] = pro.x;
      pro.dfs(pro.x);
    }
    public void dfs(int p)
    {
      visited[p] = 1;
      int i, j;
      for (i = 0; i < n; i++)
      {
        if (map[p,i] == 1 && visited[i] == 0)
        {
          if (i == y)/// If the deep search reaches the end point, the path just passed will be output  
          {
            for (j = 0; j < m; j++)
            {
              Console.WriteLine("{0}", road[j]);
            }
            Console.WriteLine("{0}\r\n", y);
          }
          else/// If this point is not the end point  
          {
            map[p,i] = 0;
            road[m] = i;/// Save the point  
            m++;
            dfs(i);/// Then search deeply  
            map[p,i] = 1;
            visited[i] = 0;
            m--;
          }
        }
      }
    }
  }
}

Related articles: