인접행렬과 인접리스트

인접 행렬 Adacency Matrix

---

개념

그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬을 의미한다.

0 은 두 정점 사이의 경로가 없음을 의미하고, 1 은 두 정점사이의 경로가 있음을 의미한다.

코드

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

인접 리스트 Adacency List

---

개념

그래프에서 정점과 간선의 관계를 나타내는 인접리스트를 의미한다.

코드

#include <bits/stdc++.h>

using namespace std;

const int V = 4;
vector<int> adj[V];

int main()
{
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[0].push_back(3);

    adj[1].push_back(0);
    adj[1].push_back(2);

    adj[2].push_back(0);
    adj[2].push_back(1);

    adj[3].push_back(0);

    for (int i = 0; i < 4; i++)
    {
        cout << i << " :: ";
        for (int there : adj[i])
        {
            cout << there << " ";
        }
        cout << '\n';
    }
}

List VS Vector

인접리스트는 list 또는 vector 로 구현이 가능하다.

하지만 인접리스트를 구현할 땐 시간복잡도 때문에 vector 를 많이 사용한다.

인접리스트를 기반으로 로직을 구현할 때 많이 사용하는 연산은 아래와 같다.

• 마지막 요소 삽입 및 삭제
• n번째 요소 참조

Function	List	Vector
n번째 인덱스 삽입 및 삭제	O(1)	O(n)
마지막 요소 삽입 및 삭제	O(1)	O(1)
특정요소 탐색	O(n)	O(n)
n번째 요소 참조	O(n)	O(1)

인접행렬 VS 인접리스트

비교	인접행렬	인접리스트
공간복잡도	O(V^2)	O(V + E)
시간복잡도 : 간선 한개 찾기	O(1)	O(V)
시간복잡도 : 모든 간선 찾기	O(V^2)	O(V + E)

그래프가 희소(sparse)할 때 는 인접리스트, 조밀(dense)할 땐 인접행렬을 사용하는 것이 좋다.

희소할 때 인접행렬을 쓰게 되면…

희소할 때 인접행렬을 쓰게 되면 간선이 없어서 대부분의 요소가 0 임에도 불구하고

해당 부분을 전부 포함하여 2차원 배열을 만들어야되기 때문에 메모리를 더 많이 사용한다.

조밀할 때 인접리스트를 쓰게 되면…

조밀할 때 인접리스트를 쓰게 되면 간선을 전부 하나하나 기록해야 한다.

그리고 i 정점의 리스트를 선형탐색해서 j가 있는지 찾아야 할 때,

평균 O(V/2) 의 시간복잡도가 소요되며, 최악의 경우엔 O(V) 만큼의 시간복잡도가 걸린다.

방향 벡터 Direction Array (Vector)

---

개념

2차원 그래프에서 상하좌우 혹은 대각선으로 이동할 때, 좌표 이동을 간단하게 표현하기 위한 도구이다.

코드

int dy[] = {-1 , 0, 1, 0}; // direction_y
int dx[] = {0, 1, 0, -1}; // direction_x