그래프에 재귀 DFS를 사용하는 사이클이 있는지 찾는 방법은 무엇입니까?

Question

아래 코드는 유향 그래프에주기가 있는지 여부를 확인하기 위해 깊이 우선 검색 DFS를 구현 한 것입니다. 그러나 작동하지 않으므로 버그가있는 것으로 보입니다. 나는 버그가 if (visited[w]) 상태에 있다는 것을 거의 100 % 확신합니다. 여기에 내 논리는 기본적으로 - 노드가 이미 방문한 경우 사이클이 존재합니다. 그러나 if (visited[w])의 문제점은 조건이 true 일지라도 노드가 오래 전에 방문되었을 수 있으므로 반드시주기가 있음을 의미하지는 않습니다.

int *visited; // array [0..V-1] of booleans 

int checkCycle(Graph g) 
{ 
    visited = malloc(sizeof(int)*g->numVertices); 
    int result = dfsCycleCheck(g, 0); 
    free(visited); 
    return result; 
} 
int dfsCycleCheck(Graph g, Vertex v) 
{ 
    visited[v] = 1; 
    Vertex w; 
    for (w = 0; w < nV(g); w++) { 
     if (!hasEdge(g,v,w)) continue; 
     if (visited[w]) return 1; // found cycle 
     return dfsCycleCheck(g, w); 
    } 
    return 0; // no cycle 
} 

Answer 1

당신은 방문 노드가 이미 방문한 된 경우 또는 현재 탐색의 일환으로 방문한 경우 알 수있는 방법이 없다는 것을 정확합니다.

하나의 접근법은 우리가 이미 가지고있는 두 가지 상태 대신에 세 가지 상태를 유지할 수있는 꼭지점 배열을 유지하는 것입니다.

화이트 : 꼭지점이 아직 처리되지 않았습니다. 처음에는 모든 정점이 흰색입니다.

GRAY : 정점 시작이 정점 (DFS 처리했지만 의미 완료되지되는 이 정점 의 모든 자손 (IND DFS 트리)가 아직 처리되지 않은 (또는 버텍스 기능 호출되어 스택)

BLACK :. 정점 및 모든 자손 이 처리

우리가 GRAY 정점 현재의 정점에서 에지가 발생하면 DFS를 수행하는 동안,이 가장자리는 뒤쪽 가장자리이며 그러므로 존재 사이클

코드는 다음과 같습니다.

// Recursive function to find if there is back edge 
// in DFS subtree tree rooted with 'u' 
bool Graph::DFSUtil(int u, int color[]) 
{ 
    // GRAY : This vertex is being processed (DFS 
    //   for this vertex has started, but not 
    //   ended (or this vertex is in function 
    //   call stack) 
    color[u] = GRAY; 

    // Iterate through all adjacent vertices 
    list<int>::iterator i; 
    for (i = adj[u].begin(); i != adj[u].end(); ++i) 
    { 
     int v = *i; // An adjacent of u 

     // If there is 
     if (color[v] == GRAY) 
      return true; 

     // If v is not processed and there is a back 
     // edge in subtree rooted with v 
     if (color[v] == WHITE && DFSUtil(v, color)) 
      return true; 
    } 

    // Mark this vertex as processed 
    color[u] = BLACK; 

    return false; 
} 

// Returns true if there is a cycle in graph 
bool Graph::isCyclic() 
{ 
    // Initialize color of all vertices as WHITE 
    int *color = new int[V]; 
    for (int i = 0; i < V; i++) 
     color[i] = WHITE; 

    // Do a DFS traversal beginning with all 
    // vertices 
    for (int i = 0; i < V; i++) 
     if (color[i] == WHITE) 
      if (DFSUtil(i, color) == true) 
       return true; 

    return false; 
} 

여기에서 주된 차이점은 노드가 될 아직 방문 할 수 있다는 어느 노드가 현재의 탐색의 일환으로 방문 된 지시 ((노드가 이전에 방문되었음을 나타내는) 흑색 또는 회색 그래서 우리가주기가 있는지 없는지 알아내는 데 도움이됩니다.

두 가지 유형의 방문 노드를 구분하지 않은 부울 배열로 인해 이전에는 불가능했던 것이있었습니다.

Source