Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
 
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 267
#1

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

26.08.2016, 18:20. Просмотров 624. Ответов 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":
Кликните здесь для просмотра всего текста
Код
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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.08.2016, 18:20
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Отслеживание узла родителя в Depth First Search (C++):

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

Шаблоны или ... (Maximum option context replay depth exceeded) - C++
Код отсюдВа http://habrahabr.ru/post/38622/ //------------------------------------------------------------ template &lt;unsigned long t&gt;...

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

Как в TreeView колучить Index узла родителя? - Базы данных
Как в TreeView колучить Index узла родителя?

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

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

28
Новичок
Модератор
1261 / 809 / 182
Регистрация: 17.07.2012
Сообщений: 4,289
Записей в блоге: 1
Завершенные тесты: 2
26.08.2016, 19:05 #2
Цитата Сообщение от Leonman Посмотреть сообщение
stack<int> S;
Можно хранить pair<int, int> и тогда первый элемент пары это вершина из которой мы пришли, а второй элемент куда мы пришли.
0
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 267
27.08.2016, 17:00  [ТС] #3
Новичок, не, вопрос не в том, где хранить. Вопрос в том, в какой момент и при каком условие записывать родителя?

Добавлено через 21 час 52 минуты
Ну же, гуру-программисты, кто-то же наверняка реализовывал такое хоть раз в жизни
0
Ромаха
303 / 85 / 15
Регистрация: 16.12.2012
Сообщений: 439
Записей в блоге: 1
27.08.2016, 23:07 #4
Цитата Сообщение от Leonman Посмотреть сообщение
Вопрос в том, в какой момент и при каком условие записывать родителя?
О мой Бог.

C++
1
2
3
4
5
6
void dfs(int v, int p) {
    if (used[v]) return;
    used[v] = true;
    for (int i = 0; i < g[v].size(); i++) 
        dfs(g[v][i], v);
}
Добавлено через 23 минуты
А так.. У вас bfs написан.
0
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 267
27.08.2016, 23:22  [ТС] #5
Ромаха, Вы не правы. BFS использует очередь, и осуществляет проверку на то, был ли просмотрен узел перед тем, как положить его в очередь, в то время, как DFS использует стэк и проверяет узел после того, как он был вытащен из стека.

Wiki: The non-recursive implementation is similar to breadth-first search but differs from it in two ways: it uses a stack instead of a queue, and it delays checking whether a vertex has been discovered until the vertex is popped from the stack rather than making this check before pushing the vertex.
0
Ромаха
303 / 85 / 15
Регистрация: 16.12.2012
Сообщений: 439
Записей в блоге: 1
27.08.2016, 23:31 #6
Leonman, действительно. Пардон. Я проглядел. Привык к каноничной записи dfs в рекурсивной форме.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
stack<pair<int, int > > S;
while(!S.empty())
    {
        int current = S.top().second; S.pop();
        
        if(!seen[current])
        {
            seen[current] = true;
            
                        for(const auto &child : graph[current])
                S.push(make_pair(current, child);
        }
    }
0
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 267
27.08.2016, 23:41  [ТС] #7
Ромаха, а как же я потом смогу вывести родителей, если при выхоже из while стек будет пуст, соответственно вся инфа о родителях пропадёт.
0
Ромаха
303 / 85 / 15
Регистрация: 16.12.2012
Сообщений: 439
Записей в блоге: 1
28.08.2016, 01:00 #8
Заведите массив предков. И если данная вершина не посещалась - записываем туда предка.
0
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 267
28.08.2016, 13:27  [ТС] #9
Ромаха, и снова нет. Нет гарантий, что прийдя в вершину впервые, родитель, от которого мы пришли и есть конечный правильный ответ.
0
Новичок
Модератор
1261 / 809 / 182
Регистрация: 17.07.2012
Сообщений: 4,289
Записей в блоге: 1
Завершенные тесты: 2
28.08.2016, 16:37 #10
Цитата Сообщение от Leonman Посмотреть сообщение
Нет гарантий, что прийдя в вершину впервые, родитель, от которого мы пришли и есть конечный правильный ответ.
Почему?
0
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 267
28.08.2016, 17:13  [ТС] #11
Новичок, Потому что, как и следует из назнания Depth First Search, алгоритм идет максимально вглубь.
Предлогаю рассмотреть вот такую гифку:
Отслеживание узла родителя в Depth First Search

Как мы видем, в вершину 'D' можно прийти из вершины 'A', однако родитель вершины 'D' будет не 'A', а 'E', т.к. алгоритм ищет вглубь.
Тоже самое с вершиной 'C', в нее тоже можно прийти из вершины 'A' и казалось бы, что 'A' - есть ее родитель, но опять же, алгоритм работает вглубь, соответственно родитель вершины 'С' - вершина 'D'.

Надеюсь я смог объяснить.
0
Новичок
Модератор
1261 / 809 / 182
Регистрация: 17.07.2012
Сообщений: 4,289
Записей в блоге: 1
Завершенные тесты: 2
28.08.2016, 17:33 #12
Цитата Сообщение от Leonman Посмотреть сообщение
Как мы видем, в вершину 'D' можно прийти из вершины 'A'
Так все ж зависит только от того какая первая вершина будет после 'A'.
Если массив вершин смежных с 'A' будет такой 'D', 'C', 'B' то мы сразу из 'A' в 'D' попадем.
Цитата Сообщение от Leonman Посмотреть сообщение
с возможностью получения родителя (т.е. узла, из которого мы пришли данный узел)
Граф по разному обойти можно как-бы, и нельзя однозначно определить родителя.
Можно так пойти
'A' - 'D' - 'C' - 'F' - 'G' - 'E' - 'B'
можно так
'A' - 'B' - 'E' - 'D' - 'G' - 'F' - 'C'
0
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 267
28.08.2016, 17:46  [ТС] #13
Новичок, Хм. Да, вы правы. Однако, задача поставленна и требует решения.

Я прикреплю полную формулировку задачи в pdf, возможно я что-то упустил:
Depth First Search - CodeAbbey.pdf

Если не затруднит конечно.
0
Новичок
Модератор
1261 / 809 / 182
Регистрация: 17.07.2012
Сообщений: 4,289
Записей в блоге: 1
Завершенные тесты: 2
28.08.2016, 17:55 #14
Цитата Сообщение от Leonman Посмотреть сообщение
Новичок, Хм. Да, вы правы.
Ура, наконец-то!
Цитата Сообщение от Leonman Посмотреть сообщение
Я прикреплю полную формулировку задачи в pdf, возможно я что-то упустил:
С этого надо было начинать.
В задании сказано
To avoid ambiguosity please take care that neighbors should be tried in order of increasing their ids
Как я понимаю это значит что если из одной вершины мы можем пойти в несколько, мы должны идти в ту у которой индекс меньше и тогда не будет неоднозначности. Потому массив смежных массив после ввода надо отсортировать.
0
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 267
29.08.2016, 13:37  [ТС] #15
Новичок, Это на самом деле было уже сделано. Почему - то в исходном коде я этого не указал
C++
1
2
for(auto &elem : graph)
    sort(elem.second.begin(), elem.second.end());
elem.second - это вектор, в котором хранятся индексы вершин, смежных с вершиной elem.first

Добавлено через 19 часов 19 минут
Новичок, ну что, есть у вас идеи?
0
29.08.2016, 13:37
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.08.2016, 13:37
Привет! Вот еще темы с ответами:

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

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

Как получить значение одного узла по значению другого узла? - LINQ
Всем благополучия. Помогите разобраться с вроде несложной ситуацией, плз. Есть простенький XML файл: &lt;Name&gt;Тип документа&lt;/Name&gt;...

Выбор узла XML по значению другого узла - C#
Работаю с xml. Его структура такова : &lt;data&gt; &lt;item&gt; &lt;id&gt;182&lt;/id&gt; &lt;art_url/&gt; &lt;artist&gt;Kevin Griffiths&lt;/artist&gt; ...


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

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

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