[그래프] 그래프의 표현

✔ 그래프의 표현

엣지 리스트

• 엣지를 중심으로 그래프를 표현
• 가중치가 없는 그래프라면, 배열의 2개의 행에 출발 노드, 도착 노드를 저장하여 엣지를 표현
• 가중치가 있는 그래프라면, 배열의 3개의 행에 출발 노드, 도착 노드, 가중치를 저장하여 엣지를 표현
• 엣지 리스트는 구현하기 쉽지만, 특정 노드와 관련되어 있는 엣지를 탐색하기 쉽지 않음
• 벨만 포드나 크루스칼 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않음

인접 행렬

• 노드 중심으로 그래프를 표현
• 가중치가 없는 그래프라면, 출발 노드에서 도착 노드로 향하는 엣지를 인접 행렬의 출발 행 도착 열에 1을 저장하여 노드를 표현
• 가중치가 있는 그래프라면, 출발 노드에서 도착 노드로 향하는 엣지를 인접 행렬의 출발 행 도착 열에 가중치를 저장하여 노드를 표현
• 인접 행렬은 구현하기 쉽지만, 노드와 관련되어 있는 엣지를 탐색하려면 N번 접근해야 하며
  노드 개수에 비해 엣지가 적을 때는 공간 효율성이 떨어짐
• 그러므로 노드 개수에 따라 사용 여부를 적절하게 판단하는 능력이 필요 

인접 리스트

• ArrayList로 그래프를 표현
• 가중치가 없는 그래프라면, N번 노드와 연결되어 있는 노드를 배열의 위치 N에 연결된 노드 개수만큼 배열을 연결하여 표현
• 가중치가 있는 그래프라면, N번 노드와 연결되어 있는 노드를 배열의 위치 N에 연결된 노드 개수만큼 배열을 선언하고
  (도착 노드, 가중치)를 갖는 Node 클래스를 사용하여 표현
• 그래프 구현은 복잡하지만, 노드와 연결되어 있는 엣지를 탐색하는 시간은 매우 뛰어나며
  노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않음
• 실제 코딩 테스트에서는 인접 리스트를 이용한 그래프 구현을 선호

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn