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

Graduate Expected numbers of cards of a last color remaining

Graduate Probability puzzle

Undergrad The problem of points

Undergrad The countability paradox of computable numbers

Undergrad How does axiom of foundation prevent infinite sequence of elements?

Graduate Cannot understand this corollary on surreal numbers

High School Bunkbed Conjecture Debunked?

Insights Revisiting the Velocity-Time Function

Insights Remote Operated Gate Control System

Insights AI Enriched Problem Solving

Insights Thinking Outside The Box Versus Knowing What’s In The Box

Insights Why Entangled Photon-Polarization Qubits Violate Bell’s Inequality

Insights Quantum Entanglement is a Kinematic Fact, not a Dynamical Effect

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}##