Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
26.08.2016, 18:20     Отслеживание узла родителя в Depth First Search #1
Всем привет!

И так. Мне надо реализовать алгоритм 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 все было как-то понятнее
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.08.2016, 18:20     Отслеживание узла родителя в Depth First Search
Посмотрите здесь:

C++ Вызов из потомка конструктор родителя
Шаблоны или ... (Maximum option context replay depth exceeded) C++
C++ Узнать id родителя процесса
Инициализация родителя C++
Поиск Breadth-First Search C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Новичок
Модератор
 Аватар для Новичок
1137 / 708 / 148
Регистрация: 17.07.2012
Сообщений: 4,039
Записей в блоге: 1
Завершенные тесты: 2
26.08.2016, 19:05     Отслеживание узла родителя в Depth First Search #2
Цитата Сообщение от Leonman Посмотреть сообщение
stack<int> S;
Можно хранить pair<int, int> и тогда первый элемент пары это вершина из которой мы пришли, а второй элемент куда мы пришли.
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
27.08.2016, 17:00  [ТС]     Отслеживание узла родителя в Depth First Search #3
Новичок, не, вопрос не в том, где хранить. Вопрос в том, в какой момент и при каком условие записывать родителя?

Добавлено через 21 час 52 минуты
Ну же, гуру-программисты, кто-то же наверняка реализовывал такое хоть раз в жизни
Ромаха
 Аватар для Ромаха
263 / 57 / 10
Регистрация: 16.12.2012
Сообщений: 363
Записей в блоге: 1
27.08.2016, 23:07     Отслеживание узла родителя в Depth First Search #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 написан.
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
27.08.2016, 23:22  [ТС]     Отслеживание узла родителя в Depth First Search #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.
Ромаха
 Аватар для Ромаха
263 / 57 / 10
Регистрация: 16.12.2012
Сообщений: 363
Записей в блоге: 1
27.08.2016, 23:31     Отслеживание узла родителя в Depth First Search #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);
        }
    }
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
27.08.2016, 23:41  [ТС]     Отслеживание узла родителя в Depth First Search #7
Ромаха, а как же я потом смогу вывести родителей, если при выхоже из while стек будет пуст, соответственно вся инфа о родителях пропадёт.
Ромаха
 Аватар для Ромаха
263 / 57 / 10
Регистрация: 16.12.2012
Сообщений: 363
Записей в блоге: 1
28.08.2016, 01:00     Отслеживание узла родителя в Depth First Search #8
Заведите массив предков. И если данная вершина не посещалась - записываем туда предка.
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
28.08.2016, 13:27  [ТС]     Отслеживание узла родителя в Depth First Search #9
Ромаха, и снова нет. Нет гарантий, что прийдя в вершину впервые, родитель, от которого мы пришли и есть конечный правильный ответ.
Новичок
Модератор
 Аватар для Новичок
1137 / 708 / 148
Регистрация: 17.07.2012
Сообщений: 4,039
Записей в блоге: 1
Завершенные тесты: 2
28.08.2016, 16:37     Отслеживание узла родителя в Depth First Search #10
Цитата Сообщение от Leonman Посмотреть сообщение
Нет гарантий, что прийдя в вершину впервые, родитель, от которого мы пришли и есть конечный правильный ответ.
Почему?
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
28.08.2016, 17:13  [ТС]     Отслеживание узла родителя в Depth First Search #11
Новичок, Потому что, как и следует из назнания Depth First Search, алгоритм идет максимально вглубь.
Предлогаю рассмотреть вот такую гифку:
Отслеживание узла родителя в Depth First Search

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

Надеюсь я смог объяснить.
Новичок
Модератор
 Аватар для Новичок
1137 / 708 / 148
Регистрация: 17.07.2012
Сообщений: 4,039
Записей в блоге: 1
Завершенные тесты: 2
28.08.2016, 17:33     Отслеживание узла родителя в Depth First Search #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'
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
28.08.2016, 17:46  [ТС]     Отслеживание узла родителя в Depth First Search #13
Новичок, Хм. Да, вы правы. Однако, задача поставленна и требует решения.

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

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

Добавлено через 19 часов 19 минут
Новичок, ну что, есть у вас идеи?
Avazart
 Аватар для Avazart
6896 / 5136 / 251
Регистрация: 10.12.2010
Сообщений: 22,568
Записей в блоге: 17
29.08.2016, 13:53     Отслеживание узла родителя в Depth First Search #16
Leonman, Может пригодится: Как обратится к обьекту класса, являющегося наследником абстрактного класса
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
30.08.2016, 13:58  [ТС]     Отслеживание узла родителя в Depth First Search #17
Avazart, Может вы понимаете, что не так?
Avazart
 Аватар для Avazart
6896 / 5136 / 251
Регистрация: 10.12.2010
Сообщений: 22,568
Записей в блоге: 17
30.08.2016, 14:52     Отслеживание узла родителя в Depth First Search #18
Цитата Сообщение от Leonman Посмотреть сообщение
Новичок, Хм. Да, вы правы. Однако, задача поставленна и требует решения.
Требует пенделя тому кто ее поставил.
Ибо не уточнено что понимается под родителем
Нет родителей, есть лишь смежные вершины https://ru.wikipedia.org/wiki/%D0%93...E%D0%B2#.D0.A0
С исходящими или входящими ребрами (опять в зависимости от типа графа)

Однако есть понятие предка и алгоритм поиска наименьшего общего предка(который как раз использует поиск в глубину).
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
31.08.2016, 01:04  [ТС]     Отслеживание узла родителя в Depth First Search #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, программа находит всех родителей правильно.

Совпадение или в правильном направлении пошел и надо поразмыслить над этой идеей?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.09.2016, 14:28     Отслеживание узла родителя в Depth First Search
Еще ссылки по теме:

Binary Search C++
C++ Sentinel Linear Search
C++ Вызов метода родителя

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

Или воспользуйтесь поиском по форуму:
Ромаха
 Аватар для Ромаха
263 / 57 / 10
Регистрация: 16.12.2012
Сообщений: 363
Записей в блоге: 1
02.09.2016, 14:28     Отслеживание узла родителя в Depth First Search #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;
}
Yandex
Объявления
02.09.2016, 14:28     Отслеживание узла родителя в Depth First Search
Ответ Создать тему
Опции темы

Текущее время: 22:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru