그래프 탐색(순회)
- 그래프 순회는 비선형구조인 그래프로 표현된 모든 자료(정점)를 빠짐없이 탐색하는 것을 의미→ 깊이 우선 탐색 (Depth First Search, DFS)
- → 너비 우선 탐색 (Breadth First Search, BFS)
너비 우선 탐색(BFS)
- 너비 우선 탐색은 탐색 시작점의 인접한 정점들을 먼저 차례로 방문한 후, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식
- 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행해야 하므로, 선입선출 형태의 자료규조인 큐를 사용
BFS(G, v) // 그래프 G, 탐색 시작 정점 v
큐 생성
시작 정점 v를 큐에 삽입
정점 v를 방문한 것으로 표시
while(큐가 비어있지 않은 경우){
t = 큐의 첫 원소 poll()
for(t와 연결된 모든 간선 탐색){
u = t의 인접 정점
u가 방문되지 않은 곳이라면,
u를 큐에 넣고, 방문한 것으로 표시
}
}
end BFS()
private static void bfs(int start) {
Queue<Integer> queue = new LinkedList<Integer>();
boolean visited[] = new boolean[N];
queue.offer(start); //처음에 0부터 시작
visited[start] = true; // 들어갈때 방문 처리 !!!
while (!queue.isEmpty()) {
int v = queue.poll();
System.out.println(v);
//visited[v] = true;
for (int i = 0; i < N; ++i) {
if (map[v][i] && !visited[i]) {
queue.offer(i);
visited[i] = true; //들어갈때 방문 처리!!!
}
}
}
}
깊이 우선 탐색(DFS)
- 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법
- 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 재귀적으로 구현하거나 후입선출 구조의 스택 사용
- → 재귀의 경우도 스택의 자료구조를 사용하기 때문에 사용가능!
DFS(v) // v : 탐색 정점 G : 그래프 visited[v] = true for(v에서 인접한 노드 w){ IF visite
DFS(v) // v : 탐색 정점 G : 그래프
visited[v] = true
for(v에서 인접한 노드 w){
IF visited[w] != TRUE
DFS(w)
}
end DFS()
private static void dfs(int v) {// 번호 v로부터 시작하는 dfs
visited[v] = true;
System.out.println(v);
for (int i = 0; i < N; ++i) {
//v번째 행에서 탐색
if (map[v][i] == true && !visited[i]) {
//System.out.println(v + ":" + i);
dfs(i);
}
}
}
'Algorithms > 개념 정리' 카테고리의 다른 글
[문자열] 문자열 패턴 매칭 (0) | 2021.04.06 |
---|---|
[Graph] 최단 경로 (0) | 2021.03.30 |
[Graph] 최소 신장 트리(MST) (0) | 2021.03.29 |
[Graph] 서로소 집합 (0) | 2021.03.26 |
[Graph] Graph 이론 (0) | 2021.03.24 |