CODEWITHSUNDEEP
algorithmgraph
Narendra Modi
Narendra Modi

Reputation: 861

Finding Strongly Connected Components in Undirected Graphs

I want to find a strongly connected components in undirected graph i.e If i start from a Node A then i will get back to node A and each edge is visited exactly by once.

For Directed Graph can use Tarjan’s algorithm for finding the strongly connected components , but how to do for undirected graph.

Upvotes: 3

Views: 5807

Answers (1)

Gefen Morami
Gefen Morami

Reputation: 323

I think you miss understood the meaning of strongly connected component.

Strongly connected components

A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected component (SCC) of a directed graph is a maximal strongly connectedsubgraph. 

But, from your definition to what your looking for, I'd say you want to find cycle in undirected graph:

  • enters each node once

  • you can start from node A and finish in node A.

If it's only what you look for I'd say use DFS algorithm to find cycle in undirected graph.

Hope I answered your question

Upvotes: 4

Related Questions