Least points that can traverse all points in the directed graph

1
votes

Given directed graph, find the minimum set of vertices that can traverse all the vertices in the graph.

E.g: 
    5 -> 4  
    4 -> 6
    6 -> 7
    5 -> 8

In the above example, the minimum set of vertices will be "5", as you can visit all other vertices from vertex 5.

Is this doable using BFS or DFS?I think Kosaraju's algorithm might work, but checking if there is a easy way to do this.

2
algorithmgraph
Please provide reference to any algorithm or pseudo code if it is doable using DFS or BFS. – palindrome88

2 Answers

1
votes
  1. Find SCCs (strong connected components) of the graph.
  2. Consider each component of SCCs as a SccNode, which is a set of nodes.
  3. For each SccNode, randomly pick one of its node. This will create a result set S of nodes.
  4. Depth first search on S, elminate nodes that can be reached by other nodes in S. Remained nodes are what you want.

Reference:

  1. Find SCC: I suggest using Kosaraju-Sharir
  2. Online judgement for the question (problem description is in Chinese): Summer Holiday
0
votes

A simple approach that you can use in order to find the minimum set of vertices is to enumerate every possible traversal for the graph and return the minimum solution.