Поиск в глубину

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

#include<stdio.h>

int MAXN = 100;//Максимальное число вершин
int MAXM = 100;//Максимальное число ребер
int minpath[MAXN];//Массив расстояний до i-ой вершины
int n;//Число вершин
int m;//Число ребер
int first;//Начальная вершина

int b[MAXM];//b[i] - куда ведет ребро i
int bc;//количество ребер
int last[MAXN];//Последнее ребро, исходящее из вершины
int prev[MAXM];
/*prev[i] - предыдущее ребро, исходящее из той же вершины, что и ребро i.*/

void dfs(int p; int len)
{//Передаем вершину и новый путь до нее
    if (minpath[p] != -1 && len < minpath[p])
        return;
    //Проверяем, уменьшим ли мы минимальный путь до это вершины
    minpath[p] = len;
    //Устанавливаем новый минимальный путь
    
    int i = last[p];
    //Начинаем перебирать ребра, начиная с последнего, исходящего из p
    while (i != -1)
{//Пока не дошли до последнего ребра
        dfs(b[i], len + 1);
        //Запускаем рекурсию в вершину, в которое ведет ребро i

        i = prev[i];
        //Переходим к предыдущему ребру.
    }
}

int main()
{
    scanf(“%d%d%d”, &n, &m, &first);
    //Читаем количество вершин, ребер и начальную вершину

    for (int i = 0; i < n; i++)
{
        minpath[i] = -1;
        last[i] = -1;
    }
    /*Устанавливаем значения минимальных путей и отсутствие ребер из каждой вершину.*/

    //Читаем список ребер:
    for (int i = 0; i < m; i++)
{
        int l, r;
        scanf(“%d%d”, &l, &r);
        
        bc++;
        b[bc] = r;
        //заносим вершину назначения данного ребра в массив
        prev[bc] = last[x];
        //Устанвливаем предыдущее ребро, как последнее, исходящее из x

        last[x] = bc;
        //Теперь последнее ребро – то, которое мы только что добавили.
    }

    dfs(first, 0);
    //Запускаем dfs из первой вершины
    /*Сейчас в массиве minpath будут расстояния от вершины first до всех остальных вершин*/
}

Модификации

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

• Для поиска не только кратчайшего пути, но и вершин, по которым нужно идти, чтобы получить этот кратчайший путь (используется, например, в алгоритме нахождения максимального потока)
• В поиске в глубину можно для каждой вершины запоминать время выхода из нее – для алгоритма нахождения минимального общего предка в графе-дереве.
• Оба алгоритма могут быть использованы для нахождения циклов в графе.
• Поиск в глубину может использоваться для топологической сортировки графа.

Эти два алгоритма являются базовыми при изучении графов и алгоритмов на них.