What is the difference between "connected", "strongly connected", and "reachable" in a graph?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Connected: Usually associated with undirected graphs (two way edges): There is a path between every two nodes.
Strongly connected: Usually associated with directed graphs (one way edges): There is a route between every two nodes (route ~ path in each direction between each pair of vertices).
Reachable (from $A$ to $B$): A path exists in the graph between nodes $A$ and $B$. (Ability to get from one vertex to another)
Note: Got some terminology from: https://mathoverflow.net/questions/6833/difference-between-connected-vs-strongly-connected-vs-complete-graphs
-
1$\begingroup$ route is an unusual word to use. See wiki page strongly connected component to realise route here means a path for each direction. $\endgroup$ Commented Jan 9, 2017 at 21:45