CODEWITHSUNDEEP
graph-theorydepth-first-searchstrongly-connected-graph
harrySherlock
harrySherlock

Reputation: 39

"A connected graph is connected if and only if a depth first search starting from any node visits every other node"

I am reading Mark Weiss's book (2nd Edition) and I can't wrap my head around this thing. How is this even possible. If a graph is undirected then there must be a way to visit every node from everyone. From the image (https://algorithms.tutorialhorizon.com/check-if-given-undirected-graph-is-connected-or-not/). If I want to visit any node from 4, I can. The only way, I can't is if I remove the connection to 4. If that happens, how is this a graph (in my mind graph needs to have edges). Can graphs have "dangling vertices"?

Upvotes: 1

Views: 239

Answers (1)

ravenspoint
ravenspoint

Reputation: 20472

Can graphs have "dangling vertices?

Yes. They can also have subgraphs, sets of vertices connected to each other but not connected to the vertices in other subgraphs. These are usually called components.

enter image description here

For more https://en.wikipedia.org/wiki/Component_(graph_theory)

Upvotes: 2

Related Questions