Minimal Vertices

Application of Topological Sort, Strongly Connected Components and Tarjan's Algorithm


Problem Statement:

Given a directed graph G , find the minimum number of vertices from which all nodes are reachable.
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:

Algorithm:


Login to Access Content




Working Solution:

Java code:



Login to Access Content



Python code:



Login to Access Content




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



Instructor:

Abhishek Dey

Abhishek Dey

Senior SDE | Chief Architect

Microsoft | University of Florida

View LinkedIn profile


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


Help Your Friends save 40% on our products

wave