CODEWITHSUNDEEP
graph-theorydigraphseuler-path
Thierry Tang
Thierry Tang

Reputation: 1

Find the minimum number of connected subgraph that covers the whole digraph

I have a large directed graph, and I try to access every edge for this digraph. The problem is to minimize the number of the access (a connected subgraph is counted as one access). And it reduces to count the minimum number of connected subgraph that covers the whole digraph. Is there any existing study or algorithm in this area?

I found some related topic such as finding the largest Eulerian subgraph, but it is different to find the minimum number of subgraphs.

Upvotes: -1

Views: 47

Answers (1)

ravenspoint
ravenspoint

Reputation: 20472

To find the number of components in a graph using DFS ( Depth First Search ):

 - zero component count
 - unmark all vertices
 - WHILE unmarked vertices remain
    - increment component count
    - Select any unmarked vertex
       - mark selected vertex
       - Apply DFS starting from selected vertex, marking every visited vertex
 - END WHILE

Upvotes: -1

Related Questions