graph - Как избежать повторной обработки одного и того же ребра дважды при поиске в глубину?

В Руководстве по проектированию алгоритмовдовольно хорошо описаны BFS и DFS. Код для dfs в книге имеет проблему при принятии решения о том, следует ли избегать двойной обработки ребер. Я нашел Errataи применил исправления к коду, но все же я думаю, что в усовершенствованном коде есть проблема с проверкой двойных границ обработки.

Я вставляю уточненный код следующим образом:

dfs(graph *g, int v) {
       edgenode *p;
       int y;
       if (finished) return;
       discovered[v] = TRUE;
       time = time + 1;
       entry_time[v] = time;
       process_vertex_early(v);
       p = g->edges[v];
       while (p != NULL) {
             /* temporary pointer */
             /* successor vertex */
             /* allow for search termination */
             y = p->y;
             if (discovered[y] == FALSE) {
                   parent[y] = v;
                   process_edge(v,y);
                   dfs(g,y);
             }
             else if (**(!processed[y] && parent[v] != 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;
}

Место, где я думаю, что есть проблема, помечено через ** **.

Таким образом, сомнительное место является одним из условий. Предположим, что это неориентированный граф, поэтому мы можем просто игнорировать условие (g->directed).

Хорошо, давайте сначала сосредоточимся на parent[v] != y. если parent[v] == y, конечно, нам не нужно снова обрабатывать ребро v->y, потому что y->v уже обрабатывается один раз при обработке вершины y.

И если parent[v] != y, мой вопрос заключается в том, необходим ли !processed[y] &&или нет.

Итак, если y не является родителем v и обработано[y] == false, это означает, что y найдено (иначе выполнение не может достичь части , else if) но не обработано, поэтому y должно быть бабкой или выше v. Это задний край, но нет проблем, мы можем его обработать, так как он еще не обработан.

А что, если обработано[y] == true? Я думаю, что это «если» никогда не произойдет, и это условие никогда не будет истинным.

Почему? Хорошо, давайте предположим, что processed[y]может быть правдой. Это означает, что все пути, которые включают y, были обработаны, а также все вершины в этих путях, верно? Итак, если это так, то как «еще не законченная обработка» вершины v может приблизиться к y?

Я думаю, что в dfs ни одна вершина никогда не приблизится к обрабатываемой вершине, я прав?

Так что, если мы никогда не будем обрабатывать обработанную вершину, мы можем просто удалить !processed[y], поскольку она всегда будет истинной.