[알고리즘][Graph] 싸이클(Cycle) #2 무방향 그래프에서 싸이클이 있는지 탐색

학습목표
1. 무방향 그래프에서 싸이클 탐색을 학습

 

1. 싸이클(Cycle)이란 무엇인가?

그래프의 특정 노드에서 출발하여 방향(Edge)를 따라 다시 출발한 노드로 올 수 있는 상황을 싸이클이 있다고 합니다.

아래의 그림은 싸이클이 있는 그래프와 없는 그래프를 표현한 것입니다. 왼쪽이 싸이클이 존재하는 그래프이고 오른쪽이 싸이클이 존재하지 않는 그래프입니다.

 

2. 무방향 그래프의 싸이클을 탐색하기 위한 접근 방법

무방향 그래프에서 싸이클을 탐색하기 위해서 DFS(Depth First Search) 순회 방법을 이용해서 할 수 있습니다. DFS는 특정 노드에서 시작하여 해당 노드의 인접 노드로 이동하면서 더이상 인접 노드가 없다면 시작 했던 노드로 되돌아가는 재귀적인 순회방법입니다. 

 

싸이클을 탐색하기 위해서 DFS의 매개변수로 parent 변수를 정의합니다. parent 변수의 용도는 특정 노드에 방문하였을때 이전에 방문했던 노드의 번호를 저장합니다. 아래 그림에서 0번 노드의 인접 노드인 1번 노드로 이동하였을 때 방문 노드는 1번 노드, parent 변수는 0을 가리킵니다. 만약 0번 노드에서 시작한다면 parent는 -1로 초기화되어 시작합니다.

 

parent 변수를 활용하여 싸이클을 탐색할 수 있습니다. 방법은 특정 노드에 방문하였고 인접 노드를 탐색하는 과정에서 인접 노드가 이미 방문하였고 해당 인접노드의 번호가 parent 변수와 다르다면 싸이클이 발생한 것이므로 true를 반환합니다.

 

예를 들어 0번 노드에서 DFS 순회를 하였다고 가정하고 1번노드->2번노드로 이동합니다.

2번 노드에서 인접노드는 0번, 1번 노드입니다. 그리고 2번 노드 방문 당시에는 parent는 1이 저장되어 있습니다. 인접 노드 0번은 이미 방문되었고 parent=1과 다르므로 싸이클이 발생했다 볼 수 있습니다.

 

정리하면 위와같이 DFS 순회도중 방문한 노드를 기준으로 인접노드 번호와 parent 변수를 비교하여 인접노드가 이미 방문하였고 parent변수와 다르다면 싸이클이 발생한 것으로 간주하여 true를 반환하면 됩니다.

 

3. 무방향 그래프의 싸이클 탐색 알고리즘 수행과정

 

4. Java 언어 기반 무방향 그래프 싸이클 탐색 알고리즘 구현

public class UnDirectedGraph<E> implements Graph<E>{
	private int V; // 노드 개수
	private ArrayList<ArrayList<Node<E>>> adj;	// 인접리스트
	private Map<Integer,E> map;
	
	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>();
	}
	
	public boolean isCyclic()
	{
		boolean[] visited = new boolean[V];
		int parent = -1;
		
		for(int i=0;i<V;i++)
		{
			if(!visited[i])
			{
				if(isCyclicUtil(i, visited, parent))
				{
					return true;
				}
			}		
		}
		return false;
	}
	
	private boolean isCyclicUtil(int i, boolean[] visited, int parent)
	{
		visited[i] = true;	
			
		Iterator<Node<E>> itor = adj.get(i).iterator();
		
		while(itor.hasNext())
		{
			int adjNode = itor.next().getNum();
			if(!visited[adjNode])
			{
				if(isCyclicUtil(adjNode, visited, i))
				{
					return true;
				} 
			}
			else if(adjNode!=parent)
			{
				return true;
			}	
		}
		return false;
	}
	
	@Override
	public void addEdge(Node u, Node v) {
		if(!map.containsKey(u.getNum()))
		{
			map.put(u.getNum(), (E) u.getValue());
		}
		if(!map.containsKey(v.getNum()))
		{
			map.put(v.getNum(), (E) v.getValue());
		}
		
		adj.get(u.getNum()).add(v);
		adj.get(v.getNum()).add(u);
	}
	
	public static void main(String[] args)
	{
		int V = 5;
		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);
		Node<Integer> node3 = new Node<Integer>(3, 3);
		Node<Integer> node4 = new Node<Integer>(4, 4);
		
		unDirectedGraph.addEdge(node0, node1);
		unDirectedGraph.addEdge(node0, node2);
		unDirectedGraph.addEdge(node0, node3);
		unDirectedGraph.addEdge(node1, node2);
		unDirectedGraph.addEdge(node3, node4);
		
		
		if(unDirectedGraph.isCyclic())
		{
			System.out.println("이 그래프는 싸이클이 존재합니다.");
		}
		else
		{
			System.out.println("이 그래프는 싸이클이 존재하지 않습니다.");
		}
		
		           
	}
}

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

 

5. 무방향 그래프 싸이클 탐색 시간복잡도

• 시간복잡도 : O(V+E), V는 정점의 개수, E는 간선의 개수를 의미합니다. DFS 순회를 이용하기 때문에 V개의 정점들을 방문하고 인접노드 탐색으로 인하여 최악의 경우 E개의 개수만큼 간선을 확인합니다.
• 공간복잡도 : O(V), V는 정점의 개수를 의미합니다. 방문 배열(visited)에 정점의 개수만큼의 공간이 필요합니다.

 

References

source code : https://github.com/yonghwankim-dev/inflearn_algorithm/tree/master/graph/graph05_iscycle
Geeks For Geeks : https://www.geeksforgeeks.org/detect-cycle-undirected-graph/