From various books and online resources, I've come to know a directed graph is said to be strongly connected if, all of its vertices reachable from each vertices. But my question is, "is it same for the undirected graphs also ?" hence we can visit all vertices of an undirected from graph its each vertices.

  • $\begingroup$ An undirected graph is strongly connected iff it is connected. This is because edges are bidirectional. $\endgroup$ – Chrystomath Apr 8 at 10:16
  • $\begingroup$ I think @Chrystomath is right, I see it is nonsense to say that an undirected graph is strongly connected. $\endgroup$ – Fareed AF Apr 8 at 10:19
  • $\begingroup$ @Chrystomath & Fareed AF please see Misha Lavrov's answer below $\endgroup$ – Shahriar Mim Apr 8 at 15:09

For an undirected graph, we simply say that it is connected when there is a path between any two vertices.

There are then (at least) two ways to generalize this notion to directed graphs:

  • Weakly connected if there is an undirected path between any two vertices, not necessarily respecting the orientations on the edges.
  • Strongly connected if there is a directed path between any two vertices.

These two definitions have the names they do because strong connectivity implies weak connectivity, but not vice versa. (If, between any two vertices, there is a directed path, it is still a path if we don't care about the orientations.)

In an undirected graph, because there is only one notion of connectivity to begin with, we don't call it strong or weak.

  • $\begingroup$ thanks but " strong connectivity implies weak connectivity " I am struggling to understand this line. $\endgroup$ – Shahriar Mim Apr 8 at 15:08
  • $\begingroup$ Edited to clarify that. Strong connectivity cares about directions on edges, and weak connectivity doesn't, so if you have the paths needed to satisfy strong connectivity, then those same paths are also going to give you weak connectivity. $\endgroup$ – Misha Lavrov Apr 8 at 15:17
  • $\begingroup$ thank you so much $\endgroup$ – Shahriar Mim Apr 8 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.