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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
Gepar
1175 / 531 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
#1

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

28.01.2013, 22:30. Просмотров 1311. Ответов 4
Метки нет (Все метки)

По условию необходимо обойти дерево так чтобы найти путь 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++
Покажите кто-нибудь как работает &quot;обход графа&quot; в графе в консоле А именно вывод глубины графа,сколько ребер обошел ,где был уже... ...

Обход графа в глубину - C++
Как сделать обход этого графа в глубину ?

Организовать обход в глубину - C++
Искал код, не смог найти подходящий. Цель следующая - первым обходом ищем все шарниры, а вторым нужно найти для каждого шарнира, на...

Обход графа в глубину - C++
Помогите, пожалуйста! Необходимо написать программу, которая показывала бы вершины, получаемые при обходе графа в глубину.

Обход неориентированного графа в глубину - C++
#include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;vector&gt; #include &lt;conio.h&gt; #include &lt;locale.h&gt; using namespace std; int...

Многопоточный обход графа в глубину - C++
Доброго времени суток. Подскажите многопоточный алгоритм обхода графа в глубину (нужно распараллелить алгоритм поиска компонент связности)....

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dmitriy_M
1341 / 1222 / 112
Регистрация: 20.03.2009
Сообщений: 4,393
Записей в блоге: 11
28.01.2013, 23:18     Хитрый обход дерева в глубину #2
Цитата Сообщение от Gepar Посмотреть сообщение
Ну или проще это же условие: Найти max длины путь без циклов и самопересечений.
По определению, дерево не имеет циклов.
Gepar
1175 / 531 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
29.01.2013, 05:34  [ТС]     Хитрый обход дерева в глубину #3
Dmitriy_M, я вначале написал слово дерево по ошибке. Думаю понятно же дальше по часто встречающемуся слову граф что обход таки графа у меня
Dmitriy_M
1341 / 1222 / 112
Регистрация: 20.03.2009
Сообщений: 4,393
Записей в блоге: 11
29.01.2013, 10:30     Хитрый обход дерева в глубину #4
Такую книжку открывал?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.02.2013, 04:26     Хитрый обход дерева в глубину
Еще ссылки по теме:

Обход вершин графа в глубину стеком - C++
Применить стек для обхода вершин графа, заданного с помощью матрицы смежности, в глубину. Есть код.. Но он не совсем правильно...

Обход дерева) - C++
Прога работает) но сказали, что нужно сделать отдельную функцию обхода дерева) можете помочь) или пример)) #include &lt;iostream.h&gt; ...

Обход дерева - C++
Вот начал читать про деревья и способы их обхода (PreOrder, InOrder и PostOrder). С алгоритмами проблем нет, но видно, как бы это сказать...

Обход дерева - C++
Всем доброе время суток. Не могу нормально обойти дерево и просмотреть введённое, по всей видимости, возможно я неправильно поставил...

обход дерева - C++
struct SAcson { int l,c; // строка, столбец float x; // заряд bool e; // возбуждающий или тормозящий }; struct SSinapc { ...

обход дерева - C++
Здравствуйте! У меня вопрос: Есть класс: class D { vector &lt;A*&gt; count; }; ...


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

Или воспользуйтесь поиском по форуму:
Gepar
1175 / 531 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
02.02.2013, 04:26  [ТС]     Хитрый обход дерева в глубину #5
Dmitriy_M, открывал и листал, но в данном случае с задачкой так и не справился. Ну да уже для меня не актуально (сделал другой вариант).
Yandex
Объявления
02.02.2013, 04:26     Хитрый обход дерева в глубину
Ответ Создать тему
Опции темы

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