dfs
-
자료구조와 알고리즘, graph, dfs, bfsData Structure & Algorithm 2024. 7. 1. 17:07
그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조로, 정점 간의 관계를 나타내는 데 사용됩니다. 그래프는 다양한 형태로 존재하며, 여러 가지 문제를 해결하는 데 유용합니다.그래프의 기본 용어정점(Vertex): 그래프의 노드를 의미합니다. 정점은 데이터를 저장할 수 있습니다.간선(Edge): 정점 간의 연결을 나타냅니다. 간선은 방향이 있을 수도(유향 그래프) 없을 수도(무향 그래프) 있습니다.인접 정점(Adjacent Vertex): 간선으로 직접 연결된 정점들입니다.경로(Path): 한 정점에서 시작하여 다른 정점으로 가는 일련의 간선들입니다.가중치(Weight): 간선에 부여된 값으로, 두 정점 간의 비용이나 거리를 나타냅니다. 가중치가 있는 그래프를 가중치 그래프(..
-
알고리즘, Tree, DFSData Structure & Algorithm 2024. 6. 27. 16:31
깊이 우선 탐색(Depth-First Search, DFS)은 그래프 또는 트리의 노드를 탐색하는 방법 중 하나로, 가능한 한 깊이 있는 노드를 우선으로 탐색합니다. DFS는 스택(stack) 자료 구조를 사용하여 구현할 수 있으며, 재귀적으로도 쉽게 구현할 수 있습니다.DFS의 특징깊이 우선 탐색: 가능한 한 깊이 있는 노드를 먼저 탐색하고, 더 이상 깊이 갈 수 없을 때 다음 인접한 노드로 이동합니다.스택 사용: DFS는 LIFO(Last In, First Out) 특성을 가진 스택을 사용하여 다음에 탐색할 노드를 관리합니다. 재귀적 구현에서는 함수 호출 스택을 사용합니다.경로 탐색: 그래프나 트리에서 경로를 탐색할 때 유용하며, 모든 경로를 탐색하는 문제에 적합합니다.DFS의 구현 (자바스크립트 예..