С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.96/25: Рейтинг темы: голосов - 25, средняя оценка - 4.96
-8 / 0 / 0
Регистрация: 27.02.2019
Сообщений: 43
1

Паттерн Итератор. Обход графа в глубину

08.11.2019, 10:12. Показов 4518. Ответов 22
Метки c++ (Все метки)

Author24 — интернет-сервис помощи студентам
Имею данный алгоритм обхода графа в глубину. Необходимо реализовать данную задачу с помощью паттерна Итератор и используя цикл foreach.
Почитал об данном итераторе, но никаких идей не появилось.
Прошу дать подсказки или намеки и возможности реализации.
Заранее спасибо
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
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
 
int DFS(vector<vector<int>>&, int&, int&);
 
int main() {
    // Список смежности графа
    vector<vector<int>> G {
        {1, 2, 3},
        //----------------------------------------------
        {0, 4, 5}, {0, 6, 7}, {0, 8, 9},
        //----------------------------------------------
        {1, 10, 11, 12}, {14, 13, 14}, {2, 15}, 
        {2, 16, 17}, {3}, {3, 18},
        //----------------------------------------------
        {4}, {4}, {4, 19, 20}, {5}, {5}, {6, 21, 22, 23},
        {7, 24, 25}, {7, 26, 27}, {9, 28, 29},
        //-----------------------------------------------
        {12}, {12}, {15}, {15}, {15}, {16}, {16}, {17}, 
        {17}, {18}, {18}
        //-----------------------------------------------
    };
 
    int start, finish; // стартовая и конечная вершины
    cout << "Введите стартовую вершину => "; cin >> start;
    cout << "Введите конечную вершину => ";  cin >> finish;
    cout << "Длина /*кратчайшего*/пути из вершины "
         << start
         << "\nв вершину "
         << finish
         << " равна "
         << DFS(G, start, finish)
         << endl;
 
    return 0;
}
 
int DFS(vector<vector<int>> &myG, int &s, int &u) {
    size_t n = myG.size();
    // Массив флагов посещаемости вершин
    vector<bool> used(n, false);
    // Подготовим стек
    stack<int> S;
    // Кладем исходную вершину в стек
    S.push(s);
    used[s] = true;
    // Будем считать длину пути
    vector<int> D(n);
    // Если нужно, запоминаем путь
    // vector<int> P(n);
    // P[start] = -1;
    // см. программу 26.3
    // Пока стек не пуст
    while (!S.empty()) {
        //Посещаем вершину
        size_t v = S.top();
        S.pop();
        // Идем в глубину графа
        auto first = myG[v].begin();
        auto last  = myG[v].end();
        // Осматриваем смежные вершины
        while (first != last) {
            // Если какие-то ещё не посещались
            if (!used[*first]) {
                // Отправляем их в стек
                S.push(*first);
                // и фиксируем их посещение
                used[*first] = true;
                // если нужно запоминать путь, то
                // P[*first] = v;
                // Но мы будем считать длину
                D[*first] = D[v] + 1;
            }
            first++;
        }
    }
    return D[u];
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.11.2019, 10:12
Ответы с готовыми решениями:

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

Обход графа в глубину
Покажите кто-нибудь как работает &quot;обход графа&quot; в графе в консоле А именно вывод глубины...

Обход графа в глубину
Доброго времени суток, братцы! Есть такая задачка - обойти граф в глубину. Сам алгоритм примерно...

Обход графа в глубину
Как сделать обход этого графа в глубину ?

22
-8 / 0 / 0
Регистрация: 27.02.2019
Сообщений: 43
11.11.2019, 16:51  [ТС] 21
Author24 — интернет-сервис помощи студентам
oleg-m1973, 'auto' not allowed in lambda parametr
0
6770 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
11.11.2019, 16:53 22
Цитата Сообщение от paradise19 Посмотреть сообщение
oleg-m1973, 'auto' not allowed in lambda parametr
Сделай [&](int item)
0
-8 / 0 / 0
Регистрация: 27.02.2019
Сообщений: 43
11.11.2019, 16:55  [ТС] 23
oleg-m1973, работает, благодарю за помощь и терпение.
0
11.11.2019, 16:55
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.11.2019, 16:55
Помогаю со студенческими работами здесь

Многопоточный обход графа в глубину
Доброго времени суток. Подскажите многопоточный алгоритм обхода графа в глубину (нужно...

Обход неориентированного графа в глубину
#include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;vector&gt; #include &lt;conio.h&gt; #include &lt;locale.h&gt;...

Обход вершин графа в глубину стеком
Применить стек для обхода вершин графа, заданного с помощью матрицы смежности, в глубину. Есть...

Обход графа в глубину
необходимо разбить неориентированный граф на связные компоненты на вход поступает матрица...


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

Или воспользуйтесь поиском по форуму:
23
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru