«Способы представления последовательностей, множеств, графов и деревьев»


Применения алгоритма поиска в глубину


Download 282.31 Kb.
bet6/7
Sana18.06.2023
Hajmi282.31 Kb.
#1560689
TuriСамостоятельная работа
1   2   3   4   5   6   7
Bog'liq
«Способы представления последовательностей, множеств, графов и д

Применения алгоритма поиска в глубину

  • Поиск любого пути в графе.

  • Поиск лексикографически первого пути в графе.

  • Проверка, является ли одна вершина дерева предком другой.

  • Поиск наименьшего общего предка.

  • Топологическая сортировка.444

  • Поиск компонент связности.

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


Реализация на C++ (с использованием стека STL)
#include 
#include  // стек
using namespace std;
int main()
{
stack Stack;
int mas[7][7] = { { 0, 1, 1, 0, 0, 0, 1 }, // матрица смежности
{ 1, 0, 1, 1, 0, 0, 0 },
{ 1, 1, 0, 0, 0, 0, 0 },
{ 0, 1, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 1, 0, 1, 0 },
{ 0, 0, 0, 0, 1, 0, 1 },
{ 1, 0, 0, 0, 0, 1, 0 } };
int nodes[7]; // вершины графа
for (int i = 0; i < 7; i++) // исходно все вершины равны 0
nodes[i] = 0;
Stack.push(0); // помещаем в очередь первую вершину
while (!Stack.empty())
{ // пока стек не пуст
int node = Stack.top(); // извлекаем вершину
Stack.pop();
if (nodes[node] == 2) continue;
nodes[node] = 2; // отмечаем ее как посещенную
for (int j = 6; j >= 0; j--)
{ // проверяем для нее все смежные вершины
if (mas[node][j] == 1 && nodes[j] != 2)
{ // если вершина смежная и не обнаружена
Stack.push(j); // добавляем ее в cтек
nodes[j] = 1; // отмечаем вершину как обнаруженную
}
}
cout << node + 1 << endl; // выводим номер вершины
}
cin.get();
return 0;
}

Результат:

Поиск в глубину также может быть реализован с использованием рекурсивного алгоритма.



Download 282.31 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling