[알고리즘][파이썬] 그래프 / graph

그래프 (graph)

• 원소 간의 관계를 표현한 자료구조

---

그래프의 기본 구조

 

• 노드(node)=정점(vertex)와 간선(edge)으로 표현
• 두 노드가 인접하다 : 두 노드가 간선으로 연결되어 있다
• 노드1과 노드3은 인접하다
• 그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는 것

 

---

그래프의 표현

1. 인접 행렬 (Adjacency Matrix)

• 2차원 배열로 그래프의 연결관계를 표현하는 방식
• 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식
• 연결되어 있지 않은 노드끼리는 무한의 비용으로 작성 (999999999,987654321)
• 자기자신은 비용이 0

 

	0	1	2
0	0	무한	5
1	무한	0	3
2	5	3	0

 

INF = 999999999 #무한

graph = [
	[0, INF, 5]
   	[INF, 0, 3]
	[5, 3, 0]
]

print(graph)

2. 인접 리스트 (Adjacency List)

• 리스트로 그래프의 연결 관계를 표현하는 방식
• 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장

• '연결 리스트'라는 자료구조를 이용해 구현
• 파이썬은 기본 자료형인 리스트 자료형의 append() 함수 이용

graph = [[] for _ in range(3)] #행이 3개인 2차원 리스트

graph[0].append((2,5)) #노드0에 연결된 노드 정보
graph[1].append((2,3)) #노드1에 연결된 노드 정보
graph[2].append((0,5)) #노드2에 연결된 노드 정보
graph[2].append((1,3))

print(graph)

∴ 메모리 측면에서 인접리스트 방식이 연결된 정보만을 저장하기 때문에 효율적

∴ 속도 측면에서 인접리스트 방식은 연결된 데이터를 하나씩 확인해야 하기 때문에 느림