11. 그래프 (서론)

강의: 08

---

< 그래프 >

 

■ 그래프 

      -노드와 에지로 구성된 집합

      -노드는 데이터를 표현하는 단위

      -에지는 노드를 연결

 

 ✔ 그래프 알고리즘 공부 전 

      -그래프는 여러 알고리즘에 자주 사용되는 자료구조

      -코딩테스트에 자주 등장

      -자료구조 별 이름과 특징을 잘 이해하고 넘어가기

 

 ✔ 그래프 알고리즘의 종류 (간단)

    1. 유니온 파인드: 그래프의 사이클이 생성되는지 판별하는 알고리즘 (싸이클 유무 판단)

 

    2. 위상 정렬: 사이클이 없고 방향이 있는 선형으로 정리하는 그래프 (전후관계가 있는 = 방향이 있는)

 

    (최단거리 알고리즘) 3. 다익스트라: 시작점(S)이 존재, 다른 모든 노드로 가는 최단거리는 구하는 알고리즘 *음수간선XXXX

 

    (최단거리 알고리즘) 4. 벨만-포드: 다익스트라랑 전부 비슷하지만 음수간선이 O

                                    * 음수 사이클을 확인하는 문제에서 더 많이 쓰임 (웜홀, 시간여행 등)

 

    (최단거리 알고리즘) 5. 플로이드-워셜: 어떤 노드를 선택하던지 최단거리를 구하는 알고리즘 but, 시간복잡도가 안 좋음

 

    6. 최소 신장 트리(MST): 그래프에서 최소의 가중치 합으로 모든 노드를 연결할 수 있게 해주는 알고리즘

                                   * 유니온 파인드가 필요함(싸이클)