[알고리즘] 그래프

에지 리스트

• 에지 중심인 그래프
• 배열에 출발 노드, 도착 노드 저장 -> 에지 표현
• 혹은 가중치까지 저장하여 표현

1. 에지리스트로 가중치 없는 그래프 표현: 출발, 도착 노드만 표시 -> 배열의 행 2개
2. 에지리스트로 가중치 있는 그래프 표현: 3번째 행에 가중치 저장

 

• 구현하기 쉬움
• 단점: 특정 노드와 관련되어 있는 에지 탐색은 어려움
• => 벨만 포트 or 크루스칼 알고리즘에 사용(노드 중심 알고리즘에서는 잘 사용 안함)

 

인접 행렬

• 2차원 배열의 노드 중으로 그래프 표현

1. 인접행렬로 가중치 없는 그래프 표현: 1 -> 2 = 1행 2열에 1을 저장 (가중치가 없으니까 1로 저장)
2. 인접행렬로 가중치 있는 그래프 표현: 1 -> 2 가중치 8 = 1행 2열에 8을 저장(가중치 값을 저장)

 

 

• 구현하기 쉬움, 두 노드 연결한 에지의 여부와 가중치값을 배열에 직접 접근하면 바로 확인 가능
• 단점: 특정 노드와 관련되어 있는 에지 탐색하려면 n번 접근해야함
• -> 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어짐
• -> 노드 개수가 많은 경우 아예 2차원 배열 선언 자체가 불가능함 -> 노드 개수에 따라 사용 여부를 판단해야함
• ex) 노드가 3만개 넘어가면 자바 힙 스페이스 에러(실행 중에 힙 메모리 공간을 모두 사용했을 때)가 발생 

 

인접 리스트

• ArrayList로 표현 -> 노드 개수만큼 선언
• n번 노드와 연결되어 있는 노드를 배열의 위치 n에 연결된 노드 개수만큼 배열을 연

1. 인접리스트로 가중치 없는 그래프 표현: 1 -> 2 = 1행 2열에 1을 저장 (가중치가 없으니까 1로 저장)
2. 인접리스트로 가중치 있는 그래프 표현: 1 -> 2 가중치 8 = 1행 2열에 8을 저장(가중치 값을 저장)

 

 

• 노드와 연결되어 있는 에지 탐색하는 시간 뛰어남
• 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러가 발생 안함
• 단점: 구현하기 복잡한 편
• 코딩테스트에서 선호

 

 

 

 

 

 

 

참고: Do it! 알고리즘 코딩 테스트 - 자바 편, 김종관저