How do I find the smallest cycle of an undirected graph?

Asked

Viewed 697 times

2

I can find a cycle in an undirected graph. But I can’t think of a way to list the vertices of each cycle, and not even find the smallest cycle. How do I do this?

graph

  • Have you done anything? You can specify your doubt better, what you are trying?

  • I am trying to finish the algorithm to check if there is a cycle in the graph. I wanted to list all the cycles of an undirected graph. And I wanted to find the smallest cycle of this graph.

  • I can tell you where to look, the book Mathematical Fundamentals for Computer Science, Judith L Gersting.

  • Although I’m pretty sure it’s an NP problem, why the number of paths is factorial if it’s a complete graph.

  • Thanks man, I’ll take a look!

  • It’s really an NP problem, I believe.

  • Also look at this topical, to see if it doesn’t help the doubt.

Show 2 more comments

2 answers

1

There are several algorithms, for valued graphs, that is, where each edge has a weight, examples: Dijkstra algorithm, Bellman-Ford algorithm, Algorithm A*, Floyd-Warshall algorithm, Johnson algorithm.

But as the meeting of the shortest path is a complete NP problem, the solutions are inefficient, or even mathematically incalculable in numbers not so large. If I’m not mistaken for directed graphs I used the algorithm of Floyd-Warshall.

0

First you must give weight 1 to all existing edges of your graph and weight INFINITO rough grafo[i][i] to every vertex i. Also make your graph pseudo-directed:

grafo[i][j] = 1
grafo[j][i] = 1

to any vertices i and j connected.

Usually the weight on the edge grafo[i][i] is of 0, what makes sense when you seek the shortest way, since it costs nothing not moving in the graph, but if you keep it that way and run the algorithms below, your end result will be just 0, since the smallest cycle of a vertex up to itself will always be the way vertex i -> vertex i, that is to say, not moving in the graph.

That said, you can run the Algorithm by Dijkstra to every vertex i, using i as the initial and final vertex of the algorithm, i.e., how much it costs to get to the vertex i from the vertex itself i (remembering that the answer will not be 0 because you defined that grafo[i][i] = INFINITO). And as the weights of the edges are all 1, the shortest path will also give you the shortest distance cycle. Running this algorithm for all vertices you will have to grafo[i][i] will be the cost of the smallest cycle in which the vertex i is involved, for every vertex i. Final complexity O(n 3):

Dijkstra: O(n^2)
Executado n vezes, onde n é a quantidade de vértices no grafo.
Final: O(n^2) * n --> O(n^3)

To find the smallest cycle in the entire graph, run the above algorithm and then take min(grafo[i][i]) to every vertex i, that is: taking all the cycles in which the vertices are involved, which one is the smallest?!

And finally, to list the vertices involved in the smallest cycle, add to the algorithm a list of previously visited vertices in the shortest path (shortest cycle, in this case) between any vertices i and j and return to the vertex list i that is part of the smallest cycle encountered by min(grafo[i][i]), as discussed above. example en.

Browser other questions tagged graph

You are not signed in. Login or sign up in order to post.