인접 행렬(Adjacency Matrix)
컴퓨터로 그래프를 표현하는 방법중 하나는 인접 행렬이다. 인접 행렬은 배열을 이용하여 표현한다.
여기서 배열의 행은 출발 노드를 가리키고 열은 도착 노드를 가리킨다. 두 노드의 경로가 존재하면 1, 존재하지 않으면 0으로 표기한다. 무방향 그래프는 1->0과 0->1로 가는 경로를 모두 표기하고 방향 그래프는 해당 경로가 있는 경우에만 표시를 한다. 위 표를 자세히 보면 알 수 있는 재미있는 사실이 하나 있다. 그건 바로 첫 번째 그래프와 두 번째 그래프의 인접 행렬은 모두 대각선에 대해 대칭 형태를 보여준다. 그렇기 때문에 대각선으로 나누어지는 배열의 반만 있어도 그래프를 표현할 수 있다. 세 번째 그래프의 경우도 1보다는 0이 더 많은 것을 볼 수 있다. 이처럼 0이 많은 그래프를 희소 그래프라고 한다. 이 또한 배열의 크기에 비해 표기되는 정보가 없기 때문에 메모리 낭비가 심하다.
인접 리스트(Adjacency List)
인접 리스트는 인접 행렬의 메모리 낭비를 줄이기 위해 만들어진 것으로 연결 리스트를 이용하여 인접 정점을 표현한다. 인접 리스트는 하나의 정점을 헤드 노드로 지정하고 이 정점의 인접 정점을 연결 리스트로 표현한다.
인접 리스트로 표현하면 인접 행렬보다는 메모리 효율이 좋다. 하지만 아직도 단점이 있다. 연결 리스트의 특성상 데이터와 링크를 가지는 노드를 사용하기 때문에 그래프의 엣지와 정점이 많아지면 많은 메모리를 요구한다. 또한 무방향 그래프는 인접 행렬의 문제점인 중복된 엣지 표현이라는 단점을 극복하지 못했다.
인접 다중 리스트(Adjacency Multi List)
인접 다중 리스트는 인접 리스트의 단점인 중복된 간선 표시를 없애준다. 아래 그림에서 보는 것처럼 그래프가 가질 수 있는 간선의 최대 개수만큼 노드로 표현되고 있다. 헤드 노드는 시작하는 노드를 가리키고 헤드 노드와 관련된 간선들을 링크를 통해 탐색한다. 간선을 표시하는 노드의 구조는 다음과 같다. 먼저 mark는 간선을 검사했는지 체크하는 필드이다. V1과 V2는 간선으로 연결되는 정점을 나타내며 V1 링크는 정점 V1과 연결된 다른 간선의 노드 주소이고 V2 링크는 정점 V2와 연결된 다른 간선의 노드 주소이다.
그러면 정점 2의 간선들을 찾아보자. 처음 헤드 노드가 가리키는 곳은 E2이다. 여기는 정점 0과 2의 간선을 표현한 것이다. 이제 E2를 확인했으니 mark에 표시를 한다. 다음 2와 관련된 간선은 오른쪽 링크 필드가 가리키고 있다. 따라가면 E4가 나온다. 다음 관련 간선은 오른쪽 링크 필드가 가리키고 있다. 따라가면 E6가 나온다. E6의 링크필드는 NULL이다. 이제 탐색이 끝난 것이다. 그럼 결과적으로 정점 2의 인접 간선은 E2, E4, E6이다. 그래프에서 확인하면 정확하다는 것을 알수 있다.
'자료구조' 카테고리의 다른 글
| 너비 우선 탐색(BFS : Breadth First Search) (0) | 2022.03.30 |
|---|---|
| 깊이 우선 탐색(DFS : Depth First Search) (0) | 2022.03.30 |
| 그래프(Graph) (0) | 2022.03.30 |
| AVL 트리(AVL Tree) (0) | 2022.03.29 |
| 이진 탐색 트리(Binary search tree) (0) | 2022.03.29 |