Путь из S в исток J, который находится в этом графе: просматриваем по рёбрам (ненасыщенным) вершины S соседей: есть ли среди них J. Если нет, то заносим всех (обнаруженных впервые) соседей в стек для посещения. После просмотра всех соседей отмечаем нашу вершину, как уже посещённую. Достаем первую непосещённую вершину из стека и идем в неё. И так далее. Причём те вершины, в которых однажды побывали — пропускаем (обнуляются соответствующие элементы матрицы смежности). Если встречается J - путь составлен.
Если не секрет, вам к какому сроку надо?
Тут завалялась коллекция (однако, сам не проверял) исходников на Pascal (Delphi) и С++ различных алгоритмов на графах:
|