[CS] AdjacentMatrix&AdjacentList

인접 행렬

일방향 그래프

첫 번째 행인 1번 노드는 2번, 3번, 4번 노드로 이어진다. 두 번째 행인 2번 노드는 3번 노드만 이어진다.

즉, 노드에서 다른 노드로 이어지는 간선 이 있을 때 1, 없을때 0으로 표현한다. 이를 행렬로 표현하면 오른쪽 표와 같다.

무방향(양방향) 그래프

무방향 그래프는 양방향 그래프로 볼 수 있다. 표현은 일방향 그래프와 비슷하다. 1번 노드와 연결된 2, 3, 4번 노드를 1로 표현한다. 2번 노드와 연결된 1, 3번 노드를 1로 표현한다.

이렇게 표현한 행렬은 오른쪽 표와 같다. 행렬을 보면 대각선을 기준으로 대칭이 됨을 알수 있는데, 무방향(양방향)그래프에서만 나타나는 특징이다.

인접 리스트

일방향 그래프

인접 행렬과 비슷하다.

연결이 없으면 공간 할당이 아예 안된다.

0 or 1 로 표현하는 것이 아닌 연결된 노드 자체를 저장한다. 이렇게 표현한 리스트는 오른쪽 표와 같다.

무방향(양방향) 그래프

무방향(양방향)도 인접 행렬과 비슷하다. 연결된 간선들이 전부 할당된다

이렇게 표현한 리스트는 오른쪽 표와 같다. 인접 행렬과 다르게 이렇다 할 특징이 눈에 보이진 않는다.

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

인접 행렬

인접 행렬은 메모리 효율이 상대적으로 좋지 않다. 간선의 유무를 0 or 1 로 표현하기 때문에 N² 크기의 메모리가 항상 할당되어야 한다. 하지만, 탐색 속도는 빠르다. 배열로 구현되어있기 때문에 인덱스를 통한 탐색에 O(1)의 시간이 걸린다.

인접 리스트

인접 리스트는 메모리 효율이 상대적으로 좋다. 연결된 간선이 없다면 따로 메모리 할당이 필요 없기 때문이다. 하지만, 탐색 속도는 느리다. 리스트로 구현되어있기 때문에 모든 리스트를 순회해 O(N)의 탐색 시간이 걸린다.

• 간선이 적다면 인접 리스트가 메모리 효율 면에서 유리하다.

• 간선이 많다면 인접 행렬이 탐색 속도 면에서 유리하다.

구현

인접 행렬

class Graph {
private:
	vector<vector<int>> adj;
	int vNum;

public:
	Graph(int vertex) {
		vNum = vertex;
		adj.resize(vNum, vector<int>(vNum, 0));
	}
	void addEdge(int i, int j) {
		if (i >= 0 && i < vNum && j >= 0 && j < vNum) {
			adj[i][j] = 1;
			//adj[j][i] = 1; // 양방향인 경우
		}
	}
	void removeEdge(int i, int j) {
		if (i >= 0 && i < vNum && j >= 0 && j < vNum) {
			adj[i][j] = 0;
			//adj[j][i] = 0; // 양방향인 경우
		}
	}
};

인접 리스트

class Graph {
private:
    vector<list<int>> adj;
    int vNum;

public:
    Graph(int vertex) {
        vNum = vertex;
        adj.resize(vertex);
    }

    void addEdge(int src, int dest) {
        if (src >= 0 && src < vNum && dest >= 0 && dest < vNum) {
            adj[src].push_back(dest);
            //adj[dest].push_back(src); // 양방향인 경우
        }
    }

    void removeEdge(int src, int dest) {
        if (src >= 0 && src < vNum && dest >= 0 && dest < vNum) {
            adj[src].remove(dest);
            //adj[dest].remove(src); // 양방향인 경우
        }
    }
};