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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Определить номера строк матрицы, в которых знаки элементов чередуются http://www.cyberforum.ru/cpp-beginners/thread773639.html
Здравствуйте все, просьба помочь в составлении программы для этой задачи: Определить номера строк матрицы, в которых знаки элементов чередуются.
C++ Хеш таблицы #include <iostream> #include <conio.h> #include <string> #include <list> using namespace std; //Структура элемента хэш таблицы struct node { int key; int value; http://www.cyberforum.ru/cpp-beginners/thread773635.html
C++ Изучение базовых типов данных
#include <cctype> #include <sstream> #include <string> using namespace std; int x; int x1; int m,c,d=0; int y; int s; float w=0;
else C++
что такое, для чего ипользуют. что означает пожалуйста русскими словами обьясните
C++ Деревья http://www.cyberforum.ru/cpp-beginners/thread773626.html
#include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; struct tree { int data; tree *left; tree *right;
C++ Освоение технологии реализации позиционных, линейных коллекций на примере АТД "Список". Освоение методики тестирования трудоѐмкости реализации колл #include <string> #include <time.h> using namespace std; int k,nn,kk=0; bool prover=false; int search1=0; //Создаем структуру node struct node { int key; подробнее

Показать сообщение отдельно
Gepar
1175 / 531 / 20
Регистрация: 01.07.2009
Сообщений: 3,517

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

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

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