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

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

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

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

28.01.2013, 22:30. Просмотров 1388. Ответов 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 длина
}

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

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

Обход графа в глубину - C++
Покажите кто-нибудь как работает &quot;обход графа&quot; в графе в консоле А именно вывод глубины графа,сколько ребер обошел ,где был уже... ...

Организовать обход в глубину - 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++
Доброго времени суток. Подскажите многопоточный алгоритм обхода графа в глубину (нужно распараллелить алгоритм поиска компонент связности)....

4
Dmitriy_M
1360 / 1243 / 114
Регистрация: 20.03.2009
Сообщений: 4,449
Записей в блоге: 11
28.01.2013, 23:18 #2
Цитата Сообщение от Gepar Посмотреть сообщение
Ну или проще это же условие: Найти max длины путь без циклов и самопересечений.
По определению, дерево не имеет циклов.
0
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
29.01.2013, 05:34  [ТС] #3
Dmitriy_M, я вначале написал слово дерево по ошибке. Думаю понятно же дальше по часто встречающемуся слову граф что обход таки графа у меня
0
Dmitriy_M
1360 / 1243 / 114
Регистрация: 20.03.2009
Сообщений: 4,449
Записей в блоге: 11
29.01.2013, 10:30 #4
Такую книжку открывал?
0
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
02.02.2013, 04:26  [ТС] #5
Dmitriy_M, открывал и листал, но в данном случае с задачкой так и не справился. Ну да уже для меня не актуально (сделал другой вариант).
0
02.02.2013, 04:26
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.02.2013, 04:26
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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