<aside> 1️⃣ 그래프를 인접 행렬과 인접 리스트로 변환하는 코드를 작성하시오.

</aside>

• 출처 (밀리의 서재에 있음)

  코딩 테스트 합격자 되기 - 자바 편 - 예스24

[ 그래프 이론 ]

1. 그래프

• 데이터 간의 관계 표현
  • 데이터 : 노드 V(vertex)
  • 관계, 흐름 : 간선 E(edge)
  • 흐름의 정도 : 가중치 w(weight)
• 방향성 : 방향성 유무에 따라 방향/무방향 그래프
• 순환성 : 순환 여부에 따라 순환/비순환 그래프

2. 인접 행렬

• 배열을 활용하여 구현

  • 배열[출발노드][도착노드] = 가중치

    

  • 연결되지 않아서 -로 표현한 가중치는 굉장히 큰 값 or -1 넣기

• 장점
  • A에서 B로 연결된 간선의 정보를 확인할 때 유리 : 시간복잡도 O(1)
    • 예) 2에서 93이 연결되어 있는지 탐색하려면 array[2][93]에 가중치 있는지 확인
  • 구현 난이도가 낮음
• 단점 : 공간 복잡도 측면에서 불리
  • 공간 복잡도 O(E²) (정점이 10만 개 이상이면 메모리 초과 발생)
  • 메모리 낭비가 많은 케이스 존재
    • 인접 행렬로 희소 그래프를 표현하는 경우 (희소 그래프 : 노드 수에 비해 간선 수가 매우 적은 그래프)
    • 노드들의 값의 차이가 매우 큰 그래프를 표현하는 경우 (1, 2, 999 이면 행렬 크기가 999*999)

3. 인접 리스트

• 인접 리스트용 노드 정의 : [ 정점(v) | 가중치(w) ]
• 배열과 ArrayList를 연결

  • 배열[시작 정점] = 노드를 담은 ArrayList를 연결