#43. Algorithm33_python) 그래프(Graph)의 기본 구조

DFS, BFS를 공부하기 전에 먼저 그래프(Graph)의 기본 구조를 알아야 함

 

 

그래프(Graph)의 기본 구조

• 그래프는 노드(Node)와 간선(Edge)로 표현됨
  • Node를 정점(Vertex)라고도 함
• 그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는 것
• 두 노드가 간선으로 연결되어 있다면, '두 노드는 인접하다(Adjacent)'라고 표현
• '노드 : 도시, 간선 : 도로' 로 이해할 수 있음
  • Edge는 거리로 표현할 수 있는 '비용'을 갖을 수 있다.

출처 : https://adrianmejia.com/data-structures-for-beginners-graphs-time-complexity-tutorial/

 

인접 행렬, 인접 리스트

• 프로그래밍에서 그래프는 크게 2가지 방식으로 표현될 수 있음
  • 1) 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
  • 2) 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식

 

1) 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

• 2차연 배열에 각 노드가 연결된 형태를 기록하는 방식
• 파이썬에서는 2차원 리스트로 구현 가능
  • 연결 되어 있지 않은 노드끼리는 무한(Infinity)의 비용이라고 작성

# Adjacency Matrix

INF = 999999999 # 무한의 비용 선언

# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph)

>>>
[[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]

 

2) 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식

• 다음 그림처럼 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장
• 파이썬은 기본 자료형인 리스트 자료형이 append()와 메소드를 제공하므로, 전통적인 프로그래밍 언어에서의 배열과 연결 리스트의 기능을 모두 기본으로 제공
• 파이썬으로 인접 리스트를 이용해 그래프를 표현하고자 할 때에도 단순히 2차원 리스트를 이용하면 됨

# Adjacency List

# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]
print(graph)

# 노드 0에 연결된 노드 정보 저장 (노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))
print(graph)

# 노드 1에 연결된 노드 정보 저장 (노드, 거리)
graph[1].append((0, 7))
print(graph)

# 노드 2에 연결된 노드 정보 저장 (노드, 거리)
graph[2].append((0, 5))
print(graph)


print()
print(graph)

>>>
[[], [], []]
[[(1, 7), (2, 5)], [], []]
[[(1, 7), (2, 5)], [(0, 7)], []]
[[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

[[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

 

두 방식은 어떤 차이?

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

• 다른 예시) : 노드1과 노드7이 연결된 상황
  • 인접 행렬 방식 : graph[1][7]만 확인하면 됨
  • 인접 리스트 방식 : 노드1에 대한 인접 리스트를 앞에서부터 차례대로 확인해야 함

 

<참조>

• 이것이 취업을 위한 코딩 테스트다 with 파이썬(나동빈, 한빛미디어)
• https://adrianmejia.com/data-structures-for-beginners-graphs-time-complexity-tutorial/