[사이클 탐색] 무방향 그래프, 방향 그래프 안 사이클 탐지

무방향 그래프 안 사이클 탐지

1) 유니온-파인드 셋 자료구조 활용

2) DFS 활용

vector<vector<int>> Edges;
vector<bool> visited;

...

bool isCyclicGraph(int node, int parent) {
    visited[node] = true;
    for(int i=0; i<Edges[node].size(); i++) {
    	int nextNode = Edges[node][i];
        if(!visted[nextNode]) {
    		// 처음 방문한 노드
            if(isCyclicGraph(nextNode, node))
            	return true;
        }
        else {
        	// 처음 방문하지 않은 노드
            if(nextNode != parent)
            	// 처음 방문하지 않은 노드인데, 부모노드가 아니라면 사이클이 발생된 것!
                return true;
        }
	
    return false;
}

...

for(int i=1; i<=N; i++){
	int node = i;
    if(visited[node])
    	continue;	// 중복 탐색을 막는다.
        
	if(isCyclicGraph(0, -1))
		// 사이클 밣생!
}

---

방향 그래프 안 사이클 탐지

무방향 그래프 안에서의 사이클 탐색 알고리즘을 쓴다면, 즉 visited 배열을 통해 사이클 탐지를 확인하면 사이클이 아닌 것도 사이클로 식별될 수 있다. 따라서 추가적인 배열이 필요하다.

vector<vector<int>> Edges;
vector<bool> visited;
vector<bool> localVisited;	// 추가적인 배열 필요

...

bool isCyclicGraph(int node, int parent) {
    visited[node] = true;
    // 추가
    localVisited[node] = true;
    
    for(int i=0; i<Edges[node].size(); i++) {
    	int nextNode = Edges[node][i];
        if(!visted[nextNode]) {
    		// 처음 방문한 노드
            if(isCyclicGraph(nextNode, node))
            	return true;
        }
        else {
        	/*
        	// 처음 방문하지 않은 노드
            if(nextNode != parent)
            	// 처음 방문하지 않은 노드인데, 부모노드가 아니라면 사이클이 발생된 것!
                return true;
            */
            
            if(localVisited[nextNode])
            	return true;
        }
	
    // 복구
    localVisited[node] = false;
    
    return false;
}

...

for(int i=1; i<=N; i++){
	int node = i;
    if(visited[node])
    	continue;	// 중복 탐색을 막는다.
        
	if(isCyclicGraph(0, -1))
		// 사이클 밣생!
}