Поиск в графе. Алгоритмы поиска в глубину и в ширину

1.

Matematica Discretă
Prelegere nr.7
Поиск в графе. Алгоритмы поиска в глубину и в ширину.
Алгоритм Форда поиска минимальных (максимальных)
путей.
Titularul cursului: conf. univ. dr. Galina Marusic
Chișinău, 2024
1

2.

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

3.

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

4.

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

5.

Минимальный (кратчайший) путь.
Взвешенные графы
Пусть G=(X, E,