무방향 그래프와 방향 그래프
무(無)방향 그래프
- 서로소 집합은 공통 원소가 없는 두 집합을 의미한다.
- find함수는 해당 노드의 root 노드를 찾는 함수이다.
- union은 두 노드가 속한 집합을 합치는 함수이다.
- 만약 root 노드가 같다면, 이는 사이클이 존재함을 의미한다.
def find(x, parent):
if x != parent[x]:
parent[x] = find(parent[x], parent)
return parent[x]
def union(a,b,parent):
a = find(a, parent)
b = find(b, parent)
parent[max(a,b)] = min(a,b)
방향 그래프
- 방문 여부를 확인하는 visited, 현재 탐색 경로를 나타내는 stack을 노드의 개수만큼 정의한다.
- 모든 노드에 대해 dfs를 수행한다.
- 해당 노드의 이웃 노드들을 확인하면서, 재귀적 탐색의 결과가 True거나 stack에 이미 있는 경우, 사이클이 존재한다.
- 모든 이웃 노드에 대해 탐색 후 False라면, 사이클이 없으므로 stack에서 해당 노드를 제외한다.
def dfs(node, visited, stack):
visited[node] = True
stack[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
if dfs(neighbor, visited, stack):
return True
elif stack[neighbor]:
return True
stack[node] = False
return False
visited = [False] * num_nodes
stack = [False] * num_nodes