CODEWITHSUNDEEP
data-structuresgraph-theory
Sahil
Sahil

Reputation: 9478

Strongly Connected Graph is cyclic graph or not?

I am fairly new to Graph theory and I have a a very basic doubt regarding Strongly connected component of a graph. It says two nodes or more are strongly connected if there are paths from both nodes to each other.so whether this graph qualifies as a cyclic graph with cycles?

Upvotes: 1

Views: 2587

Answers (1)

sxu
sxu

Reputation: 551

Yes, strongly connected graphs are cyclic. In such graphs any two vertices, say u and v are strongly connected, so there exists a path from u to v and a path from v to u made of directed edges. If the u->v path and the v->u path are disjoint, concatenate them and you have the cycle. If they share edges, start from u and follow the u->v path, once you hit the first edge shared by the two paths, start following the v->u path until you return to u.

Upvotes: 2

Related Questions