深さの最初の検索注文

Question

深さのある最初の検索では、ノードが訪問されるたびに、その隣接ノードの1つをもう一度取得し、この隣接ノードに対してこのプロセスを実行する必要があります。それに応じて、複数の深さの最初の検索オーダーが存在する可能性があります。したがって、アルゴリズムを適用せずに手作業で計算することで、グラフ内のDFSの異なる注文を数える方法はありますか？できるだけ早く解決策を教えてください。

Answer 1

あなたは、各レベルでノードを数え、次のレベルに進むたびに掛け算をすることでそれを行うことができます。

LinkedList<Node> connections = startNode.connections; 
    long totalOrders = 1L; 
    while(!connections.isEmpty()){ 
     LinkedList<Node> newConnections = new LinkedList<>(); 
     List<Integer> conSizes = new LinkedList()<>; 
     for (Node connection : connections) { 
      if(!connection.visited){      
       connection.visited = true; 
       newConnections.addAll(connection.connections); 
       totalOrders = totalOrders * factorial(connection.connections.size()); 
      } 
     } 
     totalOrders = totalOrders * factorial(connections.size()); 
     connections = newConnections; 

    } 
    System.out.println(totalOrders) 


    public static long factorial(int n) { 
     long fact = 1; // this will be the result 
     for (int i = 1; i <= n; i++) { 
      fact *= i; 
     } 
     return fact; 
    }