[자료구조] 인접 행렬, 인접 리스트

Graph 관련 문제를 해결하기 위해 모델링할 경우에는, 두 가지 방법이 존재합니다.

1. 인접 행렬
2. 인접 리스트

인접 행렬

• 그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬을 의미한다.
• 정사각형 행렬의 각 요소가 0 또는 1이라는 값으로 가짐을 의미하며, 0은 두 정점 사이의 경로가 없음을 의미하며, 1은 두 정점 사이의 경로가 있음을 의미한다.

간단히 요약하자면 다음과 같다.

adj[i][j] = 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0

 

다음 그래프를 한번 살펴보자

 

• 1 - 1, 2 - 2를 보면 0으로 되어있는 것을 볼 수 있는데 자기자신을 나타내는 것이며 해당 정점의 사이클이 없을 때는 0, 사이클이 있을 때는 1로 표기를 합니다.
• 0 - 1 이 연결되어있기 때문에 a[0][1] = 1이 됩니다. 그러나 1 - 3은 연결되어있지 않기 때문에 a[1][3] = 0이 됩니다.

이것을 C++ 코드로 표현하자면 이렇게 된다.

bool a[4][4] = {
{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 0},
{1, 0, 0, 0},
};

 

 

장단점

인접 행렬의 장점으로는

• 구현이 쉽다.
• adj[i][j]가 1인지 0인지만 확인하면 되기 때문에 시간 복잡도는 O(1)이다.

단점으로는

• 모든 간선을 찾기 위해서는 O(V^2)라는 시간 복잡도가 걸린다.
• 또한 간선이 적은 경우에도 2차원 배열을 만들기 때문에 메모리를 더욱 많이 사용한다.

인접 리스트

• 인접 리스트는 그래프에서 정점과 간선의 관계를 나타내는 연결리스트를 의미한다.
• 인접 리스트는 연결리스트로 구현한다. (C++에서는 vector로 구현하거나, Javascript에서는 Array로도 구현 가능하다.)

인접 행렬에 있는 예시를 인접 리스트로 구현한다면 다음과 같게 된다.

{
	0 : [1, 2, 3],
    1 : [0, 2],
    2 : [0, 1],
    3 : [0]
}

장단점

장점으로는

• 실제로 연결된 노드에 대한 정보만 저장하기 때문에, 간선의 개수에 비례하는 메모리만 차지한다.

단점으로는

• 노드 i와 노드 j가 연결되어 있는지 확인하는 시간복잡도는 O(N)이 걸린다.

인접 행렬과 인접 리스트 비교

 

 

 

 

참조

https://sarah950716.tistory.com/12

https://suyeon96.tistory.com/32