О себе События Портфолио Статьи Гостевая Фотоальбом На злобу дня Ссылки Учеба Программы
Alex_K (г.Киров) - Алексей Кощеев
Хостинг и регистрация доменов в Кирове

Поиск пути на простом неориентированном графе

Поиск пути на простом неориентированном графе

ГРАФОВ ТЕОРИЯ, раздел математики, особенность которого - геометрический подход к изучению объектов. Основное понятие теории - граф - задается множеством вершин (точек) и множеством ребер (связей), соединяющих некоторые пары вершин. Пример графа - схема метрополитена: множество станций (вершины графа) и соединяющих их линий (ребра графа).

Граф однозначно задан, если заданы множество его вершин, множество ребер и указаны все инцидентности (т.е. указано, какие вершины какими ребрами соединены). Наиболее наглядно граф задается рисунком; однако не все детали рисунка одинаково важны; в частности, несущественны геометрические свойства ребер (длина, кривизна и т.д.) и взаимное расположение вершин на плоскости.

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

В этой статье я предлагаю ознакомиться с двумя алгоритмами нахождения пути на простом неориентированном графе.

Метод волны (поиск в ширину)

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

Простейшим способом описания графа, содержащего n вершин, является таблица (матрица) смежности размера n х n. Она строится так: вершины графа перенумеровываются, и на пересечении i-й строки с j-м столбцом записывается 1, если вершины с номерами i и j связаны между собой ребром, и 0 в противном случае.

Программные коды адаптированны под приложения SDI C++Builder5. В переменной head будет находиться номер вершины, из которой идет волна при помощи переменной tail новые вершины помещаются в path. prv_total, prv_from, prv_to - переменные, хранящие общее количество ребер, номер вершины, из которой нужно найти путь, и номер вершины, в которую нужно найти путь, соответственно.

void Widthh::i2j(const DynamicArray<DynamicArray<int> > &matr) { // нужен для того, чтобы отмечать уже пройденные вершины DynamicArray<bool > VUsed; // для хранения пройденных вершин. DynamicArray<int > Prev, Path; Prev.Length = prv_total; Path.Length = prv_total; VUsed.Length = prv_total; for (int k=0; k < prv_total; k++) { Path[k] = 0; Prev[k] = 0; VUsed[k] = false; } /* в переменной head будет находиться номер вершины, из которой идет волна при помощи переменной tail новые вершины помещаются в path */ int head = 1, tail = 1; AnsiString s = ""; bool PathFinded = false; // правильнее было назвать переменную pathFound int i = prv_from; Path[tail-1] = i; VUsed[i-1] = true; while (head <= tail && !PathFinded) { int v = Path[head-1]; head++; for (int k = 1; k <= prv_total; k++) if (matr[v-1][k-1] == 1 && !VUsed[k-1]) { tail++; Path[tail-1] = k; VUsed[k - 1] = true; Prev[k - 1] = v; if (k == prv_to) { PathFinded = true; break; } } } if (PathFinded) { int k = prv_to; s = IntToStr(prv_to); while (Prev[k - 1] != 0) { s = IntToStr(Prev[k - 1]) + " - " + s; k = Prev[k - 1]; } } else s = "Путь не найден"; prv_obj->Lines->Add("Искали самый короткий путь методом поиска в ширину"); prv_obj->Lines->Add(s); prv_obj->Lines->Add(""); Prev.Length = 0; Path.Length = 0; VUsed.Length = 0; }

Поиск в ширину определяет кратчайший путь из prv_from в prv_to. Действительно, если принять длину дуги за 1 и в path лежат вершины, удаленные от prv_from на расстояние r, то сначала в path попадут все вершины, расположенные на 1 дальше от prv_from, чем ранее включенные (т.е. вершины, удаленные от prv_from на расстояние r+1). Поскольку при первом проходе в path попадают все вершины, удаленные от prv_from на 1, по индукции получаем требуемое.

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

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

Ниже приведен текст программы для нахождения как только одного пути, так и всех путей, в том числе максимальной и минимальной длины. В программе используются следующие переменные prv_stop_search - флаг для завершения поиска (необходим при поиске всех путей), prv_use_file - переменная, хранящая необходимость использования временного файла (файл необходим для возможности хранения найденных путей), prv_callback_object - указатель на адрес объекта для интерактивного отображения количества найденных путей, prv_obj - указатель (Pointer) на адрес объекта для вывода результата.

void Depth::i2j(const DynamicArray<DynamicArray<int> > &matr) { int i = 1; // Номер вершины для добавления в путь DynamicArray<bool > VUsed; // Массив признаков занятости вершин DynamicArray<int > Path; Path.Length = prv_total; VUsed.Length = prv_total; for (int k=0; k < prv_total; k++) { Path[k] = 0; VUsed[k] = false; } bool NoStep; // Признак перехода к следующей вершине int CurVer = prv_from; // Номер текущей вершины int paths = 0; // счетчик путей AnsiString s1, smin, smax; // переменные для хранения путей int max = 0, min = prv_total; // переменные для хранения длин путей int PCur = 1; Path[PCur-1] = CurVer; VUsed[CurVer-1] = true; // ============================== char tmp_file[] = "paths.tmp"; FILE *out; if ((out = fopen(tmp_file, "w")) == NULL) { // невозможно открыть файл Application->MessageBox("Cannot open temp file.", NULL, MB_OK); prv_stop_search = true; } // ============================== while (!prv_stop_search) { NoStep = true; while (i <= prv_total && NoStep && !prv_stop_search) { if (matr[CurVer-1][i-1] == 1 && !VUsed[i-1] && CurVer != i) { if (i != prv_to) { NoStep = false; PCur++; VUsed[i-1] = true; Path[PCur-1] = i; CurVer = i; } else { s1 = ""; for (int h = 0; h < PCur; h++) s1 += IntToStr(Path[h]) + " - "; s1 += IntToStr(prv_to); paths++; if (prv_search == 1) { if (prv_use_file) fprintf(out, "%s\n", s1); if (max < PCur) { smax = s1; max = PCur; } if (min > PCur) { smin = s1; min = PCur; } i++; if (paths % 1000 == 0) prv_callback_object->Caption = IntToStr(paths); } else { prv_stop_search = true; break; // выход из вложенного while } } } else i++; } if (NoStep) { VUsed[CurVer-1] = false; i = CurVer+1; PCur--; if (PCur == 0) { prv_stop_search = true; break; } CurVer = Path[PCur-1]; } else i = 1; Application->ProcessMessages(); } // окончательное число найденных путей if (prv_search == 1) { prv_callback_object->Caption = IntToStr(paths); fclose(out); } prv_obj->Lines->Add((prv_search ? "Искали все пути" : "Искали один путь")); prv_obj->Lines->Add("Найдено " + IntToStr(paths)); if (prv_search) { prv_obj->Lines->Add("Max = " + IntToStr(max) + "; " + smax); prv_obj->Lines->Add("Min = " + IntToStr(min) + "; " + smin); } else prv_obj->Lines->Add(s1); prv_obj->Lines->Add(""); // обнуляем массивы Path.Length = 0; VUsed.Length = 0; // устанавливаем флаг останова в положение ложь prv_stop_search = false; }

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

Особенности моей реализации решения этих задач:

  • каждая задача решается в специальном классе;
  • оба класса полиморфны третьему, абстрактному классу;
  • работа производится только с динамическими массивами.

Скачать коды и exe Вы можете здесь.

При написании этой статьи были использованы: большая энциклопедия Кирилла и Мефодия, а также несколько web - документов, ссылки на которые не сохранены.

Алексей Кощеев
4.01.2003
Наверх  Посмотреть другие статьи
Fanshop.ru

Рейтинг@Mail.ru

Rambler's Top100

© Алексей Кощеев, г.Киров, 2001-2020 хостинг предоставлен компанией Айхэд