Root Node 혹은 다른 임의의 노드에서 시작해서 다음 분기(Branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.
Stack과 재귀함수(Recursion)으로 구현한다.
두 가지의 자료구조(인접 리스트, 인접 행렬)로 구현할 수 있다.
접점(V), 간선(E)
/* 인접 리스트 이용 */
class Graph {
private int V;
private LinkedList<Integer> adj[];
Graph(int v) {
V = v;
adj = new LinkedList[v];
// 인접 리스트 초기화
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w) { adj[v].add(w); }
/* DFS에 의해 사용되는 함수 */
void DFSUtil(int v, boolean visited[]) {
// 현재 노드를 방문한 것으로 표시하고 값을 출력
visited[v] = true;
System.out.print(v + " ");
// 방문한 노드와 인접한 모든 노드를 가져온다.
Iterator<Integer> it = adj[v].listIterator();
while (it.hasNext()) {
int n = it.next();
// 방문하지 않은 노드면 해당 노드를 시작 노드로 다시 DFSUtil 호출
if (!visited[n])
DFSUtil(n, visited);
}
}
/* DFS */
void DFS(int v) {
boolean visited[] = new boolean[V];
// v를 시작 노드로 DFSUtil 재귀 호출
DFSUtil(v, visited);
}
}
합병정렬(merge sort) (0) | 2022.03.19 |
---|---|
힙 정렬(heap sort), 힙 소트 (0) | 2022.03.19 |
BFS (너비 우선 검색) 정리 (0) | 2022.03.19 |
분할정복(Divide and Conquer) (0) | 2022.03.19 |
완전탐색 (Brute-Force) (0) | 2022.03.19 |