[알고리즘] 프로그래밍에서 그래프를 표현하는 방식 (인접행렬 방식, 인접리스트 방식)

-- 본 포스팅은 이것이 취업을 위한 코딩 테스트다 with 파이썬 책을 참고하여 작성되었습니다.

1. 탐색이란

• 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 대표적인 탐색 알고리즘은 DFS 와 BFS가 있음

 

2. 그래프 표현 방식

• 그래프의 구성 : 노드(정점), 간선(Edge)

• 그래프를 코드로 표현하는 방법은 2가지가 있다

 

2.1 인접행렬 표현 방식

• 2차원 배열로 그래프의 연결관계를 표현하는 방식이다.
• 아래 그래프를 표로 표현하면 오른쪽의 표처럼 표현이 될 것이다.

• 이 그래프를 2차원 리스트로 구성하게 되면 아래와 같다

INF = 999999  #무한대의 비용 선언

#2차원 배열을 활용하여 그래프를 표현
graph = [
    [0, 7, 5],
    [7, 0 INF],
    [5, INF, 0]
    ]
   
print(graph)
## 결괏값 ---> [[0, 7, 5] , [7, 0, 999999], [5, 999999, 0]]

 

2.2 인접리스트 방식

• 리스트로 그래프의 연결 관계를 표현하는 방식

• 해당 그래프를 인접 리스트로 표현하기 위한 개념은 아래와 같다.

• 이것을 프로그래밍 코드로 표현하면 아래와 같다.

#row 가 3개인 2차원 리스트로 연결 리스트가 표현된다. (row수 = node 수)
graph = [[] for _ in range(3)]

#노드가 0인 연결 노드 정보 (노드, 거리)로 표현
graph[0].append((1,7))
grpah[0].append((2,5))
#노드 1
graph[1].append((0, 7))
#노드 2
graph[2].append((0,5))


print(graph)
## 결과 ---> [[(1,7), (2,5)], [(0,7)], [(0,5)]]

 

2.3 인접행렬과 인접리스트의 차이

• 메모리 측면
  • 인접행렬 : 모든 관계를 저장하므로 노드 개수가 많을ㅇ 수록 메모리가 불필요하게 낭비됨
  • 인접리스트 : 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용할 수 있음.
• 속도 측면 
  • 인접행렬 : 모든 관계를 저장하므로 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 빠르다
  • 인접리스트 : 연결된 정보만을 저장하기 때문에 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다. 연결된 데이터를 하나하나 다 확인해 보아야 한다.