Форум программистов, компьютерный форум CyberForum.ru

Построить эйлерову цепь в графе. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.81
k_a_t_y
 Аватар для k_a_t_y
10 / 10 / 1
Регистрация: 01.02.2011
Сообщений: 99
29.07.2011, 16:34     Построить эйлерову цепь в графе. #1
Всем доброго времени суток! Помогите пожалуйста или подскажите как сделать следующее. Дали задание по дискретной математике построить эйлерову цепь в графе (нужно реализовать все программе, но вот не знаю с чего начать). Задание следующее:
Построить эйлерову цепь в графе.
Изменить алгоритм построения эйлерова цикла так, чтобы можно было использовать его для построения эйлеровой цепи в графе.


На всякий случай прилагаю небольшую теорию по данному вопросу.

ЗА РАНЕЕ ОГРОМНОЕ СПАСИБО! Жду ваших откликов.
Вложения
Тип файла: rar Построить эйлерову цепь в графе.rar (17.9 Кб, 68 просмотров)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.07.2011, 16:34     Построить эйлерову цепь в графе.
Посмотрите здесь:

C++ Цепь Маркова
Поиск на графе C++
Составить из резисторов цепь соединения C++
C++ Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе
C++ Цепь из двух резисторов
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
co6ak
29.07.2011, 16:40
  #2

Не по теме:

кто ж вас учит писать заранее раздельно... ппц

Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
31.07.2011, 16:58     Построить эйлерову цепь в графе. #3
k_a_t_y, здесь есть код
k_a_t_y
 Аватар для k_a_t_y
10 / 10 / 1
Регистрация: 01.02.2011
Сообщений: 99
31.07.2011, 18:12  [ТС]     Построить эйлерову цепь в графе. #4
Помогите исправить код:
int main() {

int n;
vector <vector<int> > g (n, vector<int> (n));
// ... чтение графа в матрицу смежности ...

vector<int> deg (n);
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
deg[i] += g[i][j];

int first = 0;
while (!deg[first]) ++first;

int v1 = -1, v2 = -1;
bool bad = false;
for (int i=0; i<n; ++i)
if (deg[i] & 1)
if (v1 == -1)
v1 = i;
else if (v2 == -1)
v2 = i;
else
bad = true;

if (v1 != -1)
++g[v1][v2], ++g[v2][v1];

stack<int> st;
st.push (first);
vector<int> res;
while (!st.empty())
{
int v = st.top();
int i;
for (i=0; i<n; ++i)
if (g[v][i])
break;
if (i == n)
{
res.push_back (v);
st.pop();
}
else
{
--g[v][i];
--g[i][v];
st.push (i);
}
}

if (v1 != -1)
for (size_t i=0; i+1<res.size(); ++i)
if (res[i] == v1 && res[i+1] == v2 || res[i] == v2 && res[i+1] == v1)
{
vector<int> res2;
for (size_t j=i+1; j<res.size(); ++j)
res2.push_back (res[j]);
for (size_t j=1; j<=i; ++j)
res2.push_back (res[j]);
res = res2;
break;
}

for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
if (g[i][j])
bad = true;

if (bad)
puts ("-1");
else
for (size_t i=0; i<res.size(); ++i)
printf ("%d ", res[i]+1);

}
NIch
 Аватар для NIch
399 / 310 / 27
Регистрация: 17.03.2010
Сообщений: 1,120
31.07.2011, 21:10     Построить эйлерову цепь в графе. #5
А что в нем неверно? Т.е. что исправлять? Мало кто возьмется искать, то не знаю что...
leoned
 Аватар для leoned
29 / 29 / 1
Регистрация: 30.06.2011
Сообщений: 467
01.08.2011, 06:33     Построить эйлерову цепь в графе. #6
Цитата Сообщение от k_a_t_y Посмотреть сообщение
Помогите исправить код:
k_a_t_yИспользуйте теги форматирования кода!Так гораздо удобней читать и говорить в какой строке ошибка.
Yandex
Объявления
01.08.2011, 06:33     Построить эйлерову цепь в графе.
Ответ Создать тему
Опции темы

Текущее время: 11:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru