Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached.

I thought to run an SCC algorithm to find binding components and then return them. This is true? Or is there a better algorithm?

  • 1
    $\begingroup$ What are the strongly connected components of a graph without circles? Are you familiar with the concepts of sources and sinks? $\endgroup$
    – Pål GD
    Jan 21 '19 at 11:03
  • $\begingroup$ Try using a topological sort. $\endgroup$ Jan 21 '19 at 11:17
  • $\begingroup$ After the use of topological sort, there is a row of vertices arranged by a forward edge, what is the next step? $\endgroup$
    – Kate
    Jan 21 '19 at 13:35

Considering the strongly connected component is a good start if graph $G$ may have cycles. However, as implied by Pål GD, every vertex is a strongly connected component of a graph without cycles. We need to do more work to find the minimum set of vertices from which all vertices can be reached.

Here is the outline of an algorithm that does the job.

  1. Find one root $r$ of $G$ by repeatedly going to the ancestor of a node. Mark $r$ as an wanted vertex.
  2. Remove all vertices reachable from $r$.
  3. Go to step 1 unless there is no more vertex.
  4. return all vertices that are marked as wanted.

Exercise. Given a directed graph (that may have cycles), describe an algorithm that finds a minimum set of vertices from which all vertices can be reached. (Hint, strongly connected components are useful now. Try reducing the problem to the current question.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.