2024/07/12 2

[Algorithm/Graph] 깊이 우선 탐색(DFS, Depth-First scrach)

깊이 우선 탐색(DFS) 깊이 우선 탐색(DFS)는 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식이다.더 방문할 정점이 없어지면 다른 경로를 찾아 다시 멀어지는 방향으로 탐색을 반복한다. 이러한 그래프 탐색 방법을 백트래킹(backtracking)이라고 한다.DFS 구현BFS에서는 방문하지 않은 정점을 저장하기 위해 큐를 사용했다.큐를 사용하기 때문에 가장 가까이에 있는 정점부터 접근이 가능했다.하지만 DFS는 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하기 때문에, 스택을 사용한다.후입 선출 속성을 갖는 스택을 사용하기 때문에 현재 정점과 인접한 정점들을 재귀적으로 이동하면서 방문할 때 사용하기에 적합하다.PS에서 그래프를 나타내야하는 경우 인접 행렬..

Algorithm/Graph 2024.07.12

[Algorithm/Graph] 너비 우선 탐색(BFS, Breadth-First Scrach)과 구현(에지 리스트, 인접 행렬, 인접 리스트)

그래프 순회 문제그래프의 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제EX) 사무실에서 출발하여 주변 거래처를 순회하며 결재를 하는 경우그래프에서 특정 정점을 찾기 위한 용도로 사용될 수 있기 때문에 그래프 탐색 문제라고도 부른다.여러 그래프 탐색 알고리즘이 존재하고, 각각은 서로 다른 순서로 모든 정점을 방문하다.너비 우선 탐색(BFS, Breadth-First Scrach)시작 정점을 경계(frontier)에 추가하는 것으로 시작경계는 이전에 방문했던 정점들에 의해 구성된다그리고 현재 경계에 인접한 정점을 반복적으로 탐색한다같은 거리에 있는 정점들의 방문 순서는 임의로 정해도 되지만, 멀리 있는 정점보다는 가까운 정점을 먼저 방문해야 한다.BFS는 모든 정점에 대해 자식 정점을 손자 정점보..

Algorithm/Graph 2024.07.12