0. 그래프란?
1) 개념
: 정점(Vertex)과 정점들을 연결하는 간선(변, Edge)으로 이루어진 자료구조의 일종으로 G = (V,E) 로 나타낸다.
- 방향이 있는 그래프(Directed Graphs)
- 방향이 없는 그래프(Undirected Graphs)
2) 그래프 탐색
: 하나의 정점에서 시작하여 차례대로 모든 정점을 한번씩 방문하는 것을 뜻한다.
1. DFS(Depth First Search, 깊이 우선 탐색) - Stack
1) 개념: 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
2) 특징
- 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사함
- 깊게(Deep하게) 탐색하는 방법임.
- 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
- 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
- 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림
- 자기자신을 호출하는 순환 알고리즘 형태를 지님.
- 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것 (이를 검사하지 않을 경우 무한루프에 빠질 위험이 있음)
3) 시간복잡도
- DFS는 그래프(정점의 수 : N, 간선의 수: E)의 모든 간선을 조회함
* 인접 리스트로 표현된 그래프 : O(N+E)
* 인접 행렬로 표현된 그래프 : O(N^2)
DFS - 나무위키
한 정점을 두번 이상 방문하지 않는 연결그래프에서 DFS트리라는 유향트리 구조가 만들어진다. Tree edge란 DFS중 a정점을 방문한 후 b정점을 처음 방문할 때, a→b의 유향간선을 말한다. Back edge란 DFS
namu.wiki
2. BFS(Breadth First Search, 너비 우선 탐색) - Queue
1) 개념: 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
2) 특징
- 넓게(Wide하게)탐색하는 것임.
- 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택함
ex) 전 세계의 모든 사람들의 관계를 그래프로 만들고, 'Jack' 과 'Kongnamoo' 의 관계를 잇는 간선을 찾는다고 가정해보자.
BFS를 사용하면 Jack에게 관련된 간선들을 하나씩 파악해나가기 때문에 Kongnamoo를 비교적 빠르게 찾을 수 있지만, DFS로 파악할 경우 Jack의 자식노드를 모두 파악하고 가므로 Jack의 부모님, Jack의 외할머니...Jack의 외할머니의 친구의친구.. 등으로 무한한 길이로 빠져 영원히 종료하지 못하는 것이다. 때문에 DFS 에서는 너무 깊게 뻗어나가는 것을 막기 위해 때때로 limit를 걸어두는 것이다.
- BFS 는 재귀적으로 동작하지 않는다.
- 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것이다 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.
- BFS 는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 선입선출(FIFO) 원칙인 큐(Queue)를 사용함
3) 시간복잡도
- BFS는 그래프(정점의 수 : N, 간선의 수: E)의 모든 간선을 조회함
* 인접 리스트로 표현된 그래프 : O(N+E)
* 인접 행렬로 표현된 그래프 : O(N^2)
BFS - 나무위키
너비 우선 탐색은 트리나 그래프를 방문 또는 탐색하는 방법이다. 탐색 방법은 다음과 같다. 루트에서 시작한다.자식 노드들을 [1]에 저장한다.[1][1]에 저장된 노드들을 차례로 방문한다. 또한 각
namu.wiki
※참고자료: https://namu.wiki/w/BFS
※참고자료: 나무위키
※Copyright 사도출판. All rights reserved.
※본 게시물 속 내용을 통해 직접적으로 상업적인 목적이 없으며 게시물은 개인 공부 목적 및 지식 간단 전파목적으로 사용되었음을 명시함. 책 및 인터넷 검색을 참고자료로 하여 실습 및 학습을 한 내용을 올림. 참고한 책 및 인터넷 검색물의 저작권을 존중하므로 책 및 인터넷 저작물의 일부 또는 전부를 무단 복제 및 무단 전재 및 재배포하지 않음(일부라 함은 30%이하의 내용 중복은 불포함[30%이하는 다른 저작물로 간주]). 또한 책 또는 매체를 구매하지 않고는 정확한 내용을 알 수 없으며 개인이 따로 공부한 내용도 추가 되어 책과는 내용이 매우 상이할 수 있음.즉 본 게시물 작성자는 이 게시물을 읽는 모든 사람들이 책을 구매거나 인터넷 검색을 더하여 지식을 같이 나누었으면 좋겠음.