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

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

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

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

26.08.2016, 18:20. Просмотров 626. Ответов 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
Avazart
Эксперт С++
7247 / 5419 / 297
Регистрация: 10.12.2010
Сообщений: 24,046
Записей в блоге: 17
29.08.2016, 13:53 #16
Leonman, Может пригодится: Как обратится к обьекту класса, являющегося наследником абстрактного класса
0
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 267
30.08.2016, 13:58  [ТС] #17
Avazart, Может вы понимаете, что не так?
0
Avazart
Эксперт С++
7247 / 5419 / 297
Регистрация: 10.12.2010
Сообщений: 24,046
Записей в блоге: 17
30.08.2016, 14:52 #18
Цитата Сообщение от Leonman Посмотреть сообщение
Новичок, Хм. Да, вы правы. Однако, задача поставленна и требует решения.
Требует пенделя тому кто ее поставил.
Ибо не уточнено что понимается под родителем
Нет родителей, есть лишь смежные вершины https://ru.wikipedia.org/wiki/%D0%93...E%D0%B2#.D0.A0
С исходящими или входящими ребрами (опять в зависимости от типа графа)

Однако есть понятие предка и алгоритм поиска наименьшего общего предка(который как раз использует поиск в глубину).
0
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 267
31.08.2016, 01:04  [ТС] #19
Нашел интересную закономерность, если можно так обозначить. Может кому-то будет интересно или, как пища для размышление над проблемой.

Создаем дополнительный stack и пушим в него нашу current вершину (напомню, что вершины представленны ввиде индексов от 0 до graph.size()-1), при условии, что эта вершина (индекс), не был ранее в данном stack`e и, что эта вершина - не последний вершина в графе (т.е. current != graph.size()-1).

А выталкиваем наши запушенные вершины (они и есть родители) тогда, когда было обнаруженно, что current вершина была просмотренна (т.е. seen[current] == true).

В общем, так не очень понятно наверное, вот код (надеюсь понятнее будет):

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
void DFS(Graph &graph)
{
    stack<int> S;
    seen_map seen, seen_parent;
    stack<size_t> next_parent;
    vector<int> parent(graph.size(), -2);
    
    for(size_t i = 0; i < graph.size(); i++)
        seen[i] = false;
    
    for(auto it = graph.begin(); it != graph.end(); ++it)
        sort(it->second.begin(), it->second.end());
    
    S.push(0);
    parent[0] = -1;
    
    while(!S.empty())
    {
        size_t current = S.top(); S.pop();
        
        if(!seen[current])
        {
            seen[current] = true;
            
            //если у вершины current всего одна смежная вершина, 
            //то она и есть родитель
            if(graph[current].size() == 1)
                parent[current] = *graph[current].begin();
            
            for(const auto &child : graph[current])
                S.push(child);
            
            //если current - не последная вершина в графе
            //если current не была ранее в стеке next_parent (костыль detected)
            if(current != graph.size()-1 && 
               seen_parent.find(current) == seen_parent.end()) 
            {   
                //пушим родителя
                next_ parent.push(current); 
                //отмечаем, что такая вершина была запушена в стек, 
                //чтоб в следующий раз такую же веришину не пушить
                seen_parent[current] = true; 
            }
        }
        //если у current еще нет родителя и ее родитель - не она сама
        else if(parent[current] == -2 && current != next_parent.top()) 
        {
            parent[current] = next_parent.top(); //фиксируем родителя для current
            next_parent.pop();
        }
    }
    
    for(const auto &elem : parent)
        cout << elem << " ";
}
Для input'a, который был указал в самом начале темы в файле data0.txt, программа находит всех родителей правильно.

Совпадение или в правильном направлении пошел и надо поразмыслить над этой идеей?
0
Ромаха
303 / 85 / 15
Регистрация: 16.12.2012
Сообщений: 439
Записей в блоге: 1
02.09.2016, 14:28 #20
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
vii v;
vi used, p;
int t = -1;
void dfs(int V) {
    if (used[V] != -1) return;
    used[V] = 1;
    p[V] = t++;
    forn(i, v[V].size()) {
        dfs(v[V][i]);
    }
}
 
int main() {
    int n, m;
    cin >> n >> m;
    v.resize(n);
    p.assign(n, -1);
    used.assign(n, -1);
    
    forn(i, m) {
        int a, b;
        cin >> a >> b;
        v[a].pb(b);
        v[b].pb(a);
    }
    
    forn(i, n) sort(all(v[i]));
    
    dfs(0);
    forn(i, n) cout << p[i] << " ";
    
    return 0;
}
0
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 267
02.09.2016, 18:22  [ТС] #21
Ромаха, К сожалению сново не то.
0
Новичок
Модератор
1261 / 809 / 182
Регистрация: 17.07.2012
Сообщений: 4,292
Записей в блоге: 1
Завершенные тесты: 2
02.09.2016, 18:48 #22
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 / 0
Регистрация: 17.06.2012
Сообщений: 267
02.09.2016, 19:53  [ТС] #23
Новичок, А вот это другое дело. Огромное вам спасибо!
0
Ромаха
303 / 85 / 15
Регистрация: 16.12.2012
Сообщений: 439
Записей в блоге: 1
04.09.2016, 01:16 #24
Цитата Сообщение от Leonman Посмотреть сообщение
Ромаха, К сожалению сново не то.
От чего же?
0
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 267
04.09.2016, 01:50  [ТС] #25
Ромаха, Предыдущий вариант не работал правильно. А последний работает.
0
Новичок
Модератор
1261 / 809 / 182
Регистрация: 17.07.2012
Сообщений: 4,292
Записей в блоге: 1
Завершенные тесты: 2
04.09.2016, 02:06 #26
Цитата Сообщение от Ромаха Посмотреть сообщение
От чего же?
Глянь тесты в условии задачи и ответы на них.
0
Ромаха
303 / 85 / 15
Регистрация: 16.12.2012
Сообщений: 439
Записей в блоге: 1
04.09.2016, 12:56 #27
Ничего не понимаю. В условии нет слова про родителей.
Давайте посмотрим на гифку. Какой порядок обхода?
Код
ABEDCFG
0143256
-032145
Косяк или в условии или в тестах. Ну или мне нужно проспаться
0
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 267
04.09.2016, 13:18  [ТС] #28
Ромаха, Для узла 'D' родитель не 'C', а 'E'. Для узла 'F' родитель не 'E', 'C'
Поэтому не -1 0 3 2 1 4 5 (как в вашем ответе), а -1 0 3 4 1 2 5
0
Ромаха
303 / 85 / 15
Регистрация: 16.12.2012
Сообщений: 439
Записей в блоге: 1
04.09.2016, 15:57 #29
Да. Забавно. Печально. Нужно проспаться. Простите.
0
04.09.2016, 15:57
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.09.2016, 15:57
Привет! Вот еще темы с ответами:

Как удалить 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; ...


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

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

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