인접 리스트

Adjacency list
이 무방향 순환 그래프는 세 가지 순서가 지정되지 않은 목록 {b, c}, {a, c}, {a, b}으로 설명할 수 있습니다.

그래프 이론과 컴퓨터 과학에서 인접 리스트는 유한 그래프를 나타내기 위해 사용되는 순서 없는 리스트의 집합입니다.인접 리스트내의 순서 없는 리스트는, 그래프내의 특정의 정점의 네이버 세트를 나타내고 있습니다.이것은 컴퓨터 프로그램에서 일반적으로 사용되는 그래프 표현 중 하나입니다.

구현 상세

위의 그래프는 다음 인접 목록을 나타내고 있습니다.
a 에 인접한. b,c
b 에 인접한. a, c
c 에 인접한. AB

그래프의 인접 목록 표현은 그래프 내의 각 정점을 인접한 정점 또는 가장자리 집합과 관련짓습니다.이 기본 아이디어에는 여러 가지 변형이 있는데, 정점과 컬렉션 간의 연관성을 구현하는 방법, 컬렉션을 구현하는 방법, 정점과 가장자리 모두를 포함하는지 또는 정점과 가장자리만 포함하는지 여부, 그리고 정점과 모서리를 나타내기 위해 사용되는 객체의 종류에 따라 다릅니다.

  • Guido van Rossum에 의해 제안된 구현은 해시 테이블을 사용하여 그래프 내의 각 정점을 인접한 정점의 배열과 관련짓습니다.이 표현에서 정점은 해시 가능한 객체에 의해 표현될 수 있다.모서리를 [1]개체로 명시적으로 표현하지 않습니다.
  • Cormen 등은 정점이 인덱스 [2]번호로 표현되는 구현을 제안한다.이러한 표현은 정점 번호에 의해 색인화된 배열을 사용합니다. 여기서 각 정점의 배열 셀은 해당 정점의 인접 정점의 단일 링크 목록을 가리킵니다.이 표현에서 단일 링크 목록의 노드는 에지 개체로 해석될 수 있지만 각 에지에 대한 전체 정보를 저장하지 않으며(에지의 두 끝점 중 하나만 저장), 비방향 그래프에는 각 에지에 대해 두 개의 서로 다른 링크 목록 노드(2개의 끝점 각각에 대한 목록 내)가 있습니다.에지의 ts).
  • Goodrich와 Tamassia에 의해 제안된 객체 지향 발병 목록 구조는 특별한 클래스의 정점 객체와 가장자리 객체를 가지고 있다.각 정점 개체에는 인접 에지 개체를 나열하는 집합 개체를 가리키는 인스턴스 변수가 있습니다.각 모서리 객체는 [3]끝점에서 두 개의 정점 객체를 가리킵니다.이 버전의 인접 목록에서는 인접 정점이 직접 나열되는 버전보다 더 많은 메모리가 사용되지만 명시적인 엣지 개체가 존재하기 때문에 엣지에 대한 추가 정보를 저장할 때 유연성이 향상됩니다.

운용

인접 리스트 데이터 구조에 의해 실행되는 주요 조작은 특정 정점의 네이버목록을 보고하는 것입니다.위에서 설명한 구현 중 하나를 사용하면 네이버별로 일정 시간 내에 실행할 수 있습니다.즉, 정점 v의 모든 인접 관계를 보고하는 총 시간은 v의 정도에 비례한다.

인접 목록을 사용하여 지정된2개의 정점 사이에 엣지가 존재하는지 여부를 테스트할 수도 있지만 효율적이지는 않습니다.각 정점의 인접이 정렬되어 있지 않은 인접 리스트에서는, 이 정점의 인접을 통과하는 시퀀셜 서치를 이용하는 것으로, 주어진 2개의 정점의 최소도에 비례하는 시간에 엣지의 존재를 테스트할 수 있다.네이버가 정렬된 배열로 표시되는 경우 대신 이진 검색을 사용하여 정도의 대수에 비례하는 시간을 가질 수 있습니다.

트레이드오프

인접 리스트의 주요 대체는 인접 매트릭스입니다.이 매트릭스에는 행과 열이 정점에 의해 인덱스화되어 셀의 행과 열에 대응하는 정점 사이에 엣지가 존재하는지 여부를 나타내는 부울 값이 셀에 포함되어 있습니다.sparse 그래프(2차원 배열로 저장됨)의 경우 인접 리스트는 인접 매트릭스(2차원 배열로 저장됨)보다 훨씬 공간 효율적입니다.인접 리스트의 공간 사용량은 그래프 내의 엣지와 정점의 수에 비례하지만 인접 매트릭스는 ti에 저장됩니다.s 공간은 정점 수의 제곱에 비례합니다.그러나 배열이 아닌 정점 쌍으로 색인화된 해시 테이블을 사용함으로써 인접 행렬을 보다 공간 효율적으로 저장할 수 있으며 인접 목록의 선형 공간 효율은 인접 리스트의 선형 공간 사용량에 일치합니다.

인접 리스트와 인접 매트릭스의 또 다른 중요한 차이점은 실행하는 동작의 효율입니다.인접 리스트에서는 정점의 정도에 비례한 시간에 각 정점의 인접을 효율적으로 나열할 수 있다.인접행렬에서 이 연산은 그래프 내의 꼭지점 수에 비례하는 시간이 소요되며, 이는 정도보다 훨씬 높을 수 있습니다.한편, 인접 매트릭스에서는, 2개의 정점이 서로 인접하고 있는지를 일정시간 테스트할 수 있습니다.인접 리스트는 이 조작을 서포트하는 속도가 느립니다.

데이터 구조

데이터 구조로서 사용하는 경우, 인접 리스트의 주된 대체 방법은 인접 매트릭스입니다.인접 행렬의 각 엔트리는 1비트만 필요하기 때문에 V / 8바이트의 연속된 공간만을 차지하면서 매우 콤팩트하게 나타낼 수 있습니다.여기서 V는 그래프의 정점 수입니다.공간 낭비를 피할 수 있을 뿐만 아니라, 이 콤팩트함은 기준의 인접성을 촉진합니다.

단, 스퍼스 그래프의 경우 인접 리스트는 존재하지 않는 에지를 나타내기 위해 공간을 낭비하지 않기 때문에 필요한 공간이 줄어듭니다.32비트 컴퓨터에서 순진한 어레이 구현을 사용하는 경우, 무방향 그래프의 인접 목록에는 약 2µ(32/8) E = 8 E 바이트의 공간이 필요합니다. 여기서 E는 그래프의 가장자리 수입니다.

무방향 단순 그래프는 최대 (V - V )/2 µ 2 V의 에지를 가질 수 있으므로 루프가 허용되므로 d = E/V가 그래프의 밀도를 나타내도록 할 수 있습니다.다음으로 E / V > 1/64 의 경우는 8 E > V / 8 이 됩니다.즉, 인접 리스트 표현은 d > 1/64 의 경우는 인접 매트릭스 표현보다 많은 공간을 차지합니다.따라서 그래프는 인접 목록 표현을 정당화할 수 있을 만큼 충분히 희박해야 합니다.

공간 균형 외에도, 다양한 데이터 구조는 또한 다양한 운영을 촉진합니다.인접 리스트의 특정 정점에 인접한 모든 정점을 찾는 것은 목록을 읽는 것만큼이나 간단합니다.인접 매트릭스에서는 행 전체를 스캔해야 합니다.이것에 O(V)의 시간이 걸립니다.2개의 정점 사이에 엣지가 있는지 아닌지는 인접 매트릭스를 사용하여 동시에 판별할 수 있으며 인접 리스트가 있는2개의 정점의 최소 정도에 비례하는 시간이 필요합니다.

레퍼런스

  1. ^ van Rossum, Guido (1998). "Python Patterns — Implementing Graphs".
  2. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill. pp. 527–529 of section 22.1: Representations of graphs. ISBN 0-262-03293-7.
  3. ^ Goodrich, Michael T.; Tamassia, Roberto (2002). Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons. ISBN 0-471-38365-1.

추가 정보

외부 링크

Wikimedia Commons에는 인접 목록과 관련된 미디어가 있습니다.