Algorithm (2) 썸네일형 리스트형 그래프 관련 알고리즘 정리 그래프? 정점과 간선들로 이루어진 집합. 즉 트리 역시 그래프에 속한다고 할 수 있다. * 그래프를 표현하는 대표적인 방법 세가지 간선 리스트 말그대로 배열에 간선들을 저장한다. 가장 간단하게 구현되지만 한 정점의 간선에 대한 정보를 얻으려면 모든 간선리스트를 탐색해야 하기 때문에 “벨만-포드 알고리즘”과 “크루스칼 알고리즘” 같은 일부 알고리즘이 아니고서야 많이 사용되지는 않는다. 인접 행렬 정점이 N개라면 NxN행렬을 만들어서 각각에 연결된 모든 간선들을 표시한다. 장점은 어떠한 두 정점이 연결되어 있는지를 확인한다 던지 할 경우 2차원 배열에서 탐색하기 때문에 인덱스로 상수시간 탐색이 가능하다는것. 단점은 간선의 수가 적던 많던 무조건 NxN의 공간을 사용하기 때문에 특히 정점에 비해 간선의 수가 .. 벨만포드 알고리즘 다익스트라, 플로이드-워셜과 함께 가장 많이 사용되는 “최단경로 알고리즘” 3가지 중 하나. V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 특정 출발 정점(S)에서 부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘 1. 핵심 IDEA V개의 정점과 E개의 간선을 가진 가중그래프에서 어떤 정점 A에서 어떤 정점 B까지의 최단거리는 최대 V-1개의 간선을 사용한다. 즉, 시작 정점 A를 포함하여 최대 V개의 정점을 지난다. 2. 특징 일반적으로 다익스트라 알고리즘보다 느리고 플로이드-워셜 보다는 빠른 중간정도의 연산속도를 같는다. 다익스트라 알고리즘과는 달리 음의 가중치를 갖는 간선을 포함하는 그래프에서도 사용이 가능하다. 그래프에서 음의 사이클의 존재 여부를 확인할 수 있다. 3. 알고리즘 구현.. 이전 1 다음
