[질문] 그래프의 사이클 탐지하는 recusive 함수를 만들었는데 안되네요...
글쓴이: 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:
이미 방문한 node를
이미 방문한 node를 check 대상에서 제외하기 위한 장치가 없나요? 0 -> 1 -> 2 와 같이 연결되어 있고 2 -> 1가 다시 연결된 경우라면 무한 recursion이 발생할 것 같군요. 양방향 edge가 없다고 가정해도 전체 node/edge 수를 크게 상회하는 recursion이 발생할 수 있고 스택이 모자랄 수 있겠죠. visted node와 그렇지 않은 node들을 나타내는 set을 만들고 recursion대신 iteration을 사용하는 것이 효율적이지 않을까요?
댓글 달기