그래프

DFS란?BFS란?그래프에서 적용된 모습차이점 비교DFS는 Depth-First Search의 약자로 깊이 우선 탐색이란 뜻입니다.트리에서 사용한다면 다음과 같은 순서를 가집니다.선택 가능한 자식 노드가 없을 때까지 자식 노드를 우선적으로 선택합니다.모든 노드를 탐색해

다익스트라 알고리즘이란?알고리즘 사용 예시기본적으로 두 정점사이의 최소 거리를 구하는 알고리즘입니다.활용성이 좋은 알고리즘으로서 변형되는 경우가 많습니다.가장 많은 방법으로 사용되는 경우는 한 특정 정점에서 각 정점의 거리를 구하는 방법입니다.즉, DP를 사용하는 최단

벨먼-포드 알고리즘이란?알고리즘 사용 예시불가능한 예시시간 복잡도가중 유향 그래프(edge에 방향과 가중치가 있는 그래프)의 최단 경로 문제를 푸는 알고리즘 입니다.이전에 살펴본 다익스트라 알고리즘과 비슷하지만 벨먼 포드의 경우 가중치에 음수가 들어갈 수 있습니다.아래

플로이드-워셜 알고리즘이란?알고리즘 사용 예시불가능한 예시시간 복잡도앞서 살펴 보았던 최단 거리 알고리즘들은 시작 정점이 정해져야 했습니다.플로이드 워셜 알고리즘은 시작 지점을 설정하지 않습니다.플로이드 워셜 알고리즘은 모든 정점사이의 최단거리를 구하는 과정에 사용됩니

위상 정렬이란?알고리즘 사용 예시불가능한 예시방향이 있는 유향 그래프의 정점들을 간선의 방향에 위배되지 않도록 나열한 것입니다.위 그래프를 예시로 위상 정렬의 과정을 설명하겠습니다.우선 앞서 설명했던 큐와 위상 정렬을 저장할 배열을 준비합니다.정점 중 진입 차수가 0인