[개념,그래프] 인접행렬 ,인접리스트 - 그래프를 코드로 !

그래프의 개념은 뭔지 알았으니, 이제 그걸 코드로 구현해보는 연습을 해보자.

2가지 방법이 있는데, 각각의 장/단점은 뭐고, 어떨때 쓰면 이득인지 알아봅시다. 

사실 그래프의 종류는 워낙 많아서, 나중에 차근차근 더 살펴보는 걸로 하자.

언어 : Python

---

1. 인접 행렬

• Vertex * Vertex 크기 만큼 행렬을 만들어서, 그 두개의 Vertex가 Edge로 이어져있다면 1 , 아니면 0을 넣어 그래프를 표현하는 방식이다.
• 인접 행렬로 구현을 할 경우, 그래프(무방향의 한해서) 대각 성분을 기준으로 대칭인 성질을 갖게된다

그림판에서 그려옴!

위의 그래프를 인접행렬로 생각한다면, 옆의 그림과 같이 될것임. 그럼 이걸 코드로 어떻게 구현할까.

보통, 문제에서는 구성하는 정점의 개수(Vertex),간선의 개수(Edge), 연결정보가 들어온다.

위의 그래프로 예를들면 , 아래와 같이 Input이 주어진다.

Input

4 4 

1 2

1 3

2 3

3 4

그럼, 우리는 이거를 코드로 표현할 줄 알아야한다. 

Vertex * Vertex 크기 만큼 행렬을 만들어서 Edge로 이어져있다면 1 , 아니면 0

vertex,edge = map(int,input().split())

adj = [[0]*vertex for _ in range(vertex)] # 정점의 갯수만큼 생성!

# 간선의 갯수만큼 돌면서, 간선의 정보 인접행렬에 반영
for i in range(edge):
	start,end = map(int,input().split())
    	adj[start][end] = 1
    	adj[end][start] =1

장점

• 구현이 간편하다. 
• Vertex끼리 연결되어 있는지 확인하고 싶으면, adj[i][j]만 확인하면 되기때문에, 탐색(접근)이 빠르다.

단점

• 메모리가 많이 듭니다. 극단적으로, 정점(vertex)가 1,000,000개면 , 1,000,000*1,000,000개의 배열을 만들어야 한다.
• 노드에 비해 간선이 너무 적으면 비효율적이게 됨. 예를들어, 극단적으로 노드가 1,000,000개인데, 내가 간선 1개만 갖고 있으면, 최악의 경우, 1,000,000번 탐색을 해야할 수 도 있다는 이야기다.

2. 인접 리스트

• 파이썬에서는 동적배열(List)로 구현하고, 각 노드(Vertex)에 대한 간선(Edge)연결 정보를 리스트로 담는 방식으로 표현한다.

똑같이 ,그래프를 인접 리스트로 나타낸다고 생각해보자. 그럼, 옆과 같이 인접리스트의 개념은 구현이 된다.

각 노드에 대한 간선 연결정보를 담는 형식으로.

여기서 알 수 있는 특징은 , 간선의 갯수만큼만 메모리를 할당해주면 된다.

Input

4 4 

1 2

1 3

2 3

3 4

그럼, 이걸 코드로 어떻게 구현해주냐?

v ,e = map(int,input())

adj=[[] for _ in range(v)]

for i in range(e):
	start,end= map(int,input().split())
    	adj[start].append(end)
    	adj[end].append(start)

위와 같이 구현해주면 된다.

그럼, adj에는 adj=  [ [2,3] , [1,3] ,[1,2,4],[3] ]

• 첫번째 인덱스의 배열 -> 첫번째 정점에 대한 간선의 정보
• 두번째 인덱스의 배열 -> 두번째 정점에 대한 간선의 정보 

장점

• 한 노드에 연결된 친구를 찾기가 쉽다.
• 간선의 갯수만큼만 메모리가 생성되기 때문에, 메모리에서 이득을 볼 수 있다.

단점

• 정점간의 연결관계를 알고싶을때, 탐색이 느리다. 
• 인접행렬은 adj[i][j]에 딱 접근해서 1인지 0인지만 보면 되니까 O(1)이지만, 인접리스트는 adj[i]에 들어가서 하나하나 반복해야한다. 최악은 O(V)까지 나올수있음!

---

Summary

• 인접행렬 : 메모리가 많이드는 대신, 탐색이 빠르고, 간선이 많으면 사용할만하다.
• 인접리스트: 메모리는 간선의 갯수만큼 밖에 들지않지만, 탐색이 느리다. 간선이 많으면 인접리스트의 장점이 무색해지므로, 간선이 적으면 유리하다.

문제에서, 간선의 갯수의 범위를 잘보고 행렬이 유리한지, 리스트가 유리한지 선택하면 된다.

 

보통은 한 쪽으로만 풀리는 문제는 없다고 한다. 왜냐하면, 우리가 차이가 극명하게 날만큼의 거대한 데이터를 다룰일은 크게 없기 때문이다. 하지만, 둘 다 구현할 줄 아는 사람이 되어야 한다!