2022.08.02의 공부 : 그래프

1. 에지 리스트

    출발노드 - 도착노드 저장하여 에지를 표현(가중치가 들어가기도 한다!)

    출발노드, 도착노드만 이끈 경우에는 배열의 행이 2개만 존재한다.

     - 벨만포드나 크루스칼 알고리즘에 사용한다고 함

 

벨만-포드 알고리즘 : 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘

    -> 간선의 가중치가 음수일 때도 최단 거리를 구할 수 있음

**다익스트라와의 차이

- 다익스트라는 매번, 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택

- 다익스트라는 시간 복잡도가 빠르다는 장점이 있음(우선순위 큐 사용)

- 대신 벨만-포드 알고리즘의 경우에는 매번, 모든 간선을 전부 확인해서 음수 간선이 존재하는 경우에도 cost를 계산에 넣기 때문에 실질적인 최단거리를 찾는다.

 

**결론 : 모든 간선의 비용이 양수인 경우, 다익스트라

              음수간선이 포함된 경우에는 벨만-포드 사용

 

벨만-포드 과정

1. 출발 노드 설정

2. 최단 거리 테이블 초기화

3. 아래의 과정을 (정점개수-1) 번 반복

    - 모든 간선 E개를 하나씩 확인

    - 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신

 

 

2. 인접행렬

에지 리스트와는 다르게 노드 중심으로 그래프 표현

N개의 노드가 있다고 생각하면, 노드와 관련있는 에지를 탐색하기 위해서는 N번 접근해야 함

-> 노드 개수에 비해 에지가 적으면 비효율적임

     따라서 노드 개수에 따라 사용할지 말지도 생각해야함

 

 

3. 인접 리스트

ArrayList로 그래프 표현

가중치도 포함하는 경우에는 가중치도 써준다.

- 인접리스트는 그래프가 복잡한 형태를 가지고 있음

- 노드와 연결된 에지를 탐색하는 시간이 매우 뛰어남