댈팽이 2024. 4. 10. 21:54
728x90

1. 에지 리스트

  • 에지를 중심으로 그래프를 표현한다.
  • 구현이 쉽다.
  • 특정 노드와 관련되어 있는 에지를 탐색하기가 어렵다.
  • 벨만 포드, 크루스칼 알고리즘에 사용한다.

 

가중치가 없는 그래프인 경우 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현한다.

1에서 2로 가는 에지는 [1, 2]로 표현한다.

 

가중치가 있는 그래프인 경우 배열에 출발 노드, 도착 노드, 가중치를 저장하여 에지를 표현한다.

1에서 2로 가는 가중치가 8인 에지는 [1, 2, 8]로 표현한다.


2. 인접 행렬

  • 2차원 배열을 자료구조로 이용하여 노드 중심으로 그래프를 표현한다.
  • 구현이 쉽다.
  • 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어진다.
  • 노드 개수가 많은 경우 사용할 수 없다.

 

노드 개수가 5이므로 5 x 5 행렬을 사용한다.

1에서 2로 가는 에지는 A[1][2]에 1을 저장하여 표현한다.

가중치가 없는 그래프이므로 가중치 대신 1을 저장한다.

 

가중치가 있는 그래프이면 1 대신 가중치를 저장한다.

1에서 2로 가는 가중치가 8인 에지는 A[1][2]에 8을 저장하여 표현한다.


3. 인접 리스트

  • ArrayList로 그래프를 표현한다.
  • 구현이 복잡하다.
  • 공간 효율성이 좋다.

 

노드 개수인 5만큼 ArrayList를 선언한다.

1과 연결된 노드 2, 3을 ArrayList[1]에 [2, 3]을 연결하여 표현한다.

 

가중치가 있는 그래프인 경우 도착 노드, 가중치를 갖는 Node 클래스를 사용한다.

1과 연결된 노드 2, 3을 ArrayList[1]에 [(2, 8), (3, 3)]을 연결하여 표현한다.


4. 예제 문제


 

[2178] 미로 탐색 (JAVA)

# 문제 설명 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌

spicyrisotto.tistory.com

728x90