[그래프] 그래프 표현방법

• 그래프
  • 현상이나 사물을 정점과 간선으로 표현한 것
• 정점
  • 대상이나 개체를 나타냄
• 간선
  • 정점간의 관계를 나타냄
  • 가중치를 주어 정도를 표현할 수 있음

그래프, 정점, 간선

 

 

 

그래프의 표현

• 전통적인 그래프 표현법에는 행렬을 이용하는 방법과 리스트를 이용하는 방법이 있음

 

인접 행렬

인접 행렬

• 행렬 표현법은 이해하기 쉽고 간선의 존재 여부를 즉각 알 수 있음
• n*n 행렬이 필요하므로 n^2에 비례하는 공간이 필요하고, 행렬 준비 과정에서 행렬의 모든 원소를 채우는 데만 n^2에 비례하는 시간이 든다
• 표현방법
  • 정점 i 와 정점 j 사이에 간선이 있으면 행렬 (i,j)  (j,i) 원소의 값을 1로 할당함
  • 방향이 있는 경우 i->j 를  (i,j)로 표현
  • 가중치가 있는 경우 원소의 값에 할당함
  • 나머지 자리에는 0을 할당함

 

 

인접 리스트

인접 리스트

• 각 정점에 인접한 정점들을 리스트로 표현하는 방법
• 각 정점마다 리스트를 하나씩 만들며, 전통적으로 연결 리스트를 사용함
• 표현 방법
  • 각 정점마다 인접한 정점들을 하나의 연결리스트에 매달음
  • 존재하지 않는 간선은 리스트에 나타나지 않음
  • 간선 하나에 대하여 노드가 2개씩 만들어짐
  • 각 노드는 정점 번호, 가중치, 다음 정점으로 가는 링크로 구성됨
• 모든 가능한 정점 쌍에 비해 간선의 수가 적을 때 특히 유용함 : 희소 그래프
• 인접 리스트에서는 정점 i와 정점 j 간에 간선이 존재하는 지를 알아볼 때 리스트에서 차례대로 훑어야 하므로 인접 행렬 표현보다 시간이 많이 걸림
• 간선의 밀도가 아주 높을 때는 인접 행렬 표현법을 권장함

 

 

인접 배열

인접 배열

• 각 정점에 연결된 정점들을 연결리스트 대신 배열로 저장하면
  • 연결리스트의 싱크를 위한 공간 절약
  • 노드들이 메모리에 흩어져서 존재하는 불안감으로부터 벗어남
  • 두 정점의 인접 여부 체크하는 시간도 줄일 수 있음
• 그래프는 대부분 알고리즘 시작부에서 주어지거나 한번 만들어지면 변하지 않는 경우가 많음
• = 알고리즘 입장에서 보면 정적. -> 배열을 사용하면 효율적
• 각 정점의 인접 배열을 위해 공간을 따로 할당 받거나 / 하나의 배열을 할당받아서 처리할 수도 있음

 

 

인접 해시 테이블

인접 해시 테이블

• 다루어야 할 그래프가 엄청난 크기이면 비교의 횟수가 매우 커짐
• 인접 배열 각각을 해시 테이블로 대체하면 (적재율이 0.5일 때) 평균 2번의 비교로 가능함
• 공간 할당을 받을 때 정점별로 따로 할당받을 수 있고, 하나의 배열에 인접 배열 전체 크기를 할당반아서 나누어 쓸 수도 있음
• 해시 테이블을 사용하면 임의의 정점에 인접한 모든 다른 덩점에 순차적으로 접근해야하는 경우에 다소 불편할 수 있음

 

 

 

 

 

참고자료 : 「쉽게 배우는 자료구조 with 자바」