[Algorithm] 그래프 기본 알고리즘

 

8-1 그래프의 표현

 

8-2 유니온 파인드 

: 그래프의 사이클이 생성되는지 판별하는 알고리즘

8-3 위상 정렬

조건: 싸이클이 없어야 한다. 방향이 있는 그래프여야 한다.

노드를 정렬해주는 알고리즘

정렬 결과가 꼭 1개가 아니다.

 

위상 정렬을 이용한 예제.

1) 수강신청 수1->수2를 들어야 하는 방향성이 있어야 한다.

 

8-4 다익스트라

: 시작점이 있고 시작점에서 다른 모든 노드로 가는 최단거리를 구하는 알고리즘

but, 음수간선 X

8-5 벨만 포드

:시작점이 있고 시작점에서 다른 모든 노드로 가는 최단거리를 구하는 알고리즘

음수간선 O (있어도 된다)

8-6 플로이드 워셜

: 시작점이 없음 

but , 시간복잡도가 안 좋음.

-> 모든 도시간의 최단거리를 구해야 한다(도시 개수는 100개 이하)

시간복잡도가 낮아도 되고 특정 도시를 찍어준 게 아니라 모든 도시를 구해야 함(시작점이 없으므로)

이런 문제에 쓰기 좋음

 

다익스트라,벨만 포드, 플로이드 워셜은 최단 거리를 구하는 알고리즘

8-7 최소 신장 트리(MST)

그래프에서  최소의 가중치 합으로 모든 노드를 연결할 수 있게 해주는 알고리즘

 

정리가 되면 코테 문제를 풀 때 어떤 알고리즘을 선택해서 풀어야 겠다는 감을 잡을 수 있다!

 

• 참고자료

https://www.inflearn.com/course/lecture?courseSlug=%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC&unitId=148393