Minimal Vertices
Application of Topological Sort, Strongly Connected Components and Tarjan's Algorithm
-
Algorithms and Data Structures: TheAlgorist.com
-
System Design: DistributedComputing.dev
-
Low Level Design: LowLevelDesign.io
-
Frontend Engineering: FrontendEngineering.io
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:This is a Premium content.
Please subscribe to the Algorithms course to access the detailed Algorithm discussion.
Working Solution:
Java code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Python code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Don't forget to take a look at other interesting Graph Problems:
- How to Send Message to Entire Social Network
- Disconnected Network
- Critical Connection
- Course Scheduling
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
