Skienna DFSアルゴリズム

Question

以下はSkiena'aアルゴリズム設計マニュアルで提供されているDFSコードです。私はprocessed[y]が今までのコードでは、この時点でtrueすることは可能ですかを確認することができません

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

：

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

単に次のようになります。

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

私はチェックがあることを感じます。無向グラフ上のDFSでは、処理済とマークされたノードはすでにすべての子孫を処理しているため、コードのその時点で、未処理ノードからのエッジでyに到達しているという事実だけがy既に処理されています。 Skienaのコードが正しい場合に、processed[y]のチェックが正確である必要がある場合、私はここで何が分からないのですか？その条件が必要な場合の例を提示できますか？想像できませんか？

Answer 1

必要です。グラフを3つの頂点の無向ループとする。 DFSは次の順序で行くことができる

：1 - > 2 - 私たちは（2と3を処理した後）バック1に行くとき> 3、そこ3に縁があるが、3が処理されたので、チェック必要です。

Answer 2

//インポートに必要なライブラリファイル

パブリッククラス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 
} 

}