Finding all cycles in a graph

There is a graph represented by a list in the file, where n is the number of vertices. You need to find all the cycles in the graph. So far, I have only read the graph from the code, so that it is clearer what is what.

#include <iostream>
#include <vector>
#include <set>

using namespace std;

#define FOR(i,a,b) for (int i(a), __N(b); i < __N; ++i)

typedef vector<int> VI;
typedef vector<VI> VVI;

set<VI> res;

void R(){}

int main(int argc, char *args){

    // переопределение потоков
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);

    // чтение графа
    int n, a, b;
    scanf("%d", &n);
    VVI G(n);
    res = set<VI>();
    while (scanf("%d %d", &a, &b) != -1){
        G[a].push_back(b);
        G[b].push_back(a);
    }

    // обработка графа

}
Author: Nicolas Chabanovsky, 2011-03-18
Source

2 answers

Tip: specify the wording

Unfortunately, it is very difficult to answer your question without an exact formulation of the problem. For starters, what are you looking for? Simple loops? Elements of a cyclic space? Regular cycles? Do you realize that for a complete graph with n vertices, the answer size in any of the above problems is at least n!? Such a huge size of the answer (and, therefore, the working time) suggests that from a practical point of view, the problem is not very useful (for a complete graph with 14 vertexes are about 100 billion cycles). Therefore, I highly recommend clarifying the statement/necessity of the task.

If you still need to solve this particular problem

For example, using the MST search algorithms, you can find all the fundamental cycles of a graph. Each cycle in the graph is a linear combination (the coefficients are taken 0 or 1, the addition is exclusive or cycles) of fundamental cycles, so by going through these combinations, and taking only the ones you need (only connected, or only simple ones), you will find the answer. This is far from the most optimal algorithm (O(2^m), where m is the number of edges), and I have no doubt that it can be improved slightly if the problem statement is refined.

 2
Author: ofitserov, 2011-03-24 01:09:07

Here you need to create the following classes:

struct TGraphConnection : public TObject{
    TPoint;   // содержит номера точек, которые он соединяет
};

class TGraphConnectionList : public TObjectList{ // содержит список всех соединений
};

class TGraphKnot : public TObjectList{
    __property int KnotNo...; // порядковый номер узла
    __property TGraphConnection *Connection[int Index]...;
};

// класс описания узла
// содержит набор TGraphConnection структур, которые примыкают к этому узлу
class TGraphKnotList : public TObjectList{
    __property TGraphKnot *Knot[int Index]...;
};
// содержит список TGraphKnotList - всех узлов графа

And the main class responsible for all the previous ones:

class TGraph{
    private:
    TGraphConnectionList *Connections;
    TGraphKnotList * Knots;

    public:
    // здесь конструктор-деструктор
    void __fastcall Calc(); // сама функция подсчета каких-то там циклов
};

Here's where it might look like this...

The algorithm for counting cycles can be easily found in the Internet...)))

 -2
Author: малыш, 2011-03-18 12:21:16