How to determine whether a graph is connected or not?

yakin · May 4, 2014

Nono713 · May 4, 2014

If you mean an algorithm, you can just use a standard search (BFS, DFS) starting from any point in the graph, keeping track of visited nodes. Once your search ends, check if there are any nodes that were not visited - if so, the graph is not connected, otherwise it is connected (can you prove this rigorously?).

How to determine whether a graph is connected or not?

Discussion

Similar threads

Chemistry How to determine whether a single reaction is better than multi-stage reaction?

Undergrad Determine whether ##125## is a unit in ##\mathbb{Z_471}##