ошибка в коде, приведенном в книге лысена для применения dfs, чтобы найти цикл на графике

Это код для dfs.

bool processed[MAXV+1]; /* which vertices have been processed */ bool discovered[MAXV+1]; /* which vertices have been found */ int parent[MAXV+1]; /* discovery relation */ #define MAXV 1000 /* maximum number of vertices */ typedef struct { int y; /* adjacency info */ int weight; /* edge weight, if any */ struct edgenode *next; /* next edge in list */ } edgenode; typedef struct { edgenode *edges[MAXV+1]; /* adjacency info */ int degree[MAXV+1]; /* outdegree of each vertex */ int nvertices; /* number of vertices in graph */ int nedges; /* number of edges in graph */ bool directed; /* is the graph directed? */ } graph; dfs(graph *g, int v) { edgenode *p; /* temporary pointer */ int y; /* successor vertex */ if (finished) return; /* allow for search termination */ discovered[v] = TRUE; time = time + 1; entry_time[v] = time; process_vertex_early(v); p = g->edges[v]; while (p != NULL) { y = p->y; if (discovered[y] == FALSE) { parent[y] = v; process_edge(v,y); dfs(g,y); } else if ((!processed[y]) || (g->directed)) process_edge(v,y); if (finished) return; p = p->next; } process_vertex_late(v); time = time + 1; exit_time[v] = time; processed[v] = TRUE; } 

И для нахождения циклов он изменил функцию края процесса, как показано ниже

 process_edge(int x, int y) { if (parent[x] != y) { /* found back edge! */ printf("Cycle from %d to %d:",y,x); find_path(y,x,parent); printf("\n\n"); finished = TRUE; } } 

Теперь представьте небольшое дерево с двумя листами и одним корнем. Когда это дерево подвергается этой функции, я верю, что это скажет, что у нее есть циклы. что неправильно! Пожалуйста, поправьте меня, если я ошибаюсь. Благодарю.

    Из исправления исправления, по адресу http://www.cs.sunysb.edu/~skiena/algorist/book/errata :

    (*) Страница 173, процедура process_edge – правильный тест должен быть

    if (discovered[y] && (parent[x] != y)) { /* found back edge */

    Я думаю, вы правы, и код неправильный.

    Мне кажется, что проблема заключается в if (parent[x] != y) в process_edge() . В обоих вызовах process_edge() предполагаемый родитель передается перед предполагаемым дочерним process_edge() , то есть внутри process_edge() мы ожидаем, что x будет родителем, поэтому я думаю, что строка должна быть if (parent[y] != x) .

    К сожалению, я думаю, что этот код dfs просто неверен. Прошло много времени с тех пор, как я подробно изучил этот материал, но я думаю, что ясно, что код просто не делает того, что он говорит.

    Код цикла поиска правильный (с изменением, указанным в исправлениях, как отмечено Антонио).

    Основная проблема заключается в том, что процедура цикла поиска находится в process_edge, но он не обрабатывает ребра до ранее обнаруженных узлов! Так как он найдет цикл ?! Если вас интересуют циклы (или задние края по какой-либо причине), я должен подумать, что вы ДОЛЖНЫ обрабатывать все ребра.

    Если вас не интересуют задние края и вы хотите их не обрабатывать, то приведенный код верен.

    Искренне иронично, что в отрывке, непосредственно предшествующем разделу «Поиск циклов» в тексте, он пишет:

    Я нахожу, что тонкость алгоритмов, основанных на глубине первого поиска, ударяет меня по голове, когда я пытаюсь ее реализовать.

    Вы не говорите! :П


    Цикл while должен выглядеть примерно так:

     ... while (p != NULL) { y = py; process_edge(v,y); if (discovered[y] == FALSE) { parent[y] = v; dfs(g,y); } if (finished) { return; } p = p.next; } ... 

    В неориентированных графах есть только дерево и обратные края (без перекрестных или перекрестных ребер). Достаточным условием того, что это ребро дерева, является

     if (discovered[y] == FALSE) 

    Но в случае обнаруженных вершин существует вероятность того, что неориентированный край вернется к родительскому (вместо его предка). Чтобы предотвратить этот случай, добавляется другое условие:

     if (discovered[y]==TRUE && (parent[x] != y)) 

    Например: y было обнаружено через x (скажем). Когда рекурсивный алгоритм перемещается к вершине y (дочерний элемент из x), в этом случае вершина X теперь является вершиной y, а вершина Y является родительской (y) (или x!). Если второе условие удалено, существует вероятность того, что алгоритм обнаруживает ребро, идущее от дочернего (y) к его родительскому (x) (на неориентированном графе), как ребро, возвращающееся к одному из прежних предков, что совершенно неверно.