노드와 에지로 구성된 집합
노드는 데이터를 표현하는 단위이고 에지는 노드를 연결함
트리도 그래프의 일종
그래프의 사이클이 생성되는지 판별하는 알고리즘
그래프의 노드들을 선형으로 정렬
값이 유일하지 않음
※ 조건 : 사이클이 없고 방향이 있는 그래프
※ 많이 출제되는 문제 :
수강 신청
전-후 관계가 있는(방향이 있는) 데이터
최단거리 알고리즘
시작점(s)에서 다른 모든 노드로 가는 최단거리 구하는 알고리즘
※ 조건 : 음수간선이 있으면 안됨
최단거리 알고리즘
다익스트라와 똑같음
다만 음수 간선도 가능함
최단거리 알고리즘
시작점이 없음
시간복잡도가 "다익스트라" , "벨만-포드" 보다 좋지 않음
모든 노드들을 연결하는데 드는 최소의 비용을 구하는 알고리즘
그래프에서 최소의 가중치 합으로 모든 노드를 연결 할 수 있게 해주는 알고리즘
싸이클이 있으면 안됨 그래서 해당 문제를 풀려면 유니온 파인드가 필요함