CODEWITHSUNDEEP
algorithmgraph
palindrome88
palindrome88

Reputation: 95

Least points that can traverse all points in the directed graph

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.

Upvotes: 1

Views: 1174

Answers (2)

yiksanchan
yiksanchan

Reputation: 1940

  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

Upvotes: 1

Alexios Tsiaparas
Alexios Tsiaparas

Reputation: 910

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.

Upvotes: 0

Related Questions