Поиск на графах

На практике часто возникают задачи, связанные с прохождением по вершинам графа. Например, необходимо ответить на вопрос: достижима ли вершина d из вершины a? То есть, существует ли путь из а в d. Если исходный граф неориентированный, то для ответа на данный вопрос достаточно определить, принадлежат ли вершины а и d одной связной компоненте. Выделить связные компоненты можно с помощью алгоритма Краскала. Если после завершения работы алгоритма Краскала вершины а и d принадлежат разным деревьям покрывающего леса (разным букетам – в терминах, используемых при формулировке алгоритма Краскала), то пути из вершины а в вершину d не существует, в противном случае - путь существует.

Для ориентированного графа такой алгоритм не пригоден. Для ответа на вопрос, достижима вершина d из вершины a или нет, необходимо организовать обход вершин графа, начиная из вершины а. Если во время обхода мы встретим вершину d, следовательно, верщина d достижима из вершины а, в противном случае - d из а не достижима.

Существует два способа организации обхода: поиск в глубину и поиск в ширину.