3

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.

Narendra Modi
  • 851
  • 1
  • 13
  • 29
  • 4
    The "strong" part makes no sense in an undirected setting. How about following the definition exactly, i.e. trying to find out which vertices you can reach from each vertex in the graph? – Anthony Labarre Jun 16 '17 at 17:17
  • @AnthonyLabarre sure an undirected graph can never be called "strongly connected" but how do you call an undirected graph where there is an edge between every single vertices? And what algorithm to find sub-graphs like that? I think that is what being asked here. – Khoi Jul 20 '21 at 02:06
  • 1
    @Khoi: you seem to ask a different question from Narendra Modi. An undirected graph where every pair of vertices is adjacent is a **complete graph** or a **clique**, and you can find them by enumerating all subsets of fixed size (see e.g. [Wikipedia](https://en.wikipedia.org/wiki/Clique_problem)). Narendra Modi seems to want to find an [Eulerian cycle](https://en.wikipedia.org/wiki/Eulerian_path). – Anthony Labarre Jul 20 '21 at 08:40

1 Answers1

4

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

Gefen Morami
  • 313
  • 1
  • 5