Поиск Эйлерова цикла

Необходимо в неориентированном графе найти цикл, проходящий по всем рёбрам, посещая каждое ровно один раз

Если граф ориентирован, то строка D[i][v] = 0; не нужна.

Асимптотика: если граф представлен списком рёбер O(M), если матрицей смежности - O(N²).

Листинг C++

void search_euler (int v, vector < vector < int > > &D, vector < int > &c)
{
    for (int i = 0; i < D[v].size (); ++ i)
        if (D[v][i]) // если ребро есть
        {
            // проходим по нему
            D[v][i] = 0;
            D[i][v] = 0;
            search_euler (i, D, c);
        }
    c.push_back (v);
}
void euler (vector < vector < int > > D, vector < int > &c)
{
    int i, j;
    int n = D.size ();
    c.clear ();

    // вычисляем степени вершин
    vector < int > degree (n, 0);
    for (i = 0; i < n; ++ i)
        for (j = 0; j < n; ++ j)
            if (D[i][j])
                ++ degree[i];

    // проверяем существует ли в данном графе эйлеров цикл
    int count = 0; // количество степеней не кратных двум
    j = 0; // начальная вершина
    for (i = 0; i < n; ++ i)
        if (degree[i] % 2 != 0)
        {
            ++ count;
            if (count > 2)
                return;
            j = i;
        }

    // находим цикл, проходящий по всем рёбрам только один раз
    search_euler (j, D, c);
}

01.06.2007, 14:41

По всем вопросам обращаться: rumterg@gmail.com