Программная реализация алгоритмов поиска в глубину и ширину в неориентированных графах

Вершина хi называется точкой сочленения (или разделяющей вершиной), если после ее удаления граф становится не связным. Ребро графа называется мостом, если его удаление приводит к несвязному графу.

1.1.7 Деревья

Связный ациклический граф, имеющий не менее двух вершин, называется креном. Любое дерево на n вершинах содержит n-1 ребер и имеет по крайней мере две висячие вершины. Любы

е две вершины дерева связаны единственной простой пенью. Ориентированным деревом называется орграф без циклов, в котором имеется вершина x0, из которой существует только один ориентированный путь в любую другую вершину. Деревом графа G называется любой его связный ациклический подграф. Дерево графа G, содержащее все вершины этого графа, называется остовным дереном (остовом) Т графа G. При этом ребра остовного дерева Т называются ветвями, а ребра графа G, не принадлежащие остову Т – хордами. К – деревом называется ациклический граф, состоящий из k компонент связности. Если k – дерево является остовным подграфом графа G, то оно называется k – остовом этого графа. Ациклический несвязный граф, все компоненты связности которого являются деревьями, называется лесом.

Очевидно, что в любом графе существует остов, причем в общем случае остов может быть выделен не единственным способом. Например, для полною графа Кn существует nn-2 остовных деревьев. Таким образом, число деревьев, которые можно построить на данных n вершинах, равно nn-2.

Для остовного дерева Т справедливы следующие утверждения:

1) Т – связный граф, но он утрачивает связность при удалении хотя бы одного ребра.

2) Т – ациклический граф, но добавление хотя бы одного ребра приводит к появлению в нем цикла.

3) Число ребер графа Т на 1 меньше числа его вершин.

1.1.8 Алгоритм поиска в глубину и ширину

Для построения произвольного остова связного графа могут быть использованы две стратегии: поиск в глубину и поиск в ширину.

Опишем алгоритм поиска в глубину (этот метод стал одной из основных методик проектирования графовых алгоритмов). Поиск начинается с некоторой фиксированной вершины x0, например, с висячей. Затем выбирается вершина x1, смежная с x0. После этого выбирается вершина х2, смежная с х1, и т.д. Еще не просмотренные вершины будем условно называть новыми. Если на k-м шаге поиска для вершины xk существует новая вершина xk+1, то она выбирается (перестаёт быть новой) и поиск продолжается от вершины xk+1. Если же для вершины xk новых вершин не существует, осуществляется возврат к вершине, из которой мы попали в xk, и поиск осуществляется от неё. Процесс продолжается до тех нор, пока не будет произведён возврат в вершину х0. В процессе поиска вершины соединяют рёбрами.

Поиск в ширину отличается от поиска в глубину тем, что выбор очередной вершины происходит путем просмотра не одной, а всех смежных.

2. Описание программы

2.1 Описание структуры программы

Весь алгоритм программы можно разбить на следующие шаги.

1) Директива компилятора {$1-} указывает на необходимость отключить автоматическое завершение программы в случае ошибки ввода-вывода. Используется модуль crt (это позволяет применить в программе некоторые нестандартные для обычного языка Pascal процедуры и функции).

2) Объявляются переменные и метки и описываются процедуры. Следующие идентификаторы являют собой: а – 1) матрица смежности неорграфа (максимальный размер 15*15), 2) если имеются индексы, то – элемент матрицы смежности; b – 1) массив новых вершин неорграфа, 2) если есть индекс, то – свойство вершины («1» – новая, не просмотренная вершина, «0» – старая, уже просмотренная); с – 1) «очередь / стек» (массив), 2) если есть индекс, то – элемент «очереди / стека»; i – 1) индекс исходной вершины, 2) индекс рассматриваемой вершины, вершины отсчета, относительно которой осуществляется поиск; j –1) индекс искомой вершины, 2) столбцовый индекс элемента матрицы смежности; к – 1) номер нижнего, первого, элемента очереди, 2) строковый индекс элемента матрицы смежности; 1 – номер верхнего, последнего, элемента (позиции) стека / очереди. m – счетчик недостижимых вершин; n – количество вершин графа; о – символ, считанный с клавиатуры; р – счетчик найденных вершин; v – результат ввода (переменная принимает два значения: правильный ввод или ошибочный); w, х, у, z – метки.

3) Начало программы. Экран очищается. Вызывается процедура Vvod.

4) Процедура Vvod организует ввод количества вершин n и элементов матрицы смежности а, а также проверку правильности ввода:

а) В цикле. Предлагается ввести n. Цикл работает до тех пор, пока ввод не будет выполнен правильно, при этом выводится сообщение об ошибке.

б) В цикле. Предлагается ввести элементы матрицы а. Если akj принимает значение, отличное от 0 или 1, то формируется сообщение об ошибке и организуется возврат к пункту 4.

в) Проверяется симметричность матрицы: в цикле просматриваются элементы матрицы смежности. Если akj не равно ajk, то выдается сообщение о несимметричности матрицы b, организуется возврат к пункту 4.

5) С помощью цикла организуется «меню» программы (пункты «меню»: поиск в глубину, поиск в ширину, изменение матрицы смежности, вывод из программы). Предлагается выбрать пункт меню, нажав соответствующую клавишу (символ считывается с клавиатуры). Если выбран пункт меню «изменение матрицы», то осуществляется возврат к пункту 4. Если выбран поиск в ширину, то вызываются процедуры Ohistka и VShiriny (переход к пункту 6, а от него к пункту 7). Если выбран поиск в глубину, то вызываются процедуры Ochistka и VGlubiny (переход к пункту 6, а от него к пункту 8). Если выбран выход из программы, то цикл останавливается и программа завершается. Если нажата иная клавиша, то цикл продолжит работу.

6) Процедура Ochistka очищает экран от текста, обнуляет количество недостижимых вершин, очищает «стек / очередь» (заполняет массив с нулями), «обновляет» вершины неорграфа, т.е. делает их непросмотренными (заполняет массив b единицами) и выводит на экран количество вершин n и матрицу смежности а. (Переход к пункту 7 или 8, в зависимости от выбранного варианта поиска).

7) Процедура Vshiriny организует поиск в ширину: вызывается процедура ishodnaja (переход к пункту 9 с последующим возвратом к 7-му). В цикле просматриваются элементы очереди, начиная с первого и заканчивая n-ным. Если элемент очереди пуст ск=0, то цикл завершается, иначе рассматриваемой вершиной i становится вершина, находящаяся в последнем элементе очереди сk; в цикле на основе заполнения матрицы а ищутся новые смежные с i-той j-тые вершины: если аij=1 и bj=l (т.е. i-тая вершина смежна с j-той, и j-тая вершина – новая), то выводится пояснение к поиску и индекс найденной вершины, вершина становится «старой», т.е. уже найденной и помещается в последний элемент очереди, номер 1 которого до этого увеличивается на 1, счетчик р засчитывает найденную вершину. Цикл переходит к просмотру следующего элемента очереди ск. И после просмотра всех элементов выводится сообщение об окончании поиска; при этом если р=1, т.е. найденных вершин, не считая исходной, нет, то выдается сообщение об изолированности исходной вершины. (Переход к пункту 10).

 Скачать реферат