그래프는 노드와 에지로 구성된 집합이다.
노드는 데이터를 표현하는 단위이고 에지는 노드를 연결하는 선이다
트리도 그래프의 일종이다

유니온 파인드 : 그래프의 사이클이 생성되는지 판별하는 알고리즘. 사이클 유무 판단
위상 정렬 :
조건 : 사이클이 없어야한다. 방향이 있는 그래프 여야한다
그래프의 각 노드들을 선형으로 연결하는 것
값이 유일하지 않다는 특징이 있다,

• 수강신청 (전후 관계가 있어야한다)
  ex) 수1 -> 수2
  아이템을 업그레이드 하려면 선순위로 아이템을 사고 업그레이드 해야한다

다익스트라 : (S) 시작점. 다른 모든 노드로 가는 최단거리를 구하는 알고리즘
단, 음수 간선은 있으면 안된다.
벨만-포드 : 다익스트라와 비슷하지만 벨만포드는 음수간선도 ok
음수 사이클이 있는지를 체크하는 문제로 많이 사용한다.
ex) 시간여행을 할 수 있는지, 과거로 돌아가기
플로이드-워셜 : 주어진 모든 노드를 체크해서 임의의 모든 모드 쌍의 최단거리를 구한다. 시작점이 없다. 시간 복잡도가 안좋다.
ex) 모든 도시 최단거리 100개 이하,

위 3개는 최단거리 알고리즘

최소 신장 트리 : 모든 노드를 연결하는데 최소의 비용으로 간선을 연결. 사이클이 나올 수 없다. 간선의 가중치가 최소일 애들 구하려면 이걸 사용하고, 유니온 파인드가 필요하다.

그래프의 표현

에지 리스트
에지를 중심으로 그래프를 표현한다. 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현한다.
또는 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현한다.

에지 리스트로 가중치 없는 그래프 표현하기
가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 충분한다. 노드는 여러 자료형을 사용할 수 있다.

에지 리스트로 가중치 있는 그래프 표현하기
가중치가 있는 그래프는 행을 3개로 늘려 3번째 행에 가중치를 저장하면 된다.
에지 리스트는 벨만 포드나 크루스칼 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않는다

인접 행렬
N = [N][N]
인접행렬은 2차원 배열을 자료구조로 이용하여 그래프를 표현한다. 에지 리스트와 다르게 노드 중심으로 그래프를 표현한다

두 노드를 연결하는 에지의 여부와 가중치값은 배열에 직접 접근하면 바로 확인할 수 있는 것이 장점이지만 노드와 관련 있는 에지를 탐색하려면 N번 접근해야 하므로 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어진다. 또한 노드 개수가 많은 경우 아예 2차원 배열 선언 자체를 할 수 없는 결함도 있다. 따라서 인접 행렬은 노드 개수에 따라 사용 여부를 적절하게 판단하는 능력이 필요하다. 예를 들어 노드가 3만개가 넘으면 자바 힙 스페이스 에러가 발생한다.

인접 리스트
인접 리스트는 ArrayList로 그래프를 표현한다. 노드 개수만큼 ArrayList를 선언한다.

인접리스트로 가중치 있는 그래프 표현하기
가중치가 있는 경우 자료형을 클래스로 사용한다. 가중치가 없는 그래프와의 차이점은 Integer와 class로 표현된다는 것
그래프를 구현하는 다른 방법에 비해 인접 리스트를 이용한 그래프 구현은 복잡한 편이지만 노드와 연결되어 있는 에지를 탐색하는 시간은 매우 뛰어나며, 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않는다

인접행렬과의 차이점은 인접행렬은 공백도 검색해서 시간 복잡도가 오래걸린다