본문 바로가기
반응형

전체 글147

알고리즘 - 프림(Prim) 최소 신장 트리를 구하는 알고리즘. 1. 시작점을 아무거나 고른다. 2. 선택한 점을 최소 신장 트리에 추가한다. 3. 최소 신장 트리에 추가된 정점들과 일반그룹과 연결하는 간선중 가장 가중치가 낮은 간선을 추가. 4. 추가된 간선과 연결된 정점을 추가. 5. 3-4를 반복. 구현할 때는 최소값 우선순위 큐를 사용. 1. 시작 정점을 선택하고 그 점과 연결된 모든 간선을 우선순위 큐에 넣는다. 2. 시작점을 최소 신장 트리에 넣는다. 3. 우선순위 큐에는 최소 신장 트리에 포함된 정점과 그렇지 않은 정점들을 연결하는 간선이 모두 들어있음. 4. 우선순위 큐에 들은 간선중 최소값 간선을 확인하고 연결된 정점이 최소신장트리에 들어있지 않다면 추가. 5. 최소 신장 트리가 완성될 때까지, 모든 정점이 최소 신.. 2020. 3. 9.
Minimum Spanning Tree, MST - 최소 신장 트리 임의의 그래프에서 가중치의 합이 최소인 최소 연결 부분 그래프. 부분 그래프 : 임의의 그래프에서 일부 간선을 제거한 그래프. 전체 그래프의 부분 집합. 연결 그래프 : 부분그래프 중에 그래프의 모든 두 노드 사이의 경로가 존재하는 그래프. 최소 신장 트리는 그래프의 특수한 경우인 트리, 트리의 특수한 경우이기 때문에 두가지 조건을 만족한다. 1. 사이클이 존재하지 않는다. - 트리의 특징. 2. 모든 노드가 연결되어 있다. 2020. 3. 9.
알고리즘 - 플로이드 와샬(Floyd warshall) 최단 경로 탐색 알고리즘. 다른 알고리즘은 출발점, 도착점을 지정해야만 구할수 있는 반면, 이 알고리즘은 모든 노드 사이의 최단거리를 구할수 있다. 1. 그래프를 인접행렬로 저장. 두 노드 사이의 간선이 두 개 이상인 멀티 그래프라면, 짧은거 하나만 저장.(최단경로니까.) 2. 노드간 연결이 없으면 무한대로 저장. 3. 특정 정점을 경우해서 가는 경로의 길이와 기존에 저장한 정점사이의 거리를 비교해 짧은쪽으로 갱신. 4. 3번에 사용한 방법을 모든 정점에 대해 경유지로 설정해서 값을 갱신. A,B,C,D 노드를 가진 그래프라면 A를 경유해 가는 경로, B를 경유해 가는 경로, C를, D를 경유해 가는 경로를 전부 확인해서 갱신한다는 뜻. 2020. 3. 9.
알고리즘 - 벨만 포드(Bellman-ford) 최단 경로 탐색 알고리즘. 간선 가중치가 음수인 경우에도 적용가능함. 단, 사이클의 가중치 합이 음수인 경우가 존재하는 그래프는 최단 경로를 구할 수 없음. 1. 그래프의 간선정보를 저장. (출발노드, 도착노드, 가중치) 를 저장. 2. 시작 노드를 지정. 3. 모든 정점까지의 거리를 무한대로 설정. 4. 모든 간선을 확인해, 출발노드에서 도착노드로 이동했을때의 거리가 이미 저장된 도착노드까지의 거리보다 짧은경우 거리를 갱신. 거리 = 가중치. dist[v] > dist[u] + w 인 경우, dist[v] = dist[u] + w 로 갱신. 5. 4를 V-1번 반복. V는 노드 수. 6. 음수 사이클여부를 확인하려면 한번더 반복하고, 이때 거리가 갱신되는 노드가 발견되면 음수사이클이 존재함. 2020. 3. 9.
알고리즘 - 다익스트라(dijkstar) 알고리즘 최단 경로를 찾기 위해 사용하는 알고리즘. 하나의 출발점부터 모든 정점으로의 최단 거리를 계산하는 알고리즘. 1. 시작점 결정 2. 전체 거리를 무한대(코드상에서는 0)로 설정. 3. 현재 위치에서 갈수 있는 정점 저장. 전체거리를 최소로 늘릴수 있는 경로를 갱신. 불가능하면 스킵. 4. 선택하지 않았던 정점중 가장 짧은 거리에 있는 정점을 현재 정점으로 갱신. 5. 3~4 번 반복. 단순 구현으로는 시작점에서 각 정점에 대한 거리를 배열에 저장해가면서 각 정점으로의 최단 경로들을 찾아가는 방법이 있다... 10개의 정점을 가지는 그래프라고 가정할때 10개의 요소를 가지는 배열에 순서대로 각 정점에 대한 최단 경로를 저장하는 것. 당연히 자기 자신으로의 경로는 0의 거리를 가진다. 효율적인 구현으로는 우.. 2020. 3. 6.
Graph 그래프는 저장된 자료들사이의 관계를 나타내기를 위한 구조. 정점(Vertex) : 자료를 나타내는 단위로 리스트나 트리의 노드와 같은 의미. 간선(Edge) : 정점을 연결하는 선을 의미하며 자료사이의 관계를 나타냄. 가중치(Weight) : 한 정점에서 다른 정점으로 이동하는데 필요한 자원을 나타냄. 즉, 간선의 값. 가중치를 표시하지 않는다면 1로 생각해도 무방. 차수(Degree): 그래프에 연걸된 간선 수. 노드사이의 모든 연결 간선수를 나타냄. - 입력 차수 : 방향성 그래프일때 노드로 들어오는 간선수. - 출력 차수 : 방향성 그래프일때 노드에서 나가는 간선수. 단순 경로 : 그래프의 한 정점에서 다른 정점으로의 경로 중, 모든 정점을 단 한번씩만 방문하는 경로. 사이클(Cycle) : 단순 .. 2020. 3. 5.
반응형

티스토리툴바