[그래프] 사이클 찾기

1. 사이클을 이루는 정점 확인

1) BFS

bool findCycle(int here, int depth) {
	stack<int> s;

	// 사이클을 만나면 while문 종료
	while (visit[here] == 0) {
		s.push(here);
		visit[here] = depth++;		
		here = node[here];
	}

	// cnt: 사이클 크기
	int cnt = depth - visit[here];	
	cycle[here] = true; 

	// 사이클에 포함되는 정점들을 마킹
	while (cnt > 0) {
		int item = s.top();
		s.pop();
		cycle[item] = true;
		cnt--;
	}

	return cycle[here];
}

2) DFS

int cnt;

bool findCycleDfs(int here, int depth) {
        visit[here] = depth;
        int next = node[here];
        
        if (visited[next] > 0) {
            cnt = depth - visit[next];
            cycle[next] = true;            
            return cycle[next];
        }                
        
        if (findCycleDfs(next, depth + 1) && cnt > 0) {
            cycle[next] = true;
            cnt--;
        }
        
        return cycle[next];
    }

 

2. 사이클 존재 여부만 확인

1) 최소신장트리(MST)

  - findParent 으로 부모가 동일하지 않은 정점만 연결 (이것을 카운팅)

  - 모든 정점을 방문하지 못하는 경우, 간선의 개수가 N-1 이 아니다.

  - 크루스칼 알고리즘, union-find 이용

int kruskal()
{
    // 간선의 비용을 기준으로 오름차순 정렬
    sort(v.begin(), v.end());
 
    int sum = 0;
    int selected = 0;
 
    for (int i = 1; i < v.size(); i++) {
        // 사이클이 발생하지 않는 경우 그래프에 포함
        if (!findParent(v[i].from, v[i].to)) {
            sum += v[i].dist;
            selected++;
            unionParent(v[i].from, v[i].to);
        }
    }
 
    // 간선의 수 != (정점의 수 - 1)인 경우, 연결 불가능한 정점이 있음
    return selected == (n - 1) ? sum : -1;
}

 

2) 위상정렬 이용

  - 모든 노드를 방문하기 전에 큐가 빈다면, 사이클이 존재한다고 판단

  - BFS + indegree 개수

void topologySort()
{
    // indegree = 0 인 노드를 큐에 삽입
    for (int i = 1; i <= N; i++) {
        visited[i] = 0;
        if (indegree[i] == 0) {
            q.push(i);
        }
    }
 
    // 큐가 빌 때까지 수행
    while (!q.empty()) {
        int x = q.front();
        q.pop();
 
        for (Edge y : adj[x]) {
            // 큰 값 채택 : 다음번 노드에 이미 저장된 비용 vs 현재 큐 진행시 비용(current + next.cost)
            result[y.node] = max(result[y.node], result[x] + y.cost);
            if (--indegree[y.node] == 0) {
                q.push(y.node);
            }
        }
    }
}