Algorithme Skienna DFS

Question

Vous trouverez ci-dessous le code DFS fourni dans le manuel Skiena'a Algorithm Design.

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] && (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; 
} 

Je me sens que le chèque:

else if ((!processed[y] && (parent[v]!=y)) || (g->directed)) 
    process_edge(v,y); 

pourrait simplement:

else if ((parent[v]!=y) || (g->directed)) 
    process_edge(v,y); 

Je ne peux pas voir comment il est possible pour processed[y] à jamais true à ce point dans le code . Dans un DFS sur un graphe non orienté, un noeud marqué traité aurait déjà parcouru tous ses descendants, donc juste le fait qu'à ce point dans le code nous atteignons y via un bord d'un noeud non encore traité, il est impossible pour y de être déjà traité. Si le code Skiena est correct, et que la vérification processed[y] est nécessaire pour l'exactitude, qu'est-ce qui me manque ici? Pouvez-vous présenter un exemple où cette condition est nécessaire - je suis incapable d'en imaginer un?

Answer 1

C'est nécessaire. Soit le graphe une boucle non orientée de trois sommets.

Les DSF peuvent aller dans l'ordre suivant: 1 -> 2 -> 3. Lorsque nous revenons à 1 (après traitement 2 et 3), il y a un avantage à 3, mais 3 a été traitée, de sorte que le chèque est nécessaire.

Answer 2

// fichiers de bibliothèque d'importation requis

public class ArrayTest {

// 2d array matrix declaration 
// size variable declaration for rows or columns of array 

ArrayTest() {  
    // initialize size 
} 

public static void main(String[] args) { 
    //create object of ArrayTest class and call member functions in correct order 
} 

public void fillMatrix() { 
    // fill the 2D arry with random number between 10 to 99. 
} 

void countPrimes() { 
    // count the prime numbers and display total count 
} 

public boolean isPrime(/* number need to check*/) { 
    // check number sent through argument is prime or not 
} 

}