graph - ¿Cómo evitar reprocesar el mismo borde dos veces en la primera búsqueda de profundidad?

Question

El Algorithm Design Manual describe BFS y DFS bastante bien. El código para dfs en el libro tiene un problema cuando se decide si evitar o no el doble procesamiento de bordes. Encontré el Errata y apliqué la errata al código, pero aún así creo que el código refinado tiene un problema para verificar los bordes de doble procesamiento.

que pegar el código refinado de la siguiente manera:

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; 
} 

El lugar donde creo que hay un problema se marca a través ** **.

Así que el lugar cuestionable es una de las condiciones. Supongamos que es un gráfico no dirigido, por lo que podemos ignorar la condición de (g->directed).

Ok, centrémonos primero en parent[v] != y. si parent[v] == y, por supuesto, no necesitamos procesar el borde v-> y otra vez porque y-> v ya se procesa una vez cuando se procesa el vértice y.

Y si parent[v] != y, mi pregunta es si !processed[y] && es necesario o no.

Por lo tanto, si y no es el padre de v, y processed[y] == false lo que significa y se ha encontrado (en caso contrario la ejecución no puede llegar else if parte), pero no ha procesado, Y debe ser una abuela o por encima de v. Esto es un borde posterior, pero no hay problema, podemos procesarlo ya que aún no se ha procesado.

¿Y ahora qué pasa si processed[y] == true? Creo que esto "si" nunca sucederá y esta condición nunca será cierta.

¿Por qué? Bien, supongamos que processed[y] puede ser cierto. Esto significa que todas las rutas que incluyen y han sido procesadas y también todos los vértices en esas rutas han sido procesadas, ¿verdad? Entonces, si este es un caso, ¿cómo puede un "vértice v" aún no terminado de abordar el enfoque y?

Creo que en dfs, ningún vértice se acercará a un vértice procesado, ¿estoy bien?

Así que si nunca vamos a procesar un vértice procesado, simplemente podemos eliminar !processed[y] ya que siempre será cierto.

Answer 1

No, processed[y] == true podría dar un resultado verdadero.

vistazo a la siguiente gráfica, y asumir la siguiente [factible] DFS traversal:

v0,v1,v2 

v0 se inicia y, a continuación invocar de forma recursiva dfs(v1) después de procesar (v0,v1). Ahora, v1 procesa (v1,v2) e invoca recursivamente dfs(v2). v2 ve que se descubre v0 y vaya a la instrucción else if, y ve que (v0,v2) no se procesó y parent[v2] != v0 [v2 se descubrió a través de v1].

Ahora, cuando regresemos de la recursividad alcanzamos v0, y cuando revisamos el siguiente "hijo" - es v2. v2 ya fue descubierto, así que vamos a else if, y v2 no es el padre de v0, por lo que sin la parte !processed[y], habríamos procesado (v0,v2) dos veces.

La única cosa que evitar que eso hapenning es el hecho de que processed[y] == true