0 / 0 / 0
Регистрация: 02.06.2020
Сообщений: 15
1

Эйлеров путь

08.06.2020, 21:27. Показов 687. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Если не трудно помогите с заданием:
по заданной матрице смежности построить эйлеров путь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.06.2020, 21:27
Ответы с готовыми решениями:

Эйлеров путь
Я примерно написал програму, но мой вариант работает долго - 28(иногда меньше, иногда больше)...

Эйлеров путь. Не проходит по времени
Доброго времени суток! Хочу обратиться за помощью. Решаю сейчас задачу, и тестирование не...

Эйлеров цикл
Есть программа: def euler_circuit(G): EP= # Эйлеров цикл - массив вершин. ...

Найти эйлерову цепь или эйлеров цикл в графе
Найти эйлерову цепь или эйлеров цикл в графе

3
0 / 0 / 0
Регистрация: 02.06.2020
Сообщений: 15
09.06.2020, 22:22  [ТС] 2
Я так понимаю, с графами здесь туго
0
75 / 48 / 28
Регистрация: 07.01.2019
Сообщений: 168
09.06.2020, 22:41 3
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
77
78
79
80
81
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
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)
        cout << "-1";
    else
        for (size_t i=0; i<res.size(); ++i)
            cout << res[i]+1 << " ";
 
}
0
0 / 0 / 0
Регистрация: 02.06.2020
Сообщений: 15
10.06.2020, 06:03  [ТС] 4
Спасибо, но вектора мы ещё не проходили
0
10.06.2020, 06:03
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.06.2020, 06:03
Помогаю со студенческими работами здесь

Clojure Эйлеров путь на графах
Здравствуйте! Напишите, пожалуйста, программу, определяющую эйлеровый эйлеров путь,...

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

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

Эйлеров интеграл
Решаю Ейлеревые интегралы. Уже во втором примере подряд вылезает постоянно логарифм. Делаю куча...

Эйлеров интеграл
\int_{0}^{a} x^2 * \sqrt{a^2-x^2} dx C Помощью эйлеровых интегралов вычислить.

Гамильтонов, но не Эйлеров
Приведите, пожалуйста пример эйлерового графа, который не является гамильтоновым.


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru