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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.81
k_a_t_y
10 / 10 / 1
Регистрация: 01.02.2011
Сообщений: 100
#1

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

29.07.2011, 16:34. Просмотров 2094. Ответов 5
Метки нет (Все метки)

Всем доброго времени суток! Помогите пожалуйста или подскажите как сделать следующее. Дали задание по дискретной математике построить эйлерову цепь в графе (нужно реализовать все программе, но вот не знаю с чего начать). Задание следующее:
Построить эйлерову цепь в графе.
Изменить алгоритм построения эйлерова цикла так, чтобы можно было использовать его для построения эйлеровой цепи в графе.


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

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

Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе - C++
Блин я уже так задолбался с этим заданием может кто нибудь поможет: Построить алгоритм поиска кратчайшего пути между двумя...

Цепь Маркова - C++
Собственно, стоит ли на неё обращать внимание? Глава из "Практики Кернигана" довольно обширная.

Цепь Маркова - C++
Мне надо написать программу, которая будет имитировать работу цепи Маркова. Есть ли готовые алгоритмы? В заранее благодарен.

Цепь из двух резисторов - C++
Написать программу вычисления сопротивления электрической цепи, состоящей из двух резисторов. Ре-зисторы могут быть соединены...

Составить из резисторов цепь соединения - C++
Помогите с задачкой пожалуйста с написание програмгного кода Дано N резисторов различных номиналов. Необходимо выбрать несколько...

Запрограммировать простейшую цепь генератора сердца - C++
Доброго времени суток! Помогите, пожалуйста! Не пойму, как можно запрограммировать простейшую цепь генератора сердца rlc. Выводы...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
co6ak
29.07.2011, 16:40
  #2

Не по теме:

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

Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
31.07.2011, 16:58     Построить эйлерову цепь в графе. #3
k_a_t_y, здесь есть код
k_a_t_y
10 / 10 / 1
Регистрация: 01.02.2011
Сообщений: 100
31.07.2011, 18:12  [ТС]     Построить эйлерову цепь в графе. #4
Помогите исправить код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
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
399 / 310 / 27
Регистрация: 17.03.2010
Сообщений: 1,120
31.07.2011, 21:10     Построить эйлерову цепь в графе. #5
А что в нем неверно? Т.е. что исправлять? Мало кто возьмется искать, то не знаю что...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.08.2011, 06:33     Построить эйлерову цепь в графе.
Еще ссылки по теме:

Расстояние на графе - C++
Подскажите пожалуйста, с помощью какого алгоритма можно найти расстояние от заданной вершины графа до всех остальных вершин. Спасибо!

К-ый путь в графе(ДП) - C++
Здраствуйте! Прошу Вас помоч с задачной на ДП, думаю над ней достаточно долго, но ничего в голову путного не приходит. Вот условие: ...

Поиск на графе - C++
Доброго времени суток. Мне не совсем понятна реализация в коде поиска на графе в высоту и ширину. Т.к. в книге они описаны не совсем...

Пути на графе - C++
Здравствуйте, помогите пожалуйста придумать алгоритм поиска путей на орентированом графе. Пример: 0 8 7 2 0 0 0 3 0 8 0 8 0 0 0...

Поиск ободов в графе - C++
К сожалению не получается решить эту задачу на Си. Вот исходный текст задачи: &quot;Найти в графе все подграфы, которые являются ободами&quot;. ...

минимальные расстояния на графе - C++
Здравствуйте, уважаемые программисты. Задача такова: Задано N домов и M дорог. Дома пронумерованы от 1 до N. Каждая дорога...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
leoned
30 / 30 / 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     Построить эйлерову цепь в графе.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru