성장에 목마른 코린이

Graph 그래프는 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조입니다. 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있습니다. 이선을 간선(edge) 라고 부릅니다. 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어집니다. 이 점을 그래프에서는 정점(vertex)라고 부릅니다. 알아둬야 할 그래프 용어들 정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소입니다. 간선 (edge): 정점 간의 관계를 나타냅니다. (정점을 이어주는 선) 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻합니다. 가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보, 위의 예시에서는 서..

BFS (Breadth-First Search) 너비 우선 탐색이라고하고, 주로 두 정점 사이의 최단 경로를 찾을 때 사용합니다. 만약 경로를 하나씩 전부 방문한다면, 최악의 경우 모든 경로를 다 살펴봐야 합니다. DFS (Depth-First Search) 깊이 우선 탐색이라고 하고, 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용합니다. BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있습니다. DFS와 BFS는 모든 정점을 한번만 방문한다는 공통점을 지니고 있지만, 사용할 때의 장단점은 분명하기에 상황에 맞는 탐색 기법을 사용해야합니다.