ошибка в коде, приведенном в книге Скиены для применения 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;
    }
}

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


c graph algorithm depth-first-search
person jairaj    schedule 15.12.2012    source источник

Ответы (4)


arrow_upward
7
arrow_downward

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

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

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

person antoniob    schedule 26.05.2013

arrow_upward
1
arrow_downward

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

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

person j_random_hacker    schedule 15.12.2012
comment
в яблочко!! это то, что я думал. Но я просто хочу убедиться. - person jairaj; 15.12.2012
comment
Ну, исправление, конечно, поможет. Я не совсем готов доказать правильность остальной части алгоритма, тем более что я не знаю, что содержит edgenode, как инициализируются discovered и visited, что делает find_path(), какое представление используется для ребер и т. д. - person j_random_hacker; 15.12.2012
comment
Почему бы просто не запустить измененный код на нескольких примерах и сначала посмотреть, как он работает? - person j_random_hacker; 15.12.2012
comment
С изменением опечатки код цикла поиска правильный, потому что он говорит о вершине, на которую указывает это ребро, если она не обнаружена, все в порядке, мы идем вниз по DFS. Если это мой родитель, мы находимся на неориентированном графе, и это нормально. Но если он обнаружен, а не мой родитель, это должно быть заднее ребро и, следовательно, цикл. Хитрость заключается в том, чтобы понять, что этот тест актуален только после того, как вы уже обработали родителя. - person kball; 15.07.2013

arrow_upward
0
arrow_downward

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

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

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

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

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

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

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

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

...

while (p != NULL) {
    y = p.y;

    process_edge(v,y);

    if (discovered[y] == FALSE) {
        parent[y] = v;
        dfs(g,y);
    }

    if (finished) {
        return;
    }

    p = p.next;
}

...
person kball    schedule 15.07.2013
comment
На самом деле код в книге обрабатывает ранее обнаруженные узлы, пока узел не был обработан. - person Mike; 21.01.2016

arrow_upward
0
arrow_downward

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

if (discovered[y] == FALSE)

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

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

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

person saksham jindal    schedule 16.06.2016