Связные компоненты,
поиск в глубину и ширину

Наиболее простой случай задачи о кратчайших путях -- если все цены равны или $+\infty$. Другими словами, мы интересуемся возможностью попасть из i в j , но за ценой не постоим. В других терминах: мы имеем ориентированный граф (картинку из точек, некоторые из которых соединены стрелками) и нас интересуют вершины, доступные из данной.

Для этого случая задачи о кратчайших путях приведенные в предыдущем разделе алгоритмы -- не наилучшие. В самом деле, более быстрая рекурсивная программа решения этой задачи приведена в главе 7 (Рекурсия), а нерекурсивная -- в главе 6 (Типы данных). Сейчас нас интересует такая задача: не просто перечислить все вершины, доступные из данной, но перечислить их в определенном порядке. Два популярных случая -- поиск в ширину и в глубину.


 
pvv
1/8/1999