Java 코테 핵심이론 (그래프)

08 그래프

 

8-1 그래프의 표현 (중요)

 

1. 에지 리스트

- 가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 충분하다.
(방향이 없는 그래프라면 [1,2] , [2,1]은 같은 표현이다.)
- 가중치가 있는 그래프는 행을 3개로 늘려 가중치를 저장하면 된다.
- 구현하기는 쉽지만 특정 노드와 관련되어 있는 에지를 탐색하기는 쉽지 않다 (시간 복잡도 큼)
- 에지 리스트는 벨만포드나 크루스칼 알고리즘에 사용

 

2. 인접 행렬

- 2차원 배열을 자료구조로 이용하여 그래프를 표현함.
- 에지 리스트와 다르게 노드 중심으로 그래프를 표현함.
- 인덱스를 활용하여 표현 A[3][4]는 3에서 4를 향하는 엣지이다.
- 가중치가 없으면 해당 2차원 배열에 1을 넣고 가중치가 있으면 그 가중치 값을 넣으면 된다.
- 노드와 관련되어 있는 지를 탐색하려면 N번 접근해야하므로 노드 개수에 비해 엣지가 적을 때는 공간 효율성이 떨어짐.
- 따라서 인접행렬은 노드 개수에 따라 사용 여부를 적절하게 판단하는 능력이 중요

 

3. 인접 리스트

- 이것을 가장 많이 사용하고 ArrayList로 표현함 (ArrayList는 사이즈가 가변적임)
- 가중치 없는 그래프일때 ArrayList<Integer>[N] 이렇게 배열로 선언한다.
( A[3].add(3) )
- 배열이므로 index로 직접 접근이 가능함.
- 가중치 있는 그래프일때 ArrayList<Node>[N] 이렇게 내가 만들어야 할 객체, class를 넣어줘야 함.
( A[3].add(New Node(4,13) )
- 구현이 복잡하지만 노드와 연결되어 있는 엣지를 탐색하는 시간이 매우 뛰어나고 메모리 초과 에러도 발생 안함

 

 

8-2 유니온 파인드

- 그래프의 싸이클 생성되는지 판별하는 알고리즘
- 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성됨.

 

<핵심 이론>

1. 1차원 배열을 이용하여 각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스 값으로 초기화
2. 2개의 노드를 선택해 각각의 대표노드를 찾아 연결하는 union 연산을 수행
3. 대표노드를 찾을때 find()를 써라. (그래프를 정돈하고 시간 복잡도를 향상)

<find의 동작원리>

1. 대상 노드 배열의 index 값과 value 값이 동일한지 확인한다.
2. 동일하지 않으면 value값이 가르키는 index 위치로 이동한다.
3. 이동 위치의 index 값과 value 값이 같을 때까지 1~2를 반복한다. (재귀 함수로 구현)
4. 대표노드에 도달하면 재귀 함수를 빠져나오면 거치는 모든 노드값을 루트 노드값으로 변경
  (유니온 파인드의 목적 : 두 노드가 어떤 경로인지 관심없고 한 집합인지 아닌지 따질 때)

경로 압축은 실제 그래프에서 여러 노드를 거쳐야 하는 경로에서 그래프를 변형해 더 짧은 경로로 갈 수 있도록 함으로써 시간 복잡도를 효과적으로 줄이는 방법을 말한다.

 

 

8-3 위상 정렬

위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.
위상 정렬을 했을 때 값이 유일하지 않고 시간 복잡도는 O(노드 수 + 지 수) 이다.

 

<핵심 이론>

1. 인접리스트를 활용하여 진입 차수 (자신을 가리키는 엣지의 갯수) 배열을 초기화 해준다.
2. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 정렬 배열에 저장합니다.
3. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺍니다.

 

-> 다른 그래프 알고리즘과의 차이는 진입 차열 배열을 기준으로 알고리즘이 돌아간다는 것이다.

 

 

8-4 다익스트라 (최단 거리 알고리즘)

- 엣지가 모든 양수일 때 시작 점에서 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘
- 시간 복잡도는 O(ElogV)이다.

 

<핵심 이론>

1. 인접 리스트로 그래프 구현하기 (데이터를 자료구조에 저장)
2. 최단 거리 배열 초기화하기 (출발노드는 0 이외의 노드는 무한으로 초기화)
3. 값이 가장 작은 노드 고르기
4. 최단 거리 배열 업데이트 하기 (선택한 노드에서 다른 노드로 가는 값들을 더한 것과 현재 알고 있는 값 비)
5. 과정 3~4를 반복해 최단 거리 배열 완성하기 (과정 4에서 선택된 노드들을 방문 배열로 만들어 처리)

 

 

8-5 벨만-포드 (최단 거리 알고리즘)

이것은 음수 간선이 있어도 가능하다.

음수 싸이클이 있는지 체크하는 문제들이 나옴 (과거 시간 여행의 문제등)

 

 

 

8-6 플로이드-워셜 (최단 거리 알고리즘)

시작 점이 없고 모든 노드에 대해서 최단 거리를 구함 -> 시간 복잡도가 안좋음

 

 

 

8-7 최소 신장 트리

모든 노드들을 연결하는데 최소의 비용으로 연결할 때 최소 신장 트리를 쓴다.

싸이클이 나오면 안됨 -> 이때 유니온 파인드를 사용함