How many components in a directed graph?

Question

I have the following graph:

The optimal solution is to start dfs from vertex (3) then i will get one component, but when we start the dfs from vertex (1) then (3) i will get two components. The question is: I want to know how many components in this graph? or on other way, what is the minimum number of dfs needed to cover all the graph?

what is the needed algorithm for doing this?

Answer 1

You are confusing two definitions.

For undirected graphs there is the notion of connected components, which you find by performing a DFS on the undirected graph.

For directed graphs there is the notion of strongly connected components, for which multiple algorithms are available, all slightly more complicated than a simple DFS.

What you should do depends on which of the two notions you need. Your graph has one connected component when viewed as an undirected graph, and two strongly connected components when viewed as a directed graph.

Answer 2

I believe you are trying to find weakly connected components . Testing whether a directed graph is weakly connected can be done easily in linear time. Simply turn all edges into undirected edges and use the DFS-based connected components algorithm.