Главная страница Случайная лекция Мы поможем в написании ваших работ! Порталы: БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика Мы поможем в написании ваших работ! |
Алгоритм вертикального обхода дерева
2.1. Нисходящий обход. Как было описано ранее, нисходящий или прямой обход дерева выглядит следующим образом: корень - левое поддерево - правое поддерево. Для дерева, изображённого на рисунке 1.2 нисходящий обход представляет собой последовательность вершин: A-B-D-G-E-C-F-K Наглядно это представлено на рисунке 2.1:
Программный код для прямого обхода бинарного дерева будет иметь вид: Пример 2.1.1
/*ОБХОД В ПЯМОМ ПОРЯДКЕ (НИСХОДЯЩИЙ ОБХОД)*/ void pram_ob (derevo *&svob) { if (NULL==svob) return; //Если дерева нет, выходим
printf("%d\n",svob->x); //Посетили узел pram_ob (svob->left); //Обошли левое поддерево pram_ob (svob->rite); //Обошли правое поддерево } Помимо рекурсивного обхода, существует инерационный прямой обход с использованием стека. Его программный код будет иметь вид: void pram_iter_ob(derevo *current, int l) { int flag=0; while(flag==0) { while(current!=NULL) { l++; Push(current, l); for( int i=0; i<l; i++) cout << "\t"; cout << current->info << endl; current=current->left; } if(stack==NULL) flag=1; else { l=Pop(¤t); current=current->right; } } } 2.2. Восходящий обход. Восходящий обход осуществляется по схеме: левое поддерево - правое поддерево – корень. Для дерева, изображённого на рисунке 1.2 нисходящий обход представляет собой последовательность вершин: G-E-D-B-F-K-C-A Графически это выглядит так (рисунок 2.2):
2.3. Смешанный обход Смешанный обход осуществляется по схеме: левое поддерево – корень – правое поддерево. Для дерева изображенного на рисунке 1.2 смешанный обход представляет последовательность вершин: G – D – B – E – A – F – C – K Выглядит это следующим образом (рисунок 2.3): 16.Обход графа в ширину. Поиск в ширину (обход по уровням) – один из алгоритмов обхода графа. Метод лежит в основе некоторых других алгоритмов близкой тематики. Поиск в ширину подразумевает поуровневое исследование графа: вначале посещается корень – произвольно выбранный узел, затем – все потомки данного узла, после этого посещаются потомки потомков и т.д. Вершины просматриваются в порядке возрастания их расстояния от корня. Пусть задан граф G=(V, E) и корень s, с которого начинается обход. После посещения узла s, следующими за ним будут посещены смежные с s узлы (множество смежных с s узлов обозначим как q; очевидно, что q⊆V, то есть q – некоторое подмножество V). Далее, эта процедура повториться для вершин смежных с вершинами из множества q, за исключением вершины s, т. к. она уже была посещена. Так, продолжая обходить уровень за уровнем, алгоритм обойдет все доступные из s вершины множества V. Алгоритм прекращает свою работу после обхода всех вершин графа, либо в случае выполнения наличествующего условия. Рассматривая следующий пример, будем считать, что в процессе работы алгоритма каждая из вершин графа может быть окрашена в один из трех цветов: черный, белый или серый. Изначально все вершины белые. В процессе обхода каждая из вершин, по мере обнаружения, окрашивается сначала в серый, а затем в черный цвет. Определенный момент обхода описывает следующие условие: если вершина черная, то все ее потомки окрашены в серый или черный цвет.
Имеем смешанный граф (см. рис.) с |V| = 4 и |E| = 5. Выполним обход его вершин, используя алгоритм поиска в ширину. В качестве стартовой вершины возьмем узел 3. Сначала он помечается серым как обнаруженный, а затем черным, поскольку обнаружены смежные с ним узлы (1 и 4), которые, в свою очередь, в указанном порядке помечаются серым. Следующим в черный окрашивается узел 1, и находятся его соседи – узел 2, который становится серым. И, наконец, узлы 4 и 2, в данном порядке, просматриваются, обход в ширину завершается. Алгоритм поиска в ширину работает как на ориентированных, так и на неориентированных графах. Дать понять это был призван смешанный граф, используемый в примере. Стоит отметить, в неориентированном связном графе данный метод обойдет все имеющиеся узлы, а в смешанном или орграфе это необязательно произойдет. К тому же, до сих пор рассматривался обход всех вершин, но вполне вероятно, достаточным окажется, например просмотр определенного их количества, либо нахождение конкретной вершины. В таком случае придется немного приспособить алгоритм, а не изменять его полностью или вовсе отказаться от использования такового. Теперь перейдем к более формальному описанию алгоритма поиска в ширину. Основными объектами – тремя структурами данных, задействованными в программе, будут: · матрица смежности графа GM; · очередь queue; · массив посещенных вершин visited. Две первые структуры имеют целочисленный тип данных, последняя – логический. Посещенные вершины, заносятся в массив visited, что предотвратит зацикливание, а очередь queue будет хранить задействованные узлы. Напомним, что структура данных «очередь» работает по принципу «первый пришел – первый вышел». Рассмотрим разбитый на этапы процесс обхода графа: 1. массив visited обнуляется, т. е. ни одна вершина графа еще не была посещена; 2. в качестве стартовой, выбирается некоторая вершина s и помещается в очередь (в массив queue); 3. вершина s исследуется (помечается как посещенная), и все смежные с ней вершины помещаются в конец очереди, а сама она удаляется; 4. если на данном этапе очередь оказывается пустой, то алгоритм прекращает свою работу; иначе посещается вершина, стоящая в начале очереди, помечается как посещенная, и все ее потомки заносятся в конец очереди; 5. пункт 4 выполняется пока это возможно. Поиск в ширину, начиная со стартовой вершины, постепенно уходит от нее все дальше и дальше, проходя уровень за уровнем. Получается, что по окончанию работы алгоритма будут найдены все кратчайшие пути из начальной вершины до каждого доступного из нее узла.
Дата добавления: 2015-07-26; просмотров: 370; Нарушение авторских прав Мы поможем в написании ваших работ! |