Depth first search orders

Question

In depth first search, whenever a node is visited, we have to again take one of its adjacent nodes and the perform this process for this adjacent node. Depending on this , there may be multiple Depth first search orders. So , is there any way to count the total different DFS orders in a graph without applying the algorithm and manually calculating? Please give me the solution as soon as possible..

Answer 1

you can do it by counting the nodes at each level and keep multiplying every time going to the next level.

    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;
    }