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

Хитрый обход дерева в глубину - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,508
28.01.2013, 22:30     Хитрый обход дерева в глубину #1
По условию необходимо обойти дерево так чтобы найти путь max длины не имеющий кратных вершин, приэтом советуют пользоваться алгоритмом с возвратом.

Ну или проще это же условие: Найти max длины путь без циклов и самопересечений.

Граф допустим держу в виде матрицы смежностей:
bool** adj;
int size;

Держать пути которые найдены наверное будет удобно в списке
list<list<int>> traverse;
ну или на чём-то другом объясните пожалуйста, векторе, стеке или ещё чем вам удобно пользваться.

Помогите сформировать алгоритм или в виде кода подсобите.
Код самого графа в виде матрицы смежностей если необходим то вот (комментариев слишком много так как писал когда-то не для себя):
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <iostream>
#include <iomanip>
#include <list>
 
using namespace std;
 
 
//класс представляющий неориентированный граф в виде матрицы смежностей
class AdjMatrix
{
    bool** adj;//матрица смежностей (двухмерная [][] )
    int size;//размер матрицы
    list<list<int>*> traverse;//для обхода графа
public:
 
    //по умолчанию ждём что нам передадут размер матрицы смежностей
    AdjMatrix(int s)
    {
        //сохраняем размер матрицы (она будет квадратной)
        size = s;
 
        //выделяем память под массив
        adj = new bool*[s];
 
        //выделяем память под подмассивы
        for(int i = 0;i<size;i++)
            adj[i] = new bool[size];
 
        //обнуляем значения подмассивов
        for(int i=0; i<size; i++)
            for(int j=0 ;j<size; j++)
                adj[i][j]=false;
    }
 
    //вывод на экран матрици смежностей (красиво и с отступами :) )
    void print()
    {
        //проходимся по всей матрице смежностей
        for(int i = 0; i<size; i++)
        {
            //выводим номер вершины
            cout<<setw(3)<<i+1<<":";
 
                //и список всех связанных с ней вершин
                for(int j = 0; j<size;j++)
                    if(adj[i][j])
                        cout<<setw(3)<<j+1;
                    else
                        cout<<"   ";
            cout<<endl;
        }
    }
 
    //добавить новую связь двух вершин
    bool addLink(int x, int y)
    {
        //если мы не выходим за границы + такой связи ещё не было
        if((x<=size && y<=size) && !adj[x-1][y-1] )
        {
            //добавляем связи (и прямую и обратную так как не ориентированный граф)
            adj[x-1][y-1] = true;
            adj[y-1][x-1] = true;
 
            return true;
        }
        //иначе вернём false чтобы пользователь мог проверить ответ
        //и понять удалось ли добавление связи
        else
            return false;
    }
 
    //удаление связи между двумя вершинами
    bool destroyLink(int x, int y)
    {
        //если мы не выходим за границы + такая связь есть (есть что удалять хоть)
        if((x<=size && y<=size) && adj[x-1][y-1])
        {
            //удалить связь
            adj[x-1][y-1] = false;
            adj[y-1][x-1] = false;
 
            return true;
        }
        else
            return false;
    }
 
    //узнать размер матрицы смежностей (вдруг пользователь забыл что указывал)
    int getSize()
    {
        return size;
    }
 
    void traverseFor(int n)
    {
 
    }
 
    //деструктор для освобождения памяти в конце
    ~AdjMatrix()
    {
        //сначала удаляем подмассивы
        for(int i=0;i<size;i++)
            delete [] adj[i];
 
        //а в конце и сам массив
        delete [] adj;
    }
};
 
int main()
{
 
    //размер матрицы смежностей
    int size = 10;
 
    //создаём нашу матрицу смежностей
    AdjMatrix adj(size);
 
    //добавляем пачку связей
    adj.addLink(1,1);
    adj.addLink(1,2);
    adj.addLink(1,3);
    adj.addLink(1,4);
    adj.addLink(1,5);
    adj.addLink(1,6);
    adj.addLink(1,7);
    adj.addLink(1,8);
    adj.addLink(1,9);
    adj.addLink(1,10);
 
    //демонстрируем результат
    adj.print();
 
    system("PAUSE");
    return 0;
}
Ну или вот здесь можно запустить и посмотреть сам граф:
http://liveworkspace.org/code/3uwW0C$3

В текущем графе получается подходящие пути все длиной = 3. Такие пути: 2->1->3 ; 2->1->4; ... 9->1->8

Добавлено через 5 часов 20 минут
Есть ли хоть какие-то идеи?
Мне друг подкинул очень абстракционную идею алгоритма

обход(длина, посещённые вершины) {
foreach (непосещённые вершины) {
длина = max(обход(длина + 1), длина)
}
return длина
}

но развить её у нас не получилось Помогите кто советом пожалуйста.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.01.2013, 22:30     Хитрый обход дерева в глубину
Посмотрите здесь:

Обход дерева) C++
Обход дерева C++
Обход графа в глубину C++
обход дерева C++
C++ Организовать обход в глубину
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dmitriy_M
1294 / 1175 / 104
Регистрация: 20.03.2009
Сообщений: 4,208
Записей в блоге: 11
28.01.2013, 23:18     Хитрый обход дерева в глубину #2
Цитата Сообщение от Gepar Посмотреть сообщение
Ну или проще это же условие: Найти max длины путь без циклов и самопересечений.
По определению, дерево не имеет циклов.
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,508
29.01.2013, 05:34  [ТС]     Хитрый обход дерева в глубину #3
Dmitriy_M, я вначале написал слово дерево по ошибке. Думаю понятно же дальше по часто встречающемуся слову граф что обход таки графа у меня
Dmitriy_M
1294 / 1175 / 104
Регистрация: 20.03.2009
Сообщений: 4,208
Записей в блоге: 11
29.01.2013, 10:30     Хитрый обход дерева в глубину #4
Такую книжку открывал?
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,508
02.02.2013, 04:26  [ТС]     Хитрый обход дерева в глубину #5
Dmitriy_M, открывал и листал, но в данном случае с задачкой так и не справился. Ну да уже для меня не актуально (сделал другой вариант).
Yandex
Объявления
02.02.2013, 04:26     Хитрый обход дерева в глубину
Ответ Создать тему
Опции темы

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