Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.75/8: Рейтинг темы: голосов - 8, средняя оценка - 4.75
 Аватар для Leonman
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274

Отслеживание узла родителя в Depth First Search

26.08.2016, 18:20. Показов 2532. Ответов 28
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Всем привет!

И так. Мне надо реализовать алгоритм Depth First Search, с возможностью получения родителя (т.е. узла, из которого мы пришли данный узел).

Вот реализация Depth First Search:
Кликните здесь для просмотра всего текста
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
#include <iostream>
using std::cout;
#include <map>
using std::map;
#include <fstream>
using std::ifstream;
#include <vector>
using std::vector;
#include <utility>
using std::pair;
#include <stack>
using std::stack;
 
typedef map<int, vector<int>> Graph;
typedef map<int, bool> seen_map;
 
Graph genarate_graph(ifstream &fin, const int &amount_of_edges)
{
    int node_1{}, node_2{};
    Graph graph;
    
    for(int i = 0; i < amount_of_edges; i++)
    {
        fin >> node_1 >> node_2;
        graph[node_1].push_back(node_2);
        graph[node_2].push_back(node_1);
    }
    
    return graph;
}
 
void DFS(Graph &graph)
{
    stack<int> S;
    seen_map seen;
    
    for(size_t i = 0; i < graph.size(); i++)
        seen[i] = false;
    
    S.push(0);
    
    while(!S.empty())
    {
        int current = S.top(); S.pop();
        
        if(!seen[current])
        {
            seen[current] = true;
            
                        for(const auto &child : graph[current])
                S.push(child);
        }
    }
}
 
int main()
{
    ifstream fin("data0.txt");
    int amount_of_nodes{}, amount_of_edges{};
    fin >> amount_of_nodes >> amount_of_edges;
    Graph graph = genarate_graph(fin, amount_of_edges);
    
    DFS(graph);
    
    return 0;
}


Содержимое файла "data0.txt":
Кликните здесь для просмотра всего текста
Code
1
2
3
4
5
6
7
8
9
10
11
7 10
0 1
2 0
0 3
1 4
4 3
2 3
5 2
6 3
4 6
6 5


Первое значение первой строки (7) - кол-во узлов
Второе значение первой строки (10) - кол-во ребер
Последующие 10 строк содержат id узлов, между которыми есть ребро.

На выходе надо получить массив, a[i] должен содержать индекс узла, из которого мы пришли в i-ый узел. Для начального узла (т.е. узла под индексом 0), a[0] должен содержать -1, так как с него мы начинаем.

Для содержимого файла data0.txt ответ должен быть:
-1 0 3 4 1 2 5
Собственно, прошу помочь мне понять, где надо фиксировать родителя.

P.S. В Breadth First Search все было как-то понятнее
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
26.08.2016, 18:20
Ответы с готовыми решениями:

DFS Depth First Search
DFS Depth First Search кто нибуть сталкивался с таким? везде показывают только картинки в ютубах в гуглах. Может кто нить...

Как в TreeView колучить Index узла родителя?
Как в TreeView колучить Index узла родителя?

Вывод поста, который содержит id категории, её родителя, родителя родителя
Есть 2 таблицы, первая - категории ( category_id, parent_id и т.д), вторая - посты (post_id, category_id) В общем, в...

28
 Аватар для Leonman
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274
02.09.2016, 18:22  [ТС]
Студворк — интернет-сервис помощи студентам
Ромаха, К сожалению сново не то.
0
 Аватар для Новичок
1682 / 1098 / 489
Регистрация: 17.07.2012
Сообщений: 5,361
02.09.2016, 18:48
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
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector < vector <int> > a;
vector <int> p;
 
const int not_used = -2;
 
void dfs(const int& u, const int& parent) {
    if (p[u] != not_used) return;
    p[u] = parent;
    for (auto& i: a[u])
        dfs(i, u);
}
 
int main() {
    int n, m;
    cin >> n >> m;
    a.resize(n);
    p.assign(n, not_used);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for (auto& i: a)
        sort(i.begin(), i.end());
    dfs(0, -1);
    for (auto& i: p)
        cout << i << " ";
}
1
 Аватар для Leonman
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274
02.09.2016, 19:53  [ТС]
Новичок, А вот это другое дело. Огромное вам спасибо!
0
354 / 135 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
04.09.2016, 01:16
Цитата Сообщение от Leonman Посмотреть сообщение
Ромаха, К сожалению сново не то.
От чего же?
0
 Аватар для Leonman
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274
04.09.2016, 01:50  [ТС]
Ромаха, Предыдущий вариант не работал правильно. А последний работает.
0
 Аватар для Новичок
1682 / 1098 / 489
Регистрация: 17.07.2012
Сообщений: 5,361
04.09.2016, 02:06
Цитата Сообщение от Ромаха Посмотреть сообщение
От чего же?
Глянь тесты в условии задачи и ответы на них.
0
354 / 135 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
04.09.2016, 12:56
Ничего не понимаю. В условии нет слова про родителей.
Давайте посмотрим на гифку. Какой порядок обхода?
Code
1
2
3
ABEDCFG
0143256
-032145
Косяк или в условии или в тестах. Ну или мне нужно проспаться
0
 Аватар для Leonman
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274
04.09.2016, 13:18  [ТС]
Ромаха, Для узла 'D' родитель не 'C', а 'E'. Для узла 'F' родитель не 'E', 'C'
Поэтому не -1 0 3 2 1 4 5 (как в вашем ответе), а -1 0 3 4 1 2 5
0
354 / 135 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
04.09.2016, 15:57
Да. Забавно. Печально. Нужно проспаться. Простите.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
04.09.2016, 15:57

Бинарное дерево подклассов основного класса-узла. Доступ к подклассам по указателю - объекту класса-родителя
Короче, необходимо сделать бинарное дерево, решающее арифметическое выражение, предварительно туда записанное. Есть основной класс...

Как при клике взять ID родителя и скрыть дивы с классом взятого ранее родителя?
Здравствуйте друзья, столкнулся с задачкой для решения которой у меня не хватает опыта JS программировании. Имеется сайт с системой...

Как удалить Piese Search из Google Chrome? Аналогичный Get Search
Аналогичный Get Search.

Пропадает фильтр по дополнительным полям JA K2 Filter and Search Search 1.0.4
Доброго времени суток уважаемые форумчане. Возникла проблема с пропадающим фильтром по дополнительным полям в JA K2 Filter and Search...

New. Google search and search engine spam
Читаем новости из первоисточников: 1. Google search and search engine spam - 1/21/2011 09:00:00 AM Posted by Matt Cutts, Principal...


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

Или воспользуйтесь поиском по форуму:
29
Ответ Создать тему
Новые блоги и статьи
Как установить и настроить Windows 11 без подключения к Интернету и без аккаунта Microsoft
Maks 22.11.2026
Положу сюда, чтобы не искать постоянно. • На экране «Давайте подключим вас к сети» во время установки Windows 11 нажмите комбинацию клавиш Shift+F10, чтобы открыть командную строку. Введите. . .
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru