[그래프] 유니온 파인드 & 위상 정렬

 

 

그래프의 표현

그래프를 구현하는 방법에는 3가지가 있다.

1. 에지 리스트로 가중치 있는 그래프 표현하기 : 에지 중심 표현 방법, S - E - V

2. 인접 행렬로 가중치 없는 그래프 표현하기 : 바둑판처럼 2차원 배열을 자류구조로 이용해 그래프로 표현한다. (가중치가 있다면 가중치를 2차원 배열에 넣어주면 됨), 에지를 탐색하려면 N번 접근해야 하므로 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어짐

3. <중요> 인접 리스트로 가중치 없는 그래프 표현하기 : ArrayList<Integer>[]로 선언. 가중치가 있는 경우에는 Node라는 클래스를 만들어 ArrayList<Node>[]를 선언한다. 

 

 

유니온 파인드는 일반적으로 여러 노드가 있을 때, 특정 2개의 노드를 연결해 3개의 집합으로 묶는 union연산과 두 노드가 같은 집합에 속해 있는지 확인하는 find연산으로 구성되어있는 알고리즘이다. 그래프에서 유니온 파인드는 그래프의 사이클이 생성되는지 판별하는 알고리즘으로 사용된다. 유니온 알고리즘에서는 대표 노드끼리 연결해주어야 한다. -> find 연산 이용!  

 

출처 하루 코딩

 

위상 정렬은 사이클이 없고 방향이 있는 그래프에서 사용되는 알고리즘이다. 수강신청을 구현할 때 사용할 수 있는 알고리즘이라고 한다.