현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

[질문] 그래프의 사이클 탐지하는 recusive 함수를 만들었는데 안되네요...

tyolee83의 이미지
글쓴이: tyolee83 / 작성시간: 목, 2007/09/06 - 12:52오후

directed graph의 cycle을 탐지하는 함수를 만들어야 하는데요

사이클인지 아닌지는 이렇게 호출합니다.

//cycle check
if(checkCycle(connectedVertex[0],connectedVertex[1])){
	//cycle detected!!
	System.out.println("!CYCLE!!!");
}

동작 방식은 일단 에지를 그어보고 그게 사이클을 만들게 되면 빼는 방식입니다.
connectedVertex[0]은 현재 그으려는 에지의 출발점, connectedVertex[1]은 도착점입니다. [0]->[1] 이렇게 긋는 거구요

다음으로 recursive 함수를 이렇게 디자인하였습니다.

private boolean checkCycle(Vertex checkVertex, Vertex currentVertex){
		if(currentVertex.getEdgeList().size()==0)
			return false;
		boolean ret = false;	
 
		for(Edge e : currentVertex.getEdgeList()){
			if(e.getEndpoints()[1].equals(checkVertex)){
				ret = true;
				break;
			}
			if(checkCycle(checkVertex,e.getEndpoints()[1])){
				ret = true;
				break;
			}
		}		
		return ret;
	}

getEndpoints[0]은 시작점, [1]은 도착점을 나타내구요~
즉, 맨처음 vertex를 계속 인자로 주고, recursive하게 edge를 따라가서 그 에지가 결국 맨처음 vertex와 같으면!
cycle이다!!
이렇게 디자인한건데요

문제는 사이클 뿐만 아니라 모든 커넥션을 맺을 때 스택 오버플로가 납니다.

recursive 디자인이 잘못된것 같은데, 도움좀 부탁드립니다.

Forums: 
프로그래밍 QnA
totohero의 이미지

글쓴이: totohero / 작성시간: 목, 2007/09/06 - 3:02오후

이미 방문한 node를 check 대상에서 제외하기 위한 장치가 없나요? 0 -> 1 -> 2 와 같이 연결되어 있고 2 -> 1가 다시 연결된 경우라면 무한 recursion이 발생할 것 같군요. 양방향 edge가 없다고 가정해도 전체 node/edge 수를 크게 상회하는 recursion이 발생할 수 있고 스택이 모자랄 수 있겠죠. visted node와 그렇지 않은 node들을 나타내는 set을 만들고 recursion대신 iteration을 사용하는 것이 효율적이지 않을까요?

둘러보기