在有向图中找到两个节点之间的所有路径 [英] finding all paths between two nodes in directed graph

问题描述

大家好，我试图找到有向图中两个节点之间的所有路径，这里是我的代码，但它没有正常工作..任何人都可以帮我解决它

谢谢提前。

hi all , i`m trying to find all paths between two nodes in directed graph here is my code BUT it didn`t work correctly .. could any one help me to fix it
thanks in advance.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
//using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Collections.Specialized;
using System.Collections;

namespace Direct_Graph
{
  class Program
  {
    public class Digraph
    {
      private readonly int _v; //The number of vertices
      private int _e; //The number of edges
      private LinkedList<int>[] adj; //Use a LinkedList for the adjacency-list representation

      //Create a new directed graph with V vertices
      public Digraph(int V)
      {
        if (V < 0)
          throw new Exception("Number of vertices in a Digraph must be nonnegative");
          
        this._v = V;
        this._e = 0;
        //Create a new adjecency-list for each vertex
        adj = new LinkedList<int>[V];
        for (int v = 0; v < V; v++)
        {
          adj[v] = new LinkedList<int>();
        }
      }

      //return the number of vertices
      public int V()
      {
        return _v;
      }

      //return the number of edges
      public int E()
      {
        return _e;
      }

      //Add an edge to the directed graph from v to w
      public void AddEdge(int v, int w)
      {
        if (v < 0 || v >= _v) 
          throw new Exception("vertex " + v + " is not between 0 and " + (_v - 1));
        if (w < 0 || w >= _v)
          throw new Exception("vertex " + w + " is not between 0 and " + (_v - 1));
        
        adj[v].AddFirst(w);
        _e++;
      }

      /*
        * Return the adjacency-list for vertex v, which
        * are the vertices connected to v pointing from v
      * */
      public LinkedList<int> Adj(int v)
      {
        if (v < 0 || v >= _v) 
          throw new Exception();
      
        return adj[v];
      }

       //Return the directed graph as a string
       public String toString()
       {
         StringBuilder s = new StringBuilder();
         String NEWLINE = Environment.NewLine;
         //s.Append(_v + " vertices, " + _e + " edges " + NEWLINE);
         for (int v = 0; v < _v; v++)
         {
           s.Append(String.Format("{0:d}: ", v));
           foreach (int w in adj[v])
           {
             s.Append(String.Format("{0:d} ", w));
           }
           s.Append(NEWLINE);
         }
         return s.ToString();
       }
     }
  
    public class Search
    {
      int START;
      int END;

      public void DepthFirstSearch(Digraph graph, LinkedList<int> visited)
      {
        // int v = visited.Last();
                
        LinkedList<int> nodes = graph.Adj(visited.Last());
               
        // examine adjacent nodes
        foreach (int node in nodes)
        {
          if (visited.Contains(node))
            continue;

          if (node == END)
          {
            visited.AddFirst(node);
            printPath(visited);
            visited.RemoveLast();
            break;
          }
        }

        // in breadth-first, recursion needs to come after visiting adjacent nodes
        foreach (int node in nodes)
        {
          if (visited.Contains(node) || node == END)
            continue;
 
          visited.AddLast(node);
          DepthFirstSearch(graph, visited);
          visited.RemoveLast();
        }
      }

      public void printPath(LinkedList<int> visited)
      {
        foreach (int node in visited)
        {
          Console.Write(node);
          Console.Write(" ");
        }
        Console.WriteLine();
      }
    }

    static void Main(string[] args)
    {
      int START = 3;
      int END = 8;

      Digraph dg = new Digraph(30);

      dg.AddEdge(3, 4);
      dg.AddEdge(4, 8);
      dg.AddEdge(4, 11);
      dg.AddEdge(11, 14);
      dg.AddEdge(11, 17);
      dg.AddEdge(11, 8);
      dg.AddEdge(14, 8);
      dg.AddEdge(14, 17);
      dg.AddEdge(14, 25);
      dg.AddEdge(17, 22);
      dg.AddEdge(17, 25);
      dg.AddEdge(25, 8);
      dg.AddEdge(22, 25);
             
      LinkedList<int> visited = new LinkedList<int>();
      visited.AddFirst(START);
      Search s = new Search();
      s.DepthFirstSearch(dg, visited);
      s.printPath(visited);
    }
  }
}

推荐答案

Google：查找有向图中两个节点之间的所有路径 [ ^ ]

Google: finding all paths between two nodes in directed graph[^]

我已经修复了错误..谢谢大家试图帮助我。

i`ve fixed the error .. Thank you all for trying to help me .

这篇关于在有向图中找到两个节点之间的所有路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！