Graph 사이클 찾기

back_edge가 존재하면 사이클이 존재한다는 얘기

 

Q. 그래프에서 사이클이 이란 ?

그래프의 특정 정점에서 출발하여 돌아다니다가 다시 처음 출발했던 곳으로 되돌아 갈 수 있으면 사이클이 있다고 한다.

그림1에서 (a)는 Tj(출발) → Tn → Tm → Tj(출발지점으로 다시 돌아옴) 으로 순환되는 사이클이 있지만 (b)는 어디에서 출발하던 출발지점으로 다시 돌아올수 있는 방법이 없다. 즉 사이클이 존재하지 않는다.

Q. 사이클을 찾는다는 것은?

사이클을 검출(detect) 한다는 것은 그래프내에 사이클이 있는가? 있다면 총 몇 개 존재하는가 ? 그리고 사이클에 포함된 노드의 개수는 몇 개인가? 등을 알아내는 것이다.

어떠한 이유로 그래프 자료구조를 이용해 다양한 문제를 풀다보면 그래프내 사이클을  찾는 알고리즘들이 필요하게 된다.

예를들어 최소신장트리 - MST를 생성하려면 그래프내 사이클이 없어야 하는데 MST를 생성하는 알고리즘 중 하나인 크러스컬(Kruskal) 알고리즘 에서도 필요하다.

 

Q. 서로수집합(Disjoint Set) - 합집합-찾기(union–find) 으로 사이클 검출이 가능하다고 하던데 ?

Disjoin Set에 대해서 모르면 우선 서로수집합(Disjoint Set) - 합집합-찾기(union–find)를 반드시 선행 학습해야 한다.

서로수 집합의 원소를 정점(or 노드)라고 하면 같은 집합(subgraph)에 포함되어 있는 정점들끼리는 이미 에지로 연결된 것들이고 다른 집합(subgraph)에 있는 정점과는 서로 연결되어 있지 않다는 것을 기반으로 한다.  

 

Q. DFS깊이우선탐색(DFS, Depth First Search) 로 사이클 검출이 가능하다고 하던데 ?

DFS를 모르면 우선 DFS깊이우선탐색(DFS, Depth First Search)를 선행 학습해야한다.

dfs는 그래프의 모든 정점을 에지의 방향에 따라 순회하면서 백에지(bak dege)가 있으면 사이클이 있다고 판단한다.

 

 

 

[그래프] 그래프에서 사이클 찾는 방법들(Detect Cycle in an Graph)

---

• 간선의 분류를 이용하면 방향 그래프에서 사이클이 존재하는지 쉽게 알 수 있다.
  • 사이클의 존재 여부는 역방향 간선의 존재 여부와 동치이다.
• 탐색 과정
  • 어떤 그래프에서 깊이 우선 탐색 중 만나는 한 정점을 u라고 하자.
  • dfs(u)는 u에서 갈 수 있는 모든 정점들을 방문한 후에 종료된다.
  • 따라서, u이전에 있는 한 정점이 dfs(u)가 종료되기 전에 u정점을 방문을 한다면, 해당 정점은 u로 가는 역방향 간선이 된다.
  • 결과적으로, 이 그래프는 사이클이 존재하는 그래프가 된다.

 

 

[알고리즘] 그래프(Graph)에서 사이클(Cycle) 찾기

---

사이클 출력하기

 

 

Print all the cycles in an undirected graph - GeeksforGeeks