[알고리즘][Graph] Disjoint Set #1 무방향 그래프에서 싸이클 탐색

학습목표
1. Disjoint Set 자료구조에 대해서 학습
2. Disjoint Set 자료구조를 이용하여 그래프에 싸이클이 있는지 검사

1. Disjoint-Set 자료구조란 무엇인가?

Disjoint-Set 자료구조는 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조입니다. 예를 들어 집합 {1,2,3}과 집합 {4,5}는 서로 중복되는 원소가 없으므로 Disjoint-Set입니다. 

 

2. Union-Find 알고리즘 수행과정

union-find 알고리즘은 disjoint-set 자료구조에 대해 2가지 유용한 연산을 수행하는 알고리즘입니다.

• Find : 특정 원소가 어느 부분집합인지 탐색합니다. Find 기능은 두개의 원소가 서로 같은 부분집합인지 확인하는데 사용됩니다.
• Union : 두 부분집합을 하나의 부분집합으로 합칩니다. 단, 두 부분집합은 서로 다른 부분집합이어야 합니다.

Union-Find 알고리즘은 무방향 그래프가 싸이클을 포함하는지 안하는지 검사하는데 사용될 수 있습니다. 이 방법은 그래프의 노드가 자기 자신을 가리키지 않는다는 것을 가정합니다.

 

Find와 Union 연산을 수행하는데 parent라는 이름의 1차원 배열을 사용합니다. 이 배열은 특정 원소의 부모가 누구인지 알려주는 배열입니다. parent 배열을 이용하여 각각의 원소가 어느 부분집합에 속하는지 알 수 있습니다.

 

Union-Find 알고리즘의 수행과정은 다음과 같습니다.

1. parent 배열을 노드의 개수만큼 -1로 초기화합니다.
2. 무방향 그래프에 노드들간의 존재하는 에지(Edge)들을 순회합니다.
3. 한 에지에 대한 두 노드(u,v)들이 어느 부분집합에 속하는지 탐색합니다. (find 연산)
   1. 만약 u, v 노드의 속한 부분집합이 서로 다르다면 에지로 연결되어 있지만 부분집합이 서로 다른 상태이므로 두 노드는 같은 부분집합에 속해야 합니다. 따라서 union 연산을 통하여 합집합 할 수 있도록 합니다. (union 연산)
   2. 만약 u,v 노드의 속한 부분집합이 서로 같다면 사이클이 발생한 것이므로 true를 반환합니다.
4. 3번 과정을 다 수행(모든 에지 순회)하였음에도 서로가 속한 부분집합이 달라서 union만 수행하였다면 싸이클이 발생하지 않았으므로 false를 반환합니다.

 

Union-Find 알고리즘의 수행과정을 그림으로 표현하면 다음과 같습니다.

 

3. Java언어 기반 Union-Find 알고리즘 구현

public interface Graph<E> {
	static class Node<E>{
		int num;	// 노드 번호
		E value;	// 노드 값
		
		public Node(int num, E value) {
			this.num = num;
			this.value = value;
		}
	}
	static class Edge{
		int src, dest;
		public Edge(int src, int dest) {
			this.src = src;
			this.dest = dest;
		}

	}
	
	public void addEdge(Node<E> u, Node<E> v);
	public int find(int[] parent, int i);
	public void union(int[] parent, int u, int v);
	public boolean isCycle();
}

public class UnDirectedGraph<E> implements Graph<E>{
	private int V; // 노드 개수
	private ArrayList<ArrayList<Node<E>>> adj;	// 인접리스트
	private Map<Integer,E> map;
	private ArrayList<Edge> edges;
	
	public UnDirectedGraph(int v) {
		V = v;
		adj = new ArrayList<ArrayList<Node<E>>>(v);
		for(int i=0;i<v;i++)
		{
			adj.add(new ArrayList<Node<E>>());
		}
		map = new HashMap<Integer, E>();
		edges = new ArrayList<Edge>();	
	}
	
	@Override
	public void addEdge(Node u, Node v) {
		if(!map.containsKey(u.num))
		{
			map.put(u.num, (E) u.value);
		}
		if(!map.containsKey(v.num))
		{
			map.put(v.num, (E) v.value);
		}
		
		adj.get(u.num).add(v);
		adj.get(v.num).add(u);

		edges.add(new Edge(u.num,v.num));
	}

	@Override
	public int find(int[] parent, int i) {
		if(parent[i]==-1)
		{
			return i;
		}
		return find(parent, parent[i]);
	}

	@Override
	public void union(int[] parent, int u, int v) {
		parent[u] = v;
	}

	@Override
	public boolean isCycle() {
		int[] parent = new int[V];
		
		for(int i=0;i<V;i++)
		{
			parent[i] = -1;
		}
		
		for(int i=0;i<edges.size();i++)
		{
			Edge edge = edges.get(i);
			
			int u = find(parent, edge.src);
			int v = find(parent, edge.dest);
			
			if(u==v)
			{
				return true;
			}
			union(parent, u, v);
		}
		return false;
	}	
}

public class Driver {

	public static void main(String[] args) {
		int V = 3;
		UnDirectedGraph<Integer> unDirectedGraph = new UnDirectedGraph<Integer>(V);
		
		Node<Integer> node0 = new Node<Integer>(0, 0);
		Node<Integer> node1 = new Node<Integer>(1, 1);
		Node<Integer> node2 = new Node<Integer>(2, 2);
		
		
		unDirectedGraph.addEdge(node0, node1);
		unDirectedGraph.addEdge(node0, node2);
		unDirectedGraph.addEdge(node1, node2);
		
		if(unDirectedGraph.isCycle())
		{
			System.out.println("이 그래프는 싸이클이 존재합니다.");
		}
		else
		{
			System.out.println("이 그래프는 싸이클이 존재하지 않습니다.");
		}
	}

}

이 그래프는 싸이클이 존재합니다.

 

References

source code : https://github.com/yonghwankim-dev/inflearn_algorithm/tree/master/graph/graph06_disjointset_unionfind
Geeks For Geeks : https://www.geeksforgeeks.org/union-find/