Алгоритмы на графах. Графы, оргафы, деревья

Идея поиска в ширину состоит в том, чтобы посещать вершины в порядке их удаленности от некоторой заранее выбранной или указанной стартовой вершины  . Иначе говоря, сначала посещается сама вершина  , затем все вершины, смежные с  , то есть находящиеся от нее на расстоянии  , затем вершины, находящиеся от a на расстоянии 2

Рассмотрим алгоритм поиска в ширину с заданной стартовой вершиной  . Вначале все вершины помечаются как новые. Первой посещается вершина  , она становится единственной открытой вершиной. В дальнейшем каждый очередной шаг начинается с выбора некоторой открытой вершины  . Эта вершина становится активной. Далее исследуются ребра, инцидентные активной вершине. Если такое ребро соединяет вершину   с новой вершиной  , то вершина   посещается и превращается в открытую. Когда все ребра, инцидентные активной вершине, исследованы, она перестает быть активной и становится закрытой. После этого выбирается новая активная вершина, и описанные действия повторяются. Процесс заканчивается, когда множество открытых вершин становится пустым.

Основная особенность поиска в ширину, отличающая его от других способов обхода графов, состоит в том, что в качестве активной вершины выбирается та из открытых, которая была посещена раньше других. Именно этим обеспечивается главное свойство поиска в ширину: чем ближе вершина к старту, тем раньше она будет посещена. Для реализации такого правила выбора активной вершины удобно использовать для хранения множества открытых вершин очередь - когда новая вершина становится открытой, она добавляется в конец очереди, а активная выбирается в ее начале.

Procedure BFS(a)

1. посетить вершину 
3. while   do
5. for   do
6. исследовать ребро 
7. if вершина   новая
8. then посетить вершину 

Отметим некоторые свойства процедуры BFS.

1. Процедура BFS заканчивает работу после конечного числа шагов.

Действительно, при каждом повторении цикла while из очереди удаляется одна вершина. Вершина добавляется к очереди только тогда, когда она посещается. Каждая вершина может быть посещена не более одного раза, так как посещаются только новые вершины, а в результате посещения вершина перестает быть новой. Таким образом, число повторений цикла while не превосходит числа вершин.

2. В результате выполнения процедуры BFS будут посещены все вершины из компоненты связности, содержащей вершину a, и только они.

Очевидно, что вершина может быть посещена только в том случае, когда существует путь, соединяющий ее с вершиной   (так как посещается всегда вершина, смежная с уже посещенной). То, что каждая такая вершина будет посещена, легко доказывается индукцией по расстоянию от данной вершины до вершины  .

3. Время работы процедуры BFS есть  , где   - число ребер в компоненте связности, содержащей вершину  .Из предыдущих рассуждений видно, что каждая вершина из этой компоненты становится активной точно один раз. Внутренний цикл for для активной вершины   выполняется   раз. Следовательно, общее число повторений внутреннего цикла будет равно  .

Итак, процедура BFS( ) производит обход компоненты связности, содержащей вершину  . Чтобы перейти к другой компоненте, достаточно выбрать какую-нибудь новую вершину (если такие вершины еще имеются), в качестве стартовой. Пусть   - множество вершин графа. Следующий алгоритм осуществляет полный обход графа методом поиска в ширину

 

2. Поиск в глубину

 

Поиск в глубину - вероятно, наиболее важная ввиду многочисленности приложений стратегия обхода графа. Идея этого метода - идти вперед в неисследованную область, пока это возможно, если же вокруг все исследовано, отступить на шаг назад и искать новые возможности для продвижения вперед. Метод поиска в глубину известен под разными названиями, например, "бэктрекинг", "поиск с возвращением".

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

Обход начинается с посещения заданной стартовой вершины  , которая становится активной и единственной открытой вершиной. Затем выбирается инцидентное вершине   ребро   и посещается вершина  . Она становится открытой и активной. Заметим, что при поиске в ширину вершина   оставалась активной до тех пор, пока не были исследованы все инцидентные ей ребра. В дальнейшем, как и при поиске в ширину, каждый очередной шаг начинается с выбора активной вершины из множества открытых вершин. Если все ребра, инцидентные активной вершине  , уже исследованы, она превращается в закрытую. В противном случае выбирается одно из неисследованных ребер  , это ребро исследуется. Если вершина   новая, то она посещается и превращается в открытую. Главное отличие от поиска в ширину состоит в том, что при поиске в глубину в качестве активной выбирается та из открытых вершин, которая была посещена последней. Для реализации такого правила выбора наиболее удобной структурой хранения множества открытых вершин является стек: открываемые вершины складываются в стек в том порядке, в каком они открываются, а в качестве активной выбирается последняя вершина. Схематически это показано на рис

Рисунок 3.2- Иллюстрирует процедуру поиска в глубину

 

Procedure DFS(a)

1. посетить вершину 
3. while   do
5. if имеется неисследованное ребро 
6. then исследовать ребро 
7. if вершина   новая
8. then посетить вершину 
10. else удалить   из 

Еще раз обратим внимание на основное отличие этой процедуры от аналогичной процедуры поиска в ширину. При поиске в ширину вершина, став активной, остается ею, пока не будет полностью исследована ее окрестность, после чего она становится закрытой. При поиске в глубину, если в окрестности активной вершины   обнаруживается новая вершина  , то   помещается в стек и при следующем повторении цикла while станет активной. При этом   остается в стеке и через какое-то время снова станет активной. Иначе говоря, ребра, инцидентные вершине  , будут исследованы не подряд, а с перерывами.

 

4 КРАТЧАЙШИЕ ПУТИ

 

Кратчайшим путем между двумя вершинами называется путь наименьшего веса, соединяющий эти вершины. Рассмотрим задачу отыскания кратчайших путей от заданной вершины   до всех остальных вершин графа. Возможно, более естественной постановкой задачи кажется поиск кратчайшего пути между двумя заданными вершинами. Однако в настоящее время не известно никакого способа решения этой задачи, существенно лучшего, чем поиск кратчайших путей от начальной вершины до всех остальных.

 

4.1 Алгоритм Дейкстры

 

Дерево с множеством вершин  , а д

ля каждой вершины   известна вершина  , на которой достигается наименьшее значение величины  , где минимум берется по всем вершинам  . Тогда на этом шаге следует выбрать вершину   с наименьшим значением величины   и присоединить к дереву ребро  . После этого для каждой вершины  , еще не принадлежащей к дереву, значения   и   уточняются следующим образом: если , то следует положить  ,  . Вершина   может рассматриваться как предполагаемый отец вершины   в геодезическом дереве (если все множество   состояло бы из одной вершины  , то   была бы ее истинным отцом). Величина   представляет собой оценку кратчайшего пути из   в  , она равна весу кратчайшего из путей, проходящих только через вершины множества  . После того, как вершина   присоединяется к дереву, значения   и   больше не изменяются,   является отцом вершины   в геодезическом дереве, а  . В целом алгоритм можно представить следующим образом:

3. for   do   ; 
4. while   do
5. выбрать вершину   с наименьшим значением 
7. for   do
8. if 
9. then  , 

 

5. ДЕРЕВЬЯ

 

Каждому дереву можно поставить в соответствие некоторой код. С помощью этого кода можно восстановить дерево с точностью до изоморфизма. Существуют различные способы кодировки деревьев, которые позволяют решать конкретные задачи (подсчет деревьев, установление изоморфизма, генерирование всех неизоморфных деревьев и т.д.).Представлением дерева называется способ записи информации о нем, однозначно и полностью восстанавливающий структуру дерева и позволяющий вычислить его характеристики. Выбор представления зависит от решаемой задачи и способа ее решения

 

5.1 Представление с помощью матрицы смежности

 

Это представление является общим для всех видов графов; оно задает граф с точностью до изоморфизма, но вместе с тем данное представление неэкономично, так как ненулевыми являются для  -вершинного дерева только  из   элементов матрицы.

Задание графа матрицей смежности , размера  , где   — число вершин графа.  , если вершины   и  смежные, в противном случае  .   — симметрическая матрица для неориентированного графа и несимметрическая для ориентированного.

Для неориентированного графа матрица смежности симметрична относительно главной диагонали, поэтому можно задавать только верхнюю треугольную половину матрицы, но это не улучшает ситуацию. Другой недостаток этого представления заключается в том, что трудоемкость алгоритмов, работающих с таким представлением, не может быть ниже.

Пример.

Рисунок 4.1- Иллюстрирует дерево

 

Рисунок 4.2 - Иллюстрирует матрицу смежности 

6 РАЗРАБОТКА ПРОГРАММЫ

Листинг:

#include<iostream>

#include<string>

using namespace std;

int main()

{

char ans;

do{

int arr[5];

int arr1[5];

int l=1,v=2;

cout<<"vvedite cislo versin";

  int grafs;

  cin>>grafs;

  if(grafs==1)

  {

  cout<<"vvedite cislo petelei 1 versini";

  cin>>arr[0];

  cout<<"   A"<<endl;

  cout<<"M={"<<arr[0]<<"}A";

  }

  if(grafs==2){

  cout<<"vvedite cislo petelei 1 versini";

  cin>>arr[0];

   cout<<"vvedite cislo dug 1 versini vo 2 versinu";

  cin>>arr[1];

  cout<<"vvedite cislo petelei 2 versini";

  cin>>arr[2];

   cout<<"vvedite cislo dug 2 versini vo 1 versinu";

  cin>>arr[3];

   cout<<"   A B"<<endl;

   cout<<"M={"<<arr[0]<<" "<<arr[1]<<"}A"<<endl<<"  {"<<arr[3]<<" "<<arr[2]<<"}B";

  }

  if(grafs==3){

  cout<<"vvedite cislo petelei 1 versini";

  cin>>arr[0];

   cout<<"vvedite cislo dug 1 versini vo 2 versinu";

  cin>>arr[1];

  cout<<"vvedite cislo dug 1 versini vo 3 versinu";

  cin>>arr[2];

  cout<<"vvedite cislo petelei 2 versini";

  cin>>arr[3];

   cout<<"vvedite cislo dug 2 versini vo 1 versinu";

  cin>>arr[4];

  cout<<"vvedite cislo dug 2 versini vo 3 versinu";

  cin>>arr[5];

   cout<<"vvedite cislo petelei 3 versini";

  cin>>arr[6];

   cout<<"vvedite cislo dug 3 versini vo 1 versinu";

  cin>>arr[7];

  cout<<"vvedite cislo dug 3 versini vo 2 versinu";

  cin>>arr[8];

  cout<<"   A B C"<<endl;

  cout<<"M={"<<arr[0]<<" "<<arr[1]<<" "<<arr[2]<<"}A"<<endl<<"  {"<<arr[4]<<" "<<arr[3]<<" "<<arr[5]<<"}B"<<endl<<"  {"<<arr[7]<<" "<<arr[8]<<" "<<arr[6]<<"}C";

  }

  if(grafs==4){

  cout<<"vvedite cislo petelei 1 versini";

  cin>>arr[0];

   cout<<"vvedite cislo dug 1 versini vo 2 versinu";

  cin>>arr[1];

  cout<<"vvedite cislo dug 1 versini vo 3 versinu";

  cin>>arr[2];

   cout<<"vvedite cislo dug 1 versini vo 4 versinu";

  cin>>arr[3];

  cout<<"vvedite cislo petelei 2 versini";

  cin>>arr[4];

   cout<<"vvedite cislo dug 2 versini vo 1 versinu";

  cin>>arr[5];

  cout<<"vvedite cislo dug 2 versini vo 3 versinu";

  cin>>arr[6];

   cout<<"vvedite cislo dug 2 versini vo 4 versinu";

  cin>>arr[7];

   cout<<"vvedite cislo petelei 3 versini";

  cin>>arr[8];

   cout<<"vvedite cislo dug 3 versini vo 1 versinu";

  cin>>arr[9];

  cout<<"vvedite cislo dug 3 versini vo 2 versinu";

  cin>>arr[10];

   cout<<"vvedite cislo dug 3 versini vo 4 versinu";

  cin>>arr[11];

   cout<<"vvedite cislo petelei 4 versini";

  cin>>arr[12];

   cout<<"vvedite cislo dug 4 versini vo 1 versinu";

  cin>>arr[13];

  cout<<"vvedite cislo dug 4 versini vo 2 versinu";

  cin>>arr[14];

   cout<<"vvedite cislo dug 3 versini vo 4 versinu";

  cin>>arr[15];

  cout<<"   A B C D"<<endl;

  cout<<"M={"<<arr[0]<<" "<<arr[1]<<" "<<arr[2]<<" "<<arr[3]<<"}A"<<endl<<"  {"<<arr[5]<<" "<<arr[4]<<" "<<arr[6]<<" "<<arr[7]<<"}B"<<endl<<"  {"<<arr[9]<<" "<<arr[10]<<" "<<arr[8]<<" "<<arr[11]<<"}C"<<endl<<"  {"<<arr[13]<<" "<<arr[14]<<" "<<arr[15]<<" "<<arr[12]<<"}D";

  }

   if(grafs==5){

  cout<<"vvedite cislo petelei 1 versini";

  cin>>arr[0];

   cout<<"vvedite cislo dug 1 versini vo 2 versinu";

  cin>>arr[1];

  cout<<"vvedite cislo dug 1 versini vo 3 versinu";

  cin>>arr[2];

   cout<<"vvedite cislo dug 1 versini vo 4 versinu";

  cin>>arr[3];