그래프에서 DFS로 사이클 찾기

 그래프를 구현하는 방법에는 인접행렬과 인접리스트가 있다. 그 중 인접리스트를 통해 그래프를 구현하려고 한다.

아래는 예시그래프와 그래프의 정점과 정점 사이의 관계를 그림으로 그려보았다.

  구현하면 다음과 같다.

class Graph {
	private ArrayList<ArrayList<Integer>> graphList;
	
	public Graph(int size) {
		this.graphList = new ArrayList<ArrayList<Integer>>();
		
		for(int i=0; i<size; i++) {
			this.graphList.add(new ArrayList<Integer>());
		}
	}
	
	public void put(int v1, int v2) { //무방향 그래프
		graphList.get(v1).add(v2);
		graphList.get(v2).add(v1);
	}
	
	public ArrayList<Integer> get(int v){
		return graphList.get(v);
	}
}

private static Graph graph;
public static void main(String[] args) throws Exception {

	//예시그래프 생성
	graph = new Graph(4);
	graph.put(1, 2);
	graph.put(1, 3);
	graph.put(1, 4);
	graph.put(2, 1);
	graph.put(3, 1);
	graph.put(3, 4);
	graph.put(4, 1);
	graph.put(4, 3);
        
}

 

 DFS 탐색 방법은 여러가지가 있지만 여기서는 이동할 때 부모노드를 기억하는 방식으로 탐색한다. 내가 탐색할 다음 노드가 부모노드하고 같다면 방금 지나온 길이니 넘기고 탐색을 계속하는 방식이다. 

DFS 탐색 전개 순서 그림

public static boolean dfs(int currentNode, int parentNode) {

	for(int nextNode : graph.get(currentNode)) { //탐색 시작
		if(nextNode == parentNode) { //이미 지나온 경로
			continue; 
		}else if(dfs(nextNode, currentNode)) { //탐색 진행
			return true;
		}
	}
	return false;
    
}

 

 이제 DFS탐색에서 사이클을 찾아내야 한다. 사이클을 찾아내기 위해서는 내가 방문한 노드들을 기억하고 있어야 한다. DFS 탐색이 정상적으로 진행되고 있다면, 다음노드가 부모가 아닌데 이미 한 번 방문한 노드일 경우 사이클이 발생한 것이다.

private static int[] visited; //방문했는지를 기억하기 위한 리스트 변수 추가
private static ArrayList<Integer> cyclePath; //사이클 경로 담을 변수 추가

public static boolean dfs(int currentNode, int parentNode) {
	if(visited[currentNode] != -1) { //이미 방문한 노드라면 사이클 발생
		//cyclePath는 지금까지의 진행경로를 전부 담고 있어서
		//사이클 경로만 보기 위해서 사이클 발생 지점에서 cyclePath를 자른다.
		int cyclePoint = cyclePath.indexOf(currentNode); 
		System.out.println("사이클 :" + cyclePath.subList(cyclePoint, cyclePath.size()));
		return true;
	}
		
	visited[currentNode] = 1; //노드 방문
	cyclePath.add(currentNode); //방문 노드 기록
		
	for(int nextNode : stations.get(currentNode)) {
		if(nextNode == parentNode) {
			continue;
		}else if(dfs(nextNode, currentNode)) {
			return true;
		}
	}
	return false;
}

 

 그러면 전체 코드는 아래와 같이 된다.

class Graph {
	private ArrayList<ArrayList<Integer>> graphList;
	
	public Graph(int size) {
		this.graphList = new ArrayList<ArrayList<Integer>>();
		
		for(int i=0; i<size; i++) {
			this.graphList.add(new ArrayList<Integer>());
		}
	}
	
	public void put(int v1, int v2) { //무방향 그래프
		graphList.get(v1).add(v2);
		graphList.get(v2).add(v1);
	}
	
	public ArrayList<Integer> get(int v){
		return graphList.get(v);
	}
}

private static int[] visited; 
private static ArrayList<Integer> cyclePath;
private static Graph graph;
public static void main(String[] args) throws Exception {

	//예시그래프 생성
	graph = new Graph(4);
	graph.put(1, 2);
	graph.put(1, 3);
	graph.put(1, 4);
	graph.put(2, 1);
	graph.put(3, 1);
	graph.put(3, 4);
	graph.put(4, 1);
	graph.put(4, 3);
        
	//변수 초기화
	visited = new int[4];
	for(int i=0; i<4; i++) {
		visited[i] = -1;
	}
	cyclePath = new ArrayList<Integer>();
			
	dfs(1, -1);
}

public static boolean dfs(int currentNode, int parentNode) {
	if(visited[currentNode] != -1) { 
		int cyclePoint = cyclePath.indexOf(currentNode); 
		System.out.println("사이클 :" + cyclePath.subList(cyclePoint, cyclePath.size()));
		return true;
	}
		
	visited[currentNode] = 1;
	cyclePath.add(currentNode);
		
	for(int nextNode : stations.get(currentNode)) {
		if(nextNode == parentNode) {
			continue;
		}else if(dfs(nextNode, currentNode)) {
			return true;
		}
	}
	return false;
}