title: How to find Longest path in graph
body: <p>I have one problem with my solution for finding longest path in graph. My Programm works very slow when vertices are close to each other. Here is my code please help me.</p>
  
  <blockquote>
    <p>Test class</p>
  </blockquote>
  
  <pre><code>public class GraphTest : MonoBehaviour {
  
  // Use this for initialization
  void Start () {
  
      const int w = 5;
      const int h = 4;
  
  
      int[,] data = new int[h,w]{
          {0,0,0,1,0},
          {0,0,0,1,0},
          {0,0,1,1,0},
          {0,0,0,0,0}};
  
      Map map = new Map(data,w,h);
  
      List&lt;Node&gt; longest = map.longestPath();
      Debug.Log("LONGEST " + longest.Count);
  
      //INFO this doing for printing array with steps
      int c = longest.Count-1;
      foreach(Node n in longest)
          data[n.r,n.c] = c--;
  
      string st = "";
      for(int i = 0; i &lt; h; i++ )
      {
          for(int j = 0; j &lt; w; j++)
          {
              st += data[i,j] + ",";
          }
          st += "\n";
      }
  
      Debug.Log(st);
  }
  }
  </code></pre>
  
  <blockquote>
    <p>Node class</p>
  </blockquote>
  
  <pre><code>public class Node
  {
  public int r,c;
  public int data;
  public Node[] neighbors;
  
  public Node(int r, int c, int data)
  {
      this.r = r;
      this.c = c;
      this.data = data;
      neighbors = new Node[8];
  }
  }
  </code></pre>
  
  <blockquote>
    <p>Map class for finding paths</p>
  </blockquote>
  
  <pre><code>public class Map
  {
  public static int[] xDir = {1,1,1,0,-1,-1,-1,0};
  public static int[] yDir = {-1,0,1,1,1,0,-1,-1};
  
  public Node[,] map;
  public int[,] mapData;
  
  private int width,height;
  private int[,] marks;
  public Map(int[,] mapData,int width,int height)
  {
      this.mapData = mapData;
      this.width = width;
      this.height = height;
  
      createNodes();
      initNeighbors();
  }
  //INFO create nodes
  private void createNodes()
  {
      map = new Node[height,width];
      for(int i = 0; i &lt; height; i++ )
      {
          for(int j = 0; j &lt; width; j++)
          {
              map[i,j] = new Node(i,j,mapData[i,j]);
          }
      }
  }
  //INFO assign neighbor nodes
  private void initNeighbors()
  {
      for(int i = 0; i &lt; height; i++ )
      {
          for(int j = 0; j &lt; width; j++)
          {
              for(int k = 0; k &lt; 8; k++)
              {
                  if(inRange(i+yDir[k],j+xDir[k]))
                  {
                      map[i,j].neighbors[k] = map[i+yDir[k],j+xDir[k]];
                  }
              }
          }
      }
  }
  
  private bool inRange(int r, int c)
  {
      return r &lt; height &amp;&amp; r &gt;= 0 &amp;&amp; c &lt; width &amp;&amp; c &gt;= 0;
  }
  
  public List&lt;Node&gt; longestPath()
  {
      marks = new int[height,width];
      List&lt;Node&gt; nodes = new List&lt;Node&gt;();
      int c = dfs(map[0,0],nodes);
  
      //INFO Iterasions count
      Debug.Log("COUNT " + c);
      return nodes;
  }
  
  private int dfs(Node node, List&lt;Node&gt; nodes)
  {
      int i = 1;
      List&lt;Node&gt; longest = new List&lt;Node&gt;();
      List&lt;Node&gt; list = null;
      marks[node.r,node.c] = 1;
  
      for(int n = 0; n &lt; 8; n++)
      {
          //INFO if the neighbor node is not null and same type with parent node do dfs for neighbor node
          if(node.neighbors[n] != null &amp;&amp; 
             marks[node.neighbors[n].r,node.neighbors[n].c] == 0 &amp;&amp;
             node.neighbors[n].data == node.data)
          { 
              list = new List&lt;Node&gt;();
              i += dfs(node.neighbors[n],list);
             //INFO if the found nodes count is more than previous nodes count set new nodes to best nodes
              if(list.Count &gt; longest.Count)
                  longest = list;
          }
      }
  
      marks[node.r,node.c] = 0;
      longest.Add(node);
      nodes.AddRange(longest);
  
      return i;
  }
  }
  </code></pre>