CKTIS / C
Търсене в дълбочина (DFS) на C
Търсенето в дълбочина (DFS) изследва следващия клон на графа, преди да се върне към останалите съседи. Примерът показва рекурсивно обхождане, отбелязване на посетените върхове и детерминиран ред на извеждане.
Версия: C23; repository compiler flag, production runtime not attested
Синтаксис
void dfs(int v);Търсенето в дълбочина (depth-first search, DFS) изследва следващия клон, преди да се върне към останалите съседи. Рекурсивното обхождане (recursive traversal) реализира този модел чрез извикване на функцията за непосетените съседи; при връщане от извикване предишният цикъл продължава. Само по себе си DFS не определя кога се обработва даден връх; този пример го извежда при откриването му.
В примера graph[v][u] представлява насочено ребро от v към u. Функцията dfs задава visited[v] преди следващите извиквания, затова цикълът 0 → 1 → 3 → 0 не води до повторно посещаване на 0. Нарастващият ред на u дава 0, 1, 3, 2, 4, всеки на отделен ред. Всички подадени индекси са в диапазона 0–N - 1.
Извикването dfs(0) посещава само върховете, достижими от 0. За да обхванете целия граф, извикайте dfs за всеки все още непосетен връх. Нулирайте visited, преди отново да започнете независимо обхождане.
При матрица на съседство пълното обхождане изисква време O(V²); представянето със списъци на съседство позволява O(V + E), където V и E са броят на върховете и ребрата. Масивът за посетени върхове и стекът на извикванията изискват O(V) допълнителна памет. Дълбоката рекурсия може да изчерпи стека на извикванията; явният стек е алтернатива. Контекстът на хранилището посочва C23 като флаг на компилатора, но не потвърждава производствена среда.
Примери
#include <stdio.h>
enum { N = 5 };
static const int graph[N][N] = {
{0, 1, 1, 0, 0},
{0, 0, 0, 1, 0},
{0, 0, 0, 0, 1},
{1, 0, 0, 0, 0},
{0, 0, 0, 0, 0}
};
static int visited[N] = {0};
static void dfs(int v)
{
visited[v] = 1;
printf("%d\n", v);
for (int u = 0; u < N; ++u) {
if (graph[v][u] && !visited[u]) {
dfs(u);
}
}
}
int main(void)
{
dfs(0);
return 0;
}
Резултат
0 1 3 2 4
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.