(알고리즘) 그래프, 트리에서 Cycle 탐지하기

첫번째, 재귀를 이용한 방법

(Directed Graph)
http://www.geeksforgeeks.org/detect-cycle-in-a-graph/

(Undirected Graph)
http://www.geeksforgeeks.org/detect-cycle-undirected-graph/


두번째, Stack을 이용한 방법

--->방문한 점인데, 현재 Stack안에 그 노드가 있으면 Cycle이다.
--->st.contains(k)

void DFSUtil(boolean visited[], int i, Stack<Integer> st) {
st.push(i);
visited[i] = true;
for (int k : adj[i]) {
if (!visited[k])
DFSUtil(visited, k, st);
else if (st.contains(k))
flag = 1;
}
if (flag != 1)
st.pop();
}

void DFS() {
Stack<Integer> st = new Stack<Integer>();
boolean visited[] = new boolean[V];
for (int i = 0; i < V; i++) {
if (!visited[i])
DFSUtil(visited, i, st);
}
}