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

[Danion]

Доброй ночи всем присутствующим.
Помогите пожалуйста решить проблему.
Пол-интернета обыскал, но так и не нашел нормального алгоритма для поиска эйлерова цикла в графе по заданной матрице смежности. Может быть кто-нибудь его выложит?
Если есть, можно исходники на C/C++,Java.
Спасибо за внимание, заранее благодарен.

[AlDelta]

Нахождение Эйлерова пути за O (M)

Эйлеров путь - это путь в графе, проходящий через все его рёбра. Эйлеров цикл - это эйлеров путь, являющийся циклом.

Задача заключается в том, чтобы найти эйлеров путь в неориентированном мультиграфе с петлями.

Алгоритм. Сначала проверим, существует ли эйлеров путь. Затем найдём все простые циклы и объединим их в один - это и будет эйлеровым циклом. Если граф таков, что эйлеров путь не является циклом, то, добавим недостающее ребро, найдём эйлеров цикл, потом удалим лишнее ребро.

Чтобы проверить, существует ли эйлеров путь, нужно воспользоваться следующей теоремой. Эйлеров цикл существует тогда и только тогда, когда степени всех вершин чётны. Эйлеров путь существует тогда и только тогда, когда количество вершин с нечётными степенями равно двум (или нулю, в случае существования эйлерова цикла).

Таким образом, идея такая же, как и в алгоритме, работающем за O (M2), представленного здесь. Однако реализация этой идеи будет несколько другой, что даст нам линейную сложность отосительно числа рёбер.

Рассмотрим такую рекурсивную функцию:

procedure FindEulerPath (V)
1. перебрать все рёбра, выходящие из вершины V;
каждое такое ребро удаляем из графа, и
вызываем FindEulerPath из второго конца этого ребра;
2. добавляем вершину V в ответ.

Несмотря на кажущуюся на простоту, этот алгоритм выполняет все требуемые действия: находит все циклы, объединяя их в один эйлеров цикл. Сложность алгоритма, очевидно, является линейной относительно числа рёбер.

Далее, этот же алгоритм мы можем записать в нерекурсивном варианте:

stack St;
в St кладём любую вершину (стартовая вершина);
пока St не пустой
пусть V - значение на вершине St;
если степень(V) = 0, то
добавляем V к ответу;
снимаем V с вершины St;
иначе
находим любое ребро, выходящее из V;
удаляем его из графа;
второй конец этого ребра кладём в St;

Несложно проверить эквивалентность этих двух форм алгоритма. Однако вторая форма, очевидно, быстрее работает и пишется быстрее.

Итак, реализация всего алгоритма:

(ищет эйлеров цикл или путь в графе, или выводит -1, если его не существует)

typedef vector < vector<int> > graph;


bool connected (const graph & g, const vector<int> & degree, int n)
{
int first;
for (first=0; first<n; ++first)
if (degree[first])
break;
if (first == n)
return false;

vector<char> used (n);
vector<int> q (n);
int h=0, t=0;
q[t++] = first;
used[first] = true;
while (h < t)
{
int v = q[h++];
for (int i=0; i<n; ++i)
if (g[v][i] && !used[i])
{
used[i] = true;
q[t++] = i;
}
}

for (int i=0; i<n; ++i)
if (!used[i] && degree[i] > 0)
return false;
return true;
}


void find_euler_cycle (graph&g, vector<int>&degree, int n, vector<int>&result)
{
stack<int> st;
st.push (0);
while (!st.empty())
{
int v = st.top();
if (degree[v] == 0)
{
st.pop();
result.push_back (v);
}
else
{
for (int i=0; i<n; ++i)
if (g[v][i])
{
--g[v][i], --g[i][v];
--degree[v], --degree[i];
st.push (i);
break;
}
}
}
}


int main()
{
int n;
graph g (n, vector<int> (n));
vector<int> degree (n);

... чтение графа ...

int odd_count = 0;
for (int i=0; i<n; ++i)
if (degree[i] % 2 == 1)
++odd_count;

if (!connected (g, degree, n) || odd_count > 2)
cout << -1;
else
{

int im_v1 = -1, im_v2 = -1;
if (odd_count)
{
for (int i=0; i<n; ++i)
if (degree[i] % 2 == 1)
if (im_v1 == -1)
im_v1 = i;
else
im_v2 = i;
++g[im_v1][im_v2];
++g[im_v2][im_v1];
++degree[im_v1];
++degree[im_v2];
}

vector<int> result;
find_euler_cycle (g, degree, n, result);

if (odd_count)
for (size_t i=1; i<result.size(); ++i)
if (result[i-1] == im_v1 && result[i] == im_v2 ||
result[i-1] == im_v2 && result[i] == im_v1)
{
vector<int> new_res;
copy (result.begin()+i, result.end()-1, back_inserter (new_res));
copy (result.begin(), result.begin()+i, back_inserter (new_res));
result.swap (new_res);
break;
}

cout << result.size();
for (size_t i=0; i<result.size(); ++i)
cout << result[i]+1;

}

}

Программа сначала проверяет, существует ли эйлеров путь. Для этого граф проверяется на связность и количество вершин нечётной степени. Далее, если имеется две вершины нечётной степени, то в графе не существует эйлерова цикла. Для обработки этого, особого, случая просто добавим недостающее ребро, найдём эйлеров цикл и затем удалим из ответа несуществуещее ребро. Затем описанным выше алгоритмом ищется эйлеров цикл.

P.S.:Нашел во второй половине Интернета . Взято с: http://maximal.hocomua.ru/euler_path_linear.htm

[Buffalo]

Напишу спустя год. Интересует это программа, но есть проблемы с векторами. Подскажите люди как осуществить здесь ввод, лучше сразу пример ввода, а то понять не могу =/

[Taichi]

Здравствуйте! А ни у кого нет решения данной задачи на языке Lisp? Ввод графа может быть и иным