CODEWITHSUNDEEP
graphdepth-first-searchundirected-graph
Francisco Azevedo
Francisco Azevedo

Reputation: 5

Most efficient algorithm to know if undirected graph is connected

I´ve been trying to find an algorithm to search if a graph is connected. The graph is undirected and I only want to find a solution (there can be multiple) or if there is none. I was looking for a alg. that performs near linear time, maybe O(logN) or O(NlogN).

Can DFS be up to the task or is there another alternative for this specific problem?

Upvotes: 0

Views: 913

Answers (1)

amit
amit

Reputation: 178411

It's going to depend on how you define N, if N is number of vertices, the input itself can be of size O(N^2), and you will be needing to read all of it (unless you have some specific ordering of the input, and than that might change).

DFS runs in O(|V|+|E|) (number of nodes + number of edges), and can find if the graph is connected by simply counting the number of new vertices you discover, and when done, checking if this number is |V|.

Upvotes: 1

Related Questions