graph
-
알고리즘, graph, DijkstraData Structure & Algorithm 2024. 7. 3. 18:18
다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 찾는 데 사용되는 알고리즘입니다. 이 알고리즘은 가중치가 있는 그래프에서 사용되며, 가중치가 음수가 아닌 경우에만 적용할 수 있습니다.다익스트라 알고리즘의 개념시작 정점 선택: 알고리즘은 시작 정점에서 시작합니다.최단 경로 집합: 최단 경로를 확정한 정점들의 집합을 유지합니다.미확정 집합: 아직 최단 경로가 확정되지 않은 정점들의 집합을 유지합니다.거리 배열: 시작 정점에서 각 정점까지의 현재까지 발견된 최단 거리를 저장합니다. 초기에는 시작 정점의 거리를 0으로 설정하고 나머지 정점의 거리를 무한대로 설정합니다.이웃 정점 업데이트: 현재 정점에서 인접한 정점들로의 거리를 계산하고, 더 ..
-
자료구조와 알고리즘, graph, dfs, bfsData Structure & Algorithm 2024. 7. 1. 17:07
그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조로, 정점 간의 관계를 나타내는 데 사용됩니다. 그래프는 다양한 형태로 존재하며, 여러 가지 문제를 해결하는 데 유용합니다.그래프의 기본 용어정점(Vertex): 그래프의 노드를 의미합니다. 정점은 데이터를 저장할 수 있습니다.간선(Edge): 정점 간의 연결을 나타냅니다. 간선은 방향이 있을 수도(유향 그래프) 없을 수도(무향 그래프) 있습니다.인접 정점(Adjacent Vertex): 간선으로 직접 연결된 정점들입니다.경로(Path): 한 정점에서 시작하여 다른 정점으로 가는 일련의 간선들입니다.가중치(Weight): 간선에 부여된 값으로, 두 정점 간의 비용이나 거리를 나타냅니다. 가중치가 있는 그래프를 가중치 그래프(..