인접 리스트
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
인접 리스트는 그래프의 각 정점을 해당 정점과 연결된 정점들의 목록으로 표현하는 자료 구조이다. 구현 방식에 따라 해시 테이블, 배열, 연결 리스트, 객체 지향 방식을 사용하며, 그래프의 간선에 대한 추가 정보를 저장하는 데 유연성을 제공한다. 인접 행렬에 비해 공간 효율성과 이웃 정점 탐색 효율성 면에서 장점을 가지지만, 간선 존재 여부 확인은 비효율적이며, 밀집 그래프에서는 공간 효율성이 떨어진다.
더 읽어볼만한 페이지
- 그래프 자료 구조 - 노드 (컴퓨터 과학)
노드는 컴퓨터 과학에서 트리 구조를 이루는 구성 요소로, 자료 구조 내 정보를 표현하며, 값, 조건, 다른 자료 구조를 포함하고 부모 노드에 의해 표현되며, 웹 페이지 구조를 표현하는 데 사용된다. - 그래프 자료 구조 - 그래프 (자료 구조)
그래프는 정점과 간선으로 구성되어 정점 간의 관계를 표현하는 비선형 자료 구조로, 방향, 무방향, 가중치 그래프 등 다양한 형태로 존재하며, 인접 리스트, 인접 행렬 등으로 표현되고, DFS, BFS, 다익스트라, 플로이드-워셜 알고리즘 등을 통해 탐색 및 문제 해결에 활용된다. - 그래프 이론 - 다이어그램
다이어그램은 2차원 기하학적 기호를 사용하여 정보를 시각적으로 표현하는 기술로, 과학, 공학, IT, 비즈니스 등 다양한 분야에서 활용되며 정보를 간략하게 나타내고 시각적 사고를 돕는다. - 그래프 이론 - 쾨니히스베르크의 다리 문제
쾨니히스베르크의 다리 문제는 프레겔 강에 놓인 7개의 다리를 한 번씩만 건너 출발점으로 되돌아올 수 있는지 묻는 문제로, 오일러에 의해 그래프 이론적으로 분석되어 해결되었으며 그래프 이론의 탄생에 기여했다.
| 인접 리스트 |
|---|
2. 구현
인접 리스트는 그래프의 각 정점을 그 정점에 인접한 정점 또는 간선(edge)의 목록과 연결하는 방식으로 구현되며, 구현 방식에 따라 다양한 변형이 존재한다.
| 정점 | 인접 정점 |
|---|---|
| a | b, c |
| b | a, c |
| c | a, b |
위 표는 오른쪽 그래프를 인접 리스트로 표현한 것이다. 그래프의 각 정점을 인접한 정점의 모음과 연결한다.
| 정점 | 인접 정점 |
|---|---|
| 1 | 2, 3 |
| 2 | 1, 3 |
| 3 | 1, 2, 4 |
| 4 | 3 |
인접 리스트는 컴퓨터 과학에서 그래프를 나타내는 자료 구조와 밀접한 관련이 있다. 인접 리스트 표현에서는 각 정점에 대해 하나의 간선으로 해당 정점과 연결된 모든 다른 정점의 리스트를 만든다(이것이 해당 정점의 "인접 리스트"이다).
인접 리스트 구조의 문제점은 그래프의 간선에 대한 데이터(예: 길이, 비용 등)를 저장할 명확한 위치가 없다는 점이다.
2. 1. 구현 방식
- 귀도 반 로섬이 제안한 구현 방식은 그래프의 각 정점을 인접 정점의 배열과 연결하기 위해 해시 테이블을 사용한다. 이 표현에서 정점은 해시 가능한 객체로 표현될 수 있다. 간선은 객체로 명시적으로 표현되지 않는다.[1]
- 코르멘 등은 정점을 인덱스 번호로 표현하는 구현을 제안한다.[2] 이 방식에서는 정점 번호로 인덱싱된 배열을 사용하며, 각 정점에 대한 배열 셀은 해당 정점의 인접 정점의 단일 연결 리스트를 가리킨다. 단일 연결 리스트의 노드는 간선 객체로 해석될 수 있지만, 각 간선에 대한 전체 정보를 저장하지 않는다. 무방향 그래프에서는 각 간선에 대해 두 개의 서로 다른 연결 리스트 노드가 존재한다(각 간선의 두 끝점 중 하나의 리스트 내에 하나씩).
- 객체 지향 발생 리스트 구조는 굿리치와 타마시아가 제안했으며, 특별한 종류의 정점 객체와 간선 객체를 가진다. 각 정점 객체는 인접 간선 객체를 나열하는 컬렉션 객체를 가리키는 인스턴스 변수를 갖는다. 각 간선 객체는 끝점에 있는 두 정점 객체를 가리킨다.[3] 이 방식은 인접 정점이 직접 나열되는 방식보다 더 많은 메모리를 사용하지만, 명시적 간선 객체가 존재하므로 간선에 대한 추가 정보를 저장하는 데 유연성이 더 있다.
3. 연산
위에 설명된 구현 방식을 사용하면 각 이웃에 대해 상수 시간 안에 주어진 정점의 이웃 목록을 보고하는 작업을 수행할 수 있다. 즉, 정점 ''v''의 모든 이웃을 보고하는 데 걸리는 총 시간은 ''v''의 차수에 비례한다.
인접 리스트를 사용하여 두 개의 지정된 정점 사이에 간선이 있는지 여부를 테스트하는 것도 가능하지만 효율적이지 않다. 각 정점의 이웃이 정렬되지 않은 인접 리스트에서는 간선의 존재 여부를 테스트하는 데 두 정점 중 더 작은 차수에 비례하는 시간이 걸릴 수 있다. 이 정점의 이웃을 순차 탐색하여 수행할 수 있다. 이웃이 정렬된 배열로 표시되면 이진 탐색을 사용하여 차수의 로그에 비례하는 시간이 걸린다.
4. 장단점
인접 행렬과 비교했을 때, 인접 리스트는 다음과 같은 장단점을 가진다.
인접 리스트는 희소 그래프(대부분의 정점 쌍이 간선으로 연결되지 않은 그래프)에서 인접 행렬보다 공간 효율성이 훨씬 높다. 인접 리스트는 그래프의 간선 및 정점 수에 비례하는 공간을 사용하는 반면, 인접 행렬은 정점 수의 제곱에 비례하는 공간을 차지한다. 다만, 해시 테이블을 사용하여 인접 행렬을 보다 공간 효율적으로 저장하면 인접 리스트의 선형 공간 사용량과 일치시킬 수 있다.
인접 리스트와 인접 행렬은 수행하는 작업의 효율성에서도 차이를 보인다. 인접 리스트에서는 각 정점의 이웃을 정점의 차수에 비례하는 시간 안에 효율적으로 나열할 수 있지만, 인접 행렬에서는 이 작업에 그래프의 정점 수에 비례하는 시간이 걸린다. 반면, 인접 행렬을 사용하면 두 정점이 서로 인접해 있는지 여부를 상수 시간에 확인할 수 있다.[1]
4. 1. 장점
인접 리스트는 인접 행렬에 비해 공간 효율성과 특정 연산에서의 효율성이 높다는 장점을 가진다.- 공간 효율성: 희소 그래프(대부분의 정점 쌍이 간선으로 연결되지 않은 그래프)의 경우, 인접 리스트는 인접 행렬보다 공간을 훨씬 적게 사용한다. 인접 리스트는 존재하는 간선과 정점의 수에 비례하는 공간만 사용하는 반면, 인접 행렬은 정점 수의 제곱에 비례하는 공간을 사용하기 때문이다.[1] 32비트 컴퓨터에서 단순 배열 구현을 사용하면, 무방향 그래프의 인접 리스트는 대략 바이트의 공간을 필요로 한다. (는 그래프의 간선 수)[2]
- 이웃 정점 탐색 효율성: 인접 리스트에서는 특정 정점에 인접한 모든 정점을 찾는 것이 효율적이다. 각 정점의 인접 리스트를 순회하면 되므로, 정점의 차수에 비례하는 시간 안에 수행할 수 있다. 반면, 인접 행렬에서는 전체 행을 스캔해야 하므로 그래프의 정점 수에 비례하는 시간이 걸린다.[1]
| 자료 구조 | 공간 복잡도 | 이웃 정점 탐색 시간 복잡도 | 두 정점 간 간선 존재 여부 확인 시간 복잡도 |
|---|---|---|---|
| 인접 리스트 | 정점의 차수에 비례 | 두 정점의 최소 차수에 비례 | |
| 인접 행렬 |
4. 2. 단점
인접 리스트는 인접 행렬에 비해 다음과 같은 단점을 갖는다.- 간선 존재 여부 확인 비효율성: 두 정점 사이에 간선이 존재하는지 확인하려면, 인접 리스트에서는 두 정점 중 차수(연결된 간선의 수)가 낮은 정점의 인접 리스트를 순회하며 확인해야 한다. 따라서 이 연산은 해당 정점의 차수에 비례하는 시간이 걸린다. 반면, 인접 행렬에서는 두 정점에 해당하는 행과 열의 값을 확인하면 되므로 상수 시간 안에 확인할 수 있다. 인접 리스트는 이 작업 속도가 느리다.[1]
- 밀집 그래프에서의 공간 비효율성: 밀집 그래프(대부분의 정점 쌍이 간선으로 연결된 그래프)의 경우, 인접 리스트는 인접 행렬보다 더 많은 공간을 차지할 수 있다. 그래프의 밀도()가 1/64보다 크면() 인접 행렬이 인접 리스트보다 공간 효율성이 더 좋다.[2] 여기서 는 간선의 수, 는 정점의 수이다. 따라서 그래프가 인접 리스트 표현을 정당화할 만큼 충분히 희소해야 한다.[3]
참조
[1]
웹사이트
Python Patterns — Implementing Graphs
https://www.python.o[...]
2014-08-17
[2]
서적
Introduction to Algorithms, Second Edition
MIT Press and McGraw-Hill
[3]
서적
Algorithm Design: Foundations, Analysis, and Internet Examples
John Wiley & Sons
[4]
웹사이트
Python Patterns — Implementing Graphs
http://www.python.or[...]
2009-06-25
[5]
서적
Introduction to Algorithms, Second Edition
MIT Press and McGraw-Hill
[6]
서적
Algorithm Design: Foundations, Analysis, and Internet Examples
John Wiley & Sons
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com