[알고리즘 파이썬] 인접 행렬과 인접 리스트

그래프 용어 정리

경로 : 정점 A에서 B로 가는 경로 

사이클 : 정점 A에서 다시 A로 돌아오는 경로 

 

단순경로(사이클) : 같은 정점을 두 번 이상 방문하지 않는 경로(사이클)

 

차수 : 정점과 연결되어 있는 간선의 수 

In-degree : 들어오는 간선의 수

Out-degree : 나가는 간선의 수

---

인접 행렬과 인접 리스트

1. 인접행렬 (Adjacency-matrix)

 

- 인접 행렬이란, 이름 그대로 그래프의 연결 관계를 행렬로 표현하여 이차원 배열로 나타내는 방식을 의미한다. 

- 대각 성분을 기준으로 대칭인 성질을 갖는다.

- Adj_mat[i][j] : 노드i 에서 노드j로 가는 간선이 존재할 경우 1이고 아니면 0이다. 

 

2. 인접 리스트 (Adjacency-list)

- 각 노드에 연결된 노드를 리스트로 포함하고 있다. 

- 리스트는 크기를 동적으로 변경할 수 있는 배열이나(리스트) or 링크드 리스트를 사용한다. (파이썬)

 

[전체 노드의 개수가 V개, 간선의 개수가 E개라고 가정]

	인접 행렬(Adjacency-matrix)	인접 리스트(Adjacency-list)
공간 복잡도	O(V*V)	O(E) => 간선의 개수에 비례
한 정점과 연결된 모든 간선 찾기	O(V) => 1개의 행 만큼 들여다 봐야 함	O(차수) => 연결된 간선의 개수
한 정점과 다른 정점 사이의 간선 찾기	O(1) => 좌표만 확인	O(차수)=> 연결된 간선에서 찾기

- 인접 리스트가 인접 행렬보다 공간을 적게 차지하고, 연결된 간선을 찾는 시간도 적게 걸린다.