 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
|
|
|
|
|
|
|
|
|
  |
Поиск пути на простом неориентированном графе
ГРАФОВ ТЕОРИЯ, раздел математики, особенность которого - геометрический подход к изучению объектов. Основное понятие теории - граф - задается множеством вершин (точек) и множеством ребер (связей), соединяющих некоторые пары вершин. Пример графа - схема метрополитена: множество станций (вершины графа) и соединяющих их линий (ребра графа). Граф однозначно задан, если заданы множество его вершин, множество ребер и указаны все инцидентности (т.е. указано, какие вершины какими ребрами соединены). Наиболее наглядно граф задается рисунком; однако не все детали рисунка одинаково важны; в частности, несущественны геометрические свойства ребер (длина, кривизна и т.д.) и взаимное расположение вершин на плоскости. Маршрут, или путь - это последовательность ребер в неориентированном графе, в котором конец каждого ребра совпадает с началом следующего ребра. Число ребер маршрута называется его длиной. В этой статье я предлагаю ознакомиться с двумя алгоритмами нахождения пути на простом неориентированном графе. Метод волны (поиск в ширину)Подобно тому как, согласно принципу Гюйгенса, каждая точка волнового фронта является источником вторичной волны, мы, отправляясь из заданной вершины 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, печатаем путь. Если все вершины исчерпаны - такого пути нет. Ниже приведен текст программы для нахождения как только одного пути, так и всех путей, в том числе максимальной и минимальной длины. В программе используются следующие переменные 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 |
|
| © Алексей Кощеев, г.Киров, 2001-2024 |
