그래프2

• 

  [c++] 다익스트라 알고리즘 (백준-최단경로 1753) 다익스트라 알고리즘이란? 다익스트라 알고리즘이란 한 지점에서 그래프 상의 나머지 모든 지점으로의 최단 경로를 구할 수 있는 알고리즘이다. 다익스트라 알고리즘은 그래프 상의 어느 한 간선의 가중치라도 음수가 존재하면 안된다. 이는 다익스트라 알고리즘이 현재 선택하는 것이 최선의 방법이라는 greedy를 기반으로 한 알고리즘이기 때문이다. 만약 음수의 가중치가 있다면 이 경로를 계속 지나갈수록 더욱 최선의 값을 가지게 되므로 다익스트라 알고리즘에 위배된다. (음수의 가중치를 가질 수 있을 때는 벨만 포드 알고리즘을 이용해야한다.) 다익스트라 알고리즘을 구현하기 위해서는 2가지의 과정을 반복해주면 된다. /* 1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. -> 이를 위해 처음 배열을 무.. c++/알고리즘 2023. 1. 25.

• 

  [c++] 알고리즘 그래프 - 위상 정렬 - 백준 - 줄 세우기 2252 위상 정렬이란? 위상 정렬이란 어떤 집합에서 원소들의 우선 순위 정렬이라고 할 수 있겠다. 또한 위상정렬은 비순환 방향 그래프 즉 (DAG : Directed Acyclic Graph)에서 가능하다. 즉 그래프를 이루는 노드들 간의 순환이 존재하지 않게 방향이 존재할 때 가능한 정렬이다. DAG 위와 같은 DAG그래프를 선형적 그래프로 변경하는 것을 위상정렬이라고 한다. 위상정렬은 말 그대로 위상을 정렬한다는 뜻으로 이 정렬에는 각 노드들의 우선 순위가 중요하다. 또한 우선 순위만을 고려하기 때문에 최종 결과 값이 여러 개가 될 수 있다. 즉 위의 비선형 그래프는 다음과 같은 뜻을 내포한다. 1보다는 0이 선행되어야한다. 1보다는 4가 선행되어야한다. 2보다는 1이 선행되어야한다. 2보다는 4가 선행되어.. c++/알고리즘 2023. 1. 25.