• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



Problem Statement:

Given a directed graph G , find the minimum number of vertices (let's call these vertices minimal vertices) from which all nodes are reachable. Print these minimal vertices.
For example:
          0<-------1
                  _
            \     /|
            _\|  /
               2

               |
              \ /

               3 _
             /  |\
           |/_    \
            4----->5


The above graph would have only one 1 minimal vertex: either vertex 1, 2 or 3. You can reach all the vertices if you 'start traversing from either vertex 1 , 2 or 3.

          0<-------1
                  _
            \     /|
            _\|  /
               2

              / \
               |
               3
               |
              \ /

               6 _
             /  |\
           |/_    \
            4----->5
For the above graph all the nodes are reachable from vertex 3.

Tag(s): #airbnb_interview

Solution:


Let's look at 3 different graphs below:


The minimal vertices are marked in RED. If you start traversing from all the RED vertices you would eventually reach all other vertices in the directed graphs.

What's the common characteristics you notice for all the vertices marked in red ? They all have no inbound edges. Basically if you do a Topological Sort of all the vertices in the given directed graph, you need to include only those vertices which have indegree = 0 and are located all the way left in the topologically sorted list (i.e, towards the beginning of the topologically sorted list). Vertices with indegree = 0 are the vertices that have no inbound edges. These are the vertices which are minimal vertices and all other vertices are reachable at least from any one of these minimal vertices.

Presence of Strongly Connected Component(s):


What's missing from the directed graphs in the above diagram is Strongly Connected Components. Please read the chapter Strongly Connected Components (SCC) to know more about it.

A very important observation here is that all the vertices belonging to a Strongly Connected Component has non-zero indegree since all of them have at least one inbound edge.


These Strongly Connected Components (SCC) can be of two types:
  1. Isolated SCC, i.e, SCC with no incoming cross-edge or a forward edge from a vertex that is not part of the same SCC:

    This kind of SCCs are totally disconnected from the rest of the graph, and cannot be reached from a node outside of the SCC or from other SCC. In this case we just need to make the indegree for the root of the Strongly Connected Component zero and include that in our list of minimal vertices. The SCC below is an isolated SCC.


  2. SCC reachable from some other vertex which is not part of the same SCC:

    This kind of Strongly Connected Component is connected to the rest of the graph by one or more vertices outside of the SCC (through forward edge) or from any other SCC (through cross-edge). In this case there is at least one cross-edge or forward edge from a node that is not part of this SCC.

    In this case we do not need to include any of the vertices in the SCC in our list of minimal vertices , since all the SCC (and all the vertices in the SCC) can be reached from one or more vertices which are not part of the SCC. In the below diagram SCC 5-6-7 is connected to the SCC 2-3-4 through the cross-edge 4->6. Also both SCC 2-3-4 and 5-6-7 are connected to the rest of the graph by vertex A. Both of these two SCCs have incoming forward edges from vertex A. So if user A gets the message all the users in SCC 2-3-4 and 5-6-7 will get the message too.



In order to determine if an SCC is reachable from any vertex outside of the SCC, we need to remove all the edges in the SCC and see if one or more nodes in the SCC is still connected to at least one node that is not part of the same SCC. If it is, then there is no need to include any node from this SCC to our minimal vertices list.
But if the above is not the case, then we need to include any one node from the SCC.

How can we determine if an SCC is connected to at least one node outside of the SCC ?
We find all the SCCs in the given directed graph. For each SCC: for each of the nodes present in the SCC we decrement indegree of all its adjacent nodes that are part of this SCC (to avoid including cross-edges) by 1. After this operation, if the indegree of all the nodes in the current SCC are zero, then it is an isolated SCC and one user from this SCC needs to be included in our minimal list. If not, then no node from this SCC needs to be included. Try to run this logic on the above two diagrams and it will become crystal clear.

Algorithm:
From the above observations we come to the below simple yet robust algorithm to solve the problem:


This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.


Concept of indegree is discussed in Topological Sort by BFS chapter.


Working Solution:

import java.util.*;

/**
 * Created by Abhishek on 9/21/20.
 */
public class MinimalVertices {

    int discoveryTime = 0; // discovery time

    // Nodes in adjacency lists are numbered from 0 to N - 1
    public void findSccAndDecrementIndegreeOfRoot(List< Set< Integer >> adjacencyLists, int[] indegree) {
        discoveryTime = 0; // reset index to 0
        int len = adjacencyLists.size();
        int[] discoveryTime = new int[len];
        int[] earliestDiscoveredNodeReachable = new int[len];
        Deque< Integer > sccStack = new ArrayDeque<>();
        boolean[] onStack = new boolean[len];

        for (int i = 0; i < adjacencyLists.size(); i++) {
            if (discoveryTime[i] == 0) { // indices[i] == 0 when vertex i is not already visited
                dfs(adjacencyLists, discoveryTime, earliestDiscoveredNodeReachable, sccStack, onStack, i, indegree);
            }
        }
    }

    private void dfs(
            List< Set< Integer >> adjacencyLists,
            int[] discoveryTimes,
            int[] earliestDiscoveredNodeReachable,
            Deque< Integer > strongComponentStack,
            boolean[] onStack,
            int currentNode,
            int[] indegree)
    {
        discoveryTime++;
        discoveryTimes[currentNode] = discoveryTime; // array is zero based index, nodes are numbered from 0 to N - 1
        earliestDiscoveredNodeReachable[currentNode] = discoveryTime;
        strongComponentStack.push(currentNode);
        onStack[currentNode] = true;
        for (int adjVertex : adjacencyLists.get(currentNode)) { //adjacencyList of vertex i is stored ar index i in arraylist
            if (discoveryTimes[adjVertex] == 0) { // discoveryTime[v] == 0 when vertex v is not already visited
                dfs(adjacencyLists, discoveryTimes, earliestDiscoveredNodeReachable, strongComponentStack, onStack, adjVertex, indegree);
                earliestDiscoveredNodeReachable[currentNode] =
                        Math.min(earliestDiscoveredNodeReachable[currentNode], earliestDiscoveredNodeReachable[adjVertex]);
            } else { // adjacentVertex is already visited
                if (!onStack[adjVertex]) {
                    // the adjacent vertex is already visited BUT it is not in the stack
                    // this means the current edge is just a cross edge to an SCC
                    // which has already been found and processed
                    continue;
                } else {
                    // adjacent vertex is in stack, so must be in the same SCC
                    earliestDiscoveredNodeReachable[currentNode] =
                            Math.min(earliestDiscoveredNodeReachable[currentNode], discoveryTimes[adjVertex]);
                    // NOTE: Because adjacentVertex is on the stack already, the edge (currentNode, adjacentVertex)
                    // is a back-edge in the DFS tree and
                    // therefore adjacentVertex is not in the subtree of currentNode.
                    // Because earliestDiscoveredNodeReachable[i]
                    // takes into account nodes reachable only through the nodes in the subtree of currentNode and we
                    // must stop at adjacentVertex and use discoveryTime[adjacentVertex]
                    // instead of earliestDiscoveredNodeReachable[adjacentVertex]. One back-edge is okay, but not more than one.
                }
            }
        }
        // now that DFS on currentNode is done lets see
        // if we got any SCC before backtracking
        if (earliestDiscoveredNodeReachable[currentNode] == discoveryTimes[currentNode]) {
            Set< Integer > sccNodes = new HashSet<>();
            int top = 0;
            // construct a set of all the nodes in this SCC
            do {
                top = strongComponentStack.pop();
                sccNodes.add(top);
                onStack[top] = false;
            } while (top != currentNode); // root can have self loop as well. it takes care of that too.

            // Determine if there is any incoming edge from
            // a node that is not part of this SCC.
            // Presence of a cross-edge or a forward edge from outside of the SCC
            // would mean that this SCC is reachable from a vertex outside of this SCC
            // and need not be included in the minimum list of users to send message.
            for (int current : sccNodes) {
                for (int otherNode : sccNodes) {
                    if (adjacencyLists.get(otherNode).contains(current)) {
                        indegree[current]--;
                    }
                }
            }
            boolean isolatedSCC = true;
            for (int sccNode : sccNodes) {
                if (indegree[sccNode] != 0) {
                    isolatedSCC = false;
                }
            }
            for (int sccNode : sccNodes) {
                indegree[sccNode] = Integer.MAX_VALUE;
            }
            if (isolatedSCC) {
                indegree[currentNode] = 0;
            }

        }

    }


    public List< Integer> getMinimalVertices(List< Set< Integer >> adjacencyLists) {
        int totalNumberOfUsers = adjacencyLists.size();
        int[] indegree = new int[totalNumberOfUsers];
        for (Set< Integer > adjacencyList : adjacencyLists) {
            for (int user : adjacencyList) {
                indegree[user]++;
            }
        }
        findSccAndDecrementIndegreeOfRoot(adjacencyLists, indegree);

        List< Integer > res = new ArrayList<>();

        for (int i = 0; i < totalNumberOfUsers; i++) {
            if (indegree[i] == 0) {
                res.add(i);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        /*
           0<-------1
                  _
            \     /|
            _\|  /
               2

              / \
               |
               3
               |
              \ /

               6 _
             /  |\
           |/_    \
            4----->5

            Expected Result => 3
         */
        List< Set< Integer >> adjLists = new ArrayList<>();
        adjLists.add(new HashSet< Integer >() {{ add(2); }}); // for node 0
        adjLists.add(new HashSet< Integer >() {{ add(0); }}); // for node 1
        adjLists.add(new HashSet< Integer >() {{ add(1); }}); // for node 2
        adjLists.add(new HashSet< Integer >() {{ add(2); add(6); }}); // for node 3
        adjLists.add(new HashSet< Integer >() {{ add(5); }}); // for node 4
        adjLists.add(new HashSet< Integer >() {{ add(6); }}); // for node 5
        adjLists.add(new HashSet< Integer >() {{ add(4); }}); // for node 6

        MinimalVertices ob = new MinimalVertices();
        List< Integer > res = ob.getMinimalVertices(adjLists);
        for (int i : res) {
            System.out.print(i + "  ");
        }
        System.out.println();
        System.out.println();

        /*
           0<-------1
                  _
            \     /|
            _\|  /
               2

               3

               6 _
             /  |\
           |/_    \
            4----->5

            Expected Result => 3 and (0 or 1 or 2) and (4 or 5 or 6)
         */
        adjLists = new ArrayList<>();
        adjLists.add(new HashSet< Integer >() {{ add(2); }}); // for node 0
        adjLists.add(new HashSet< Integer >() {{ add(0); }}); // for node 1
        adjLists.add(new HashSet< Integer >() {{ add(1); }}); // for node 2
        adjLists.add(new HashSet< Integer >()); // for node 3
        adjLists.add(new HashSet< Integer >() {{ add(5); }}); // for node 4
        adjLists.add(new HashSet< Integer >() {{ add(6); }}); // for node 5
        adjLists.add(new HashSet< Integer >() {{ add(4); }}); // for node 6

        ob = new MinimalVertices();
        res = ob.getMinimalVertices(adjLists);
        for (int i : res) {
            System.out.print(i + "  ");
        }
        System.out.println();
        System.out.println();


        /*
           0<-------1
                  _
            \     /|
            _\|  /
               2
               ^
               |
               3

               6 _
             /  |\
           |/_    \
            4----->5

            Expected Result => 3 and (4 or 5 or 6)
         */
        adjLists = new ArrayList<>();
        adjLists.add(new HashSet< Integer >() {{ add(2); }}); // for node 0
        adjLists.add(new HashSet< Integer >() {{ add(0); }}); // for node 1
        adjLists.add(new HashSet< Integer >() {{ add(1); }}); // for node 2
        adjLists.add(new HashSet< Integer >() {{ add(2);}}); // for node 3
        adjLists.add(new HashSet< Integer >() {{ add(5); }}); // for node 4
        adjLists.add(new HashSet< Integer >() {{ add(6); }}); // for node 5
        adjLists.add(new HashSet< Integer >() {{ add(4); }}); // for node 6

        ob = new MinimalVertices();
        res = ob.getMinimalVertices(adjLists);
        for (int i : res) {
            System.out.print(i + "  ");
        }
        System.out.println();
        System.out.println();


        /*
           0<-------1
                  _
            \     /|
            _\|  /
               2

               |
              \ /

               3 _
             /  |\
           |/_    \
            4----->5

            Expected result => 0 or 1 or 2
         */
        adjLists = new ArrayList<>();
        adjLists.add(new HashSet< Integer >() {{ add(2); }}); // for node 0
        adjLists.add(new HashSet< Integer >() {{ add(0); }}); // for node 1
        adjLists.add(new HashSet< Integer >() {{ add(1); add(3); }}); // for node 2
        adjLists.add(new HashSet< Integer >() {{ add(4); }}); // for node 3
        adjLists.add(new HashSet< Integer >() {{ add(5); }}); // for node 4
        adjLists.add(new HashSet< Integer >() {{ add(3); }}); // for node 5

        ob = new MinimalVertices();
        res = ob.getMinimalVertices(adjLists);
        for (int i : res) {
            System.out.print(i + "  ");
        }
        System.out.println();
        System.out.println();

        /*
           0<-------1
                  _
            \     /|
            _\|  /
               2


               3 _
             /  |\
           |/_    \
            4----->5

            Expected result => (0 or 1 or 2) and (3 or 4 or 5)
         */
        adjLists = new ArrayList<>();
        adjLists.add(new HashSet< Integer >() {{ add(2); }}); // for node 0
        adjLists.add(new HashSet< Integer >() {{ add(0); }}); // for node 1
        adjLists.add(new HashSet< Integer >() {{ add(1); }}); // for node 2
        adjLists.add(new HashSet< Integer >() {{ add(4); }}); // for node 3
        adjLists.add(new HashSet< Integer >() {{ add(5); }}); // for node 4
        adjLists.add(new HashSet< Integer >() {{ add(3); }}); // for node 5

        ob = new MinimalVertices();
        res = ob.getMinimalVertices(adjLists);
        for (int i : res) {
            System.out.print(i + "  ");
        }
        System.out.println();
        System.out.println();



        /*
            0

            Expected Result: 0
         */
        adjLists = new ArrayList<>();
        adjLists.add(new HashSet< Integer >()); // for node 0
        ob = new MinimalVertices();
        res = ob.getMinimalVertices(adjLists);
        for (int i : res) {
            System.out.print(i + "  ");
        }
        System.out.println();
        System.out.println();

        /*
            0------>1
            ^       |
            |_______|

            ExpectedResult: 0 or 1
         */
        adjLists = new ArrayList<>();
        adjLists.add(new HashSet< Integer >(){{add(1);}}); // for node 0
        adjLists.add(new HashSet< Integer >(){{add(0);}}); // for node 1
        ob = new MinimalVertices();
        res = ob.getMinimalVertices(adjLists);
        for (int i : res) {
            System.out.print(i + "  ");
        }
        System.out.println();
        System.out.println();


        /*
            1------>0

            ExpectedResult: 1
         */
        adjLists = new ArrayList<>();
        adjLists.add(new HashSet< Integer >()); // for node 0
        adjLists.add(new HashSet< Integer >(){{add(0);}}); // for node 1
        ob = new MinimalVertices();
        res = ob.getMinimalVertices(adjLists);
        for (int i : res) {
            System.out.print(i + "  ");
        }
        System.out.println();


    }

}






Don't forget to take a look at other interesting Graph Problems:



The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave