Скачать бесплатно рефераты, сочинения, курсовые работы

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

матрица m[1..n, 1..n] - матрица смежности графа;
вспомогательный массив queue[1..n], в котором будет формироваться оче-редь, т.е. тип данных первый вошел – первый вышел (FIFO). Размер его доста-точен, так как мы не посещаем вершины дважды. С массивом queue связаны две переменные - head и tail. В переменной head будет находиться номер теку-щей вершины, из которой идет волна, а при помощи переменной tail новые вершины помещаются в "хвост" очереди queue;
вспомогательный массив visited[1..n], который нужен для того, чтобы отме-чать уже пройденные вершины (visited[i]=TRUE вершина i пройдена);
вспомогательный массив prev[1..n] для хранения пройденных вершин. В этом массиве и будет сформирован искомый путь;
переменная f, которая примет значение TRUE, когда путь будет найден.
Кроме того, мы введем несколько вспомогательных переменных, которые понадобятся при организации циклов.
Program breadth_first_search;


Скачать реферат
y-na-grafax.zip [68.69 Kb] (cкачиваний: 5)