CODEWITHSUNDEEP
c++algorithmgraph-theoryadjacency-matrixgraph-traversal
Arkaprabha Banerjee
Arkaprabha Banerjee

Reputation: 5

How to find the cycles present (with the vertex no as well ) in an undirected graph using only adjacency list?

I f you have only an adjacency matrix ,how do you find where are the cycles present in the undirected graph?

Upvotes: 1

Views: 563

Answers (2)

Madison
Madison

Reputation: 11

To find the cycles in an undirected graph, you'll want to run depth-first search (DFS) on that graph. If your graph is represented as an adjacency matrix, this has a running time of Θ(V+E), where V is the number of vertices and E is the number of edges. As you run DFS, you'll want to classify each edge that you traverse as either a tree edge or a back edge. An edge between vertices u and v, denoted (u, v), is a tree edge if v was not seen before (u, v) was processed. (u, v) is a back edge if v was already discovered before (u, v) was processed. The discovery of a back edge indicates that there is a cycle in the graph because a path exists out of a vertex from one edge and back into that same vertex from a different edge. Once you have classified all of your edges, any back edge (u, v) forms a cycle with the tree edges that form a path from u to v.

Upvotes: 1

Patrick87
Patrick87

Reputation: 28292

You can find all of what I will call the "simple" cycles as I describe below. What I refer to as "simple" cycles are cycles which do not contain any sub-cycles. If you include "non-simple" cycles, it's possible that a graph has infinitely many. For instance, consider this graph:

     (C)--(D)
      |   /
      |  /
      | /
(A)--(B)
  \   |
   \  |
    \ |
     (E)

The "simple" cycles are ABE and BCD. All other cycles contain one of these complete cycles. If we want to include "non-complete" ones, we get infinitely many cycles in the following sequence: ABE, ABCDBE, ABCDBCDBE, …, or AB(CDB)*E (to borrow from regular expressions).

To find the cycles I describe, do a depth-first search from each vertex in the graph, looking for the initial node encountered at a level lower than the root of the search. To keep the cycles "simple", we stop searching along a path if we encounter any of the other nodes (besides the root) we've already seen. On our example graph, here's how this looks:

Depth-first search from A for A
DFS search to B, AB
 DFS search to C, ABC
  DFS search to D, ABCD
   DFS search to B; duplicate, skip;
   no other unvisited notes reachable, go up;
  no other unvisited nodes reachable, go up;
 DFS search to D, ABD
  DFS search to C, ABDC
   DFS search to B; duplicate; skip;
   no other unvisited nodes reachable, go up;
  no other unvisited nodes reachable, go up;
 DFS search to E, ABE
  DFS search to A; found target; register ABE;
  no other unvisited notes reachable, go up;
DFS search to E, AE
 DFS search to B, AEB
  DFS search to A; found target; register AEB;
  DFS search to C, AEBC
   DFS search to D, ABECD
    DFS search to B; duplicate; skip;
    no other unvisited nodes reachable; go up;
   no other unvisited nodes reachable; go up;
  no other unvisited nodes reachable; go up;
 no other unvisited nodes reachable; go up;
no other unvisited nodes reachable; go up;
(return)

If we continue this for the remaining nodes I believe we will find the following registered cycles:

ABE, AEB
BAE, BEA, BCD, BDC
CDB, CBD
DBC, DCB
EBA, EAB

Note that these may be equivalent by rotation and, since the graph is undirected, they are also equivalent by inversion (that is, ABE and EBA are the same cycle). To address this, I recommend first transforming each cycle listed above into a "canonical" representation as follows:

  1. rotate the cycle so the earliest vertex comes first
  2. reverse the cycle and then rotate the cycle so the earliest vertex comes first
  3. choose as the canonical cycle whichever one has the earliest vertices first

Here is what this looks like in our case:

Original    Rotated   Reversed    Reverse-Rotated    Chosen    Reason
ABE         ABE       EBA         AEB                ABE       ABE < AEB
AEB         AEB       BEA         ABE                ABE       ABE < AEB
BAE         AEB       EAB         ABE                ABE       ABE < AEB
BEA         ABE       AEB         AEB                ABE       ABE < AEB
BCD         BCD       DCB         BDC                BCD       BCD < BDC
BDC         BDC       CDB         BCD                BCD       BCD < BDC
CDB         BCD       BDC         BDC                BCD       BCD < BDC
CBD         BDC       DBC         BCD                BCD       BCD < BDC
DBC         BCD       CBD         BDC                BCD       BCD < BDC
DCB         BDC       BCD         BCD                BCD       BCD < BDC
EBA         AEB       ABE         ABE                ABE       ABE < AEB
EAB         ABE       BAE         AEB                ABE       ABE < AEB

We find there are two unique cycles chosen: ABE and BCD.

Upvotes: 0

Related Questions