Find the starting node in a directed graph which covers the maximum number of nodes

#tutorial #datastructure #graph #beginners

Given a directed graph with N number of nodes and exactly N number of edges. Each node has exactly one outgoing edge from it. Find a path such that the maximum number of nodes can be covered from the starting point, and return the starting point.

NOTE: A node can have multiple edges which are pointing towards him, but only one outgoing edge



Input: N = 5
1->2, 2->1, 3->1, 4->2, 5->3

Graph Structure:



Output: 5
Explanation: 
If we start from node 1 as beginning then the path is: 1 -> 2
If we start from node 2 as beginning then the path is: 2 -> 1
If we start from node 3 as beginning then the path is: 3 -> 1 -> 2
If we start from node 4 as beginning then the path is: 4 -> 2 -> 1
If we start from node 5 as beginning then path is: 5 -> 3 -> 1 -> 2

Hence, we can clearly see that if we start for 5, we cover the 
maximum number of nodes in the
graph i.e. 4.

Approach:

To find the number of nodes reachable from a particular node, one thing to observe is that we can reach from a node X to a node Y only when they are in the same connected component.

Since the graph is directional, any node in a connected component to any other node in the same connected components. Hence for a particular node X number of nodes that will be reachable will be the number of nodes in that particular component. Use a depth-first search to find the answer.

CODE
Following is a Java implementation of the code:



import java.util.HashSet;
import java.util.Set;

public class Main{

    static int[] graph;

    // Driver Function
    public static void main(String[] args) {

        // Taking the number of nodes from the user
        int n = 5;

        // Array to store the nodes direction
        graph = new int[n];

        // Initializing graph
        // 1->2, 2->1, 3->1, 4->2, 5->3
        graph[0] = 1;
        graph[1] = 0;
        graph[2] = 0;
        graph[3] = 1;
        graph[4] = 2;

        System.out.println(find(n));
    }

    static int find(int n) {

        int max = 0; // Holds the maximum count of nodes visited
        int node = 0; // Starting index of the node with maximum max count

        // Considering each node one-by-one as beginning node
        // Using DFS to fully explore that node
        for (int i = 0; i < n; i++) {

            // Finding the total number of node that can be covered by
            // considering the ith node as beginning
            int visits = canVisit(i);

            if (visits > max) { // If ith node covers more node then
                max = visits; // Store the number of nodes covered
                node = i; // Store the node index
            }
        }

        // As we are considering the indices from 0 just add 1 into the index
        return node + 1; // and return it
    }

    // Function to perform the DFS calculating the
    // count of the elements in a connected component
    static int canVisit(int n) {
        // This set contains the indices of the visited elements
        // This will help use to make sure that we are not running
        // inside a cycle in the graph
        Set<Integer> set = new HashSet<>();

        set.add(n); // Add the current node into the graph as it is visited

        // Go to the next node in the graph towards with the current directs
        int visit = graph[n];

        // Hold the total number of nodes visited
        // Since we at least visit the beginning node hence assign count to 1
        int count = 1;

        // Explore until the node repeats or we reach at the dead-end
        while (!set.contains(visit)) {
            set.add(visit); // Add the next visit into the set
            visit = graph[visit]; // Jump to next directed node
            count++; // Increment the count as one more has been explored
        }

        return count; // Return the total number of nodes visited
    }
}

Complexity:

We will have the worst case if the graph is linearly connected with no internal cycles, which will give us O(N²). With an Auxiliary space of O(N).

Hands-on debugging session: instrument, monitor, and fix

Join Lazar for a hands-on session where you’ll build it, break it, debug it, and fix it. You’ll set up Sentry, track errors, use Session Replay and Tracing, and leverage some good ol’ AI to find and fix issues fast.

RSVP here →