그래프 저장을 위한 데이터 구조: 기존 항목 검토 및 "거의 새로운" 항목 XNUMX개 검토

안녕 모두

이 노트에서 나는 컴퓨터 과학에서 그래프를 저장하는 데 사용되는 주요 데이터 구조를 나열하기로 결정했으며, 나에게 "결정화"된 몇 가지 구조에 대해서도 더 이야기하겠습니다.

그럼 시작해 보겠습니다. 하지만 맨 처음부터 그런 것은 아닙니다. 제 생각에는 우리 모두가 이미 그래프가 무엇인지, 그래프가 무엇인지(방향성, 방향성 없음, 가중치 부여, 가중치 없음, 다중 모서리 및 루프 유무)를 알고 있다고 생각합니다.

자, 가자. "그래프 저장"을 위한 데이터 구조에는 어떤 옵션이 있나요?

1. 행렬 데이터 구조

1.1 인접 행렬. 인접 행렬(Adjacency Matrix)은 행과 열의 제목이 그래프의 꼭지점 개수에 해당하는 행렬이며, 각 요소 a(i,j)의 값은 꼭지점 사이의 간선 유무에 따라 결정됩니다. i와 j(무방향 그래프의 경우 이러한 행렬은 대칭이거나 모든 값을 주 대각선 위에만 저장한다는 데 동의할 수 있음이 분명합니다). 가중치가 적용되지 않은 그래프의 경우 a(i,j)는 i에서 j까지의 간선 수로 설정될 수 있으며(그러한 간선이 없으면 a(i,j)= 0), 가중치가 적용된 그래프의 경우에도 가중치로 설정될 수 있습니다. (총 무게) 언급된 가장자리.

1.2 사건 매트릭스. 이 경우 그래프는 일반적으로 행 번호가 정점 수에 해당하고 열 번호가 미리 번호가 매겨진 가장자리에 해당하는 테이블에도 저장됩니다. 꼭지점과 모서리가 서로 일치하는 경우 해당 셀에 1이 아닌 값이 기록됩니다(무방향 그래프의 경우 꼭지점과 모서리가 일치하면 1이 기록되고 지향성 그래프의 경우 모서리가 "1"로 기록됨) 꼭지점에서 "종료"되고 정점에 "포함"된 경우 "-1"입니다("마이너스" 기호도 숫자 "-1"에 "포함"된 것처럼 보이기 때문에 기억하기 쉽습니다). 가중치 그래프의 경우 1과 -XNUMX 대신 간선의 총 가중치를 지정할 수 있습니다.

2. 열거형 데이터 구조

2.1 인접 목록. 글쎄, 여기서는 모든 것이 간단한 것 같습니다. 그래프의 각 정점은 일반적으로 주어진 정점에 인접한 모든 정점의 수를 저장하는 열거형 구조(목록, 벡터, 배열 등)와 연관될 수 있습니다. 방향성 그래프의 경우, 특징 정점에서 "방향성" 가장자리가 있는 정점만 목록에 추가합니다. 가중치 그래프의 경우 구현이 더 복잡해집니다.

2.2 갈비뼈 목록. 꽤 대중적인 데이터 구조입니다. Captain Obviousness가 말했듯이 가장자리 목록은 실제로 그래프의 가장자리 목록이며, 각 가장자리는 시작 정점, 끝 정점으로 지정됩니다(무방향 그래프의 경우 여기서 순서는 중요하지 않지만 통합을 위해서는 다음을 수행할 수 있습니다). 예를 들어 정점을 증가하는 순서로 지정하고 가중치(가중치 그래프에만 해당)를 지정하는 등 다양한 규칙을 사용합니다.

위에 나열된 매트릭스 목록을 더 자세히(및 그림과 함께) 볼 수 있습니다. 예를 들면 다음과 같습니다. 여기에.

2.3 인접 배열. 가장 일반적인 구조는 아닙니다. 핵심은 인접 목록을 하나의 열거형 구조(배열, 벡터)로 "패킹"하는 형식입니다. 이러한 배열의 처음 n개(그래프의 정점 수에 따라) 요소에는 동일한 배열의 시작 인덱스가 포함되어 있으며, 이 인덱스부터 시작하여 주어진 배열에 인접한 모든 정점이 연속으로 기록됩니다.

여기에서 (나 자신에게) 가장 이해하기 쉬운 설명을 찾았습니다. ejuo.livejournal.com/4518.html

3. 인접 벡터와 연관 인접 배열

전문 프로그래머는 아니지만 주기적으로 그래프를 처리하는 이 줄의 작성자는 가장자리 목록을 가장 자주 처리하는 것으로 나타났습니다. 실제로 그래프에 루프와 간선이 여러 개 있으면 편리합니다. 따라서 고전적인 모서리 목록을 개발할 때 "개발/분기/수정/돌연변이", 즉 인접 벡터와 연관 인접 배열에 주의를 기울일 것을 제안합니다.

3.1 인접 벡터

사례 (a1): 비가중 그래프

비가중 그래프에 대한 인접 벡터를 짝수 정수(a[2i], a[2i+1],..., 여기서 i의 번호는 c 0)의 순서 집합이라고 부릅니다. 여기서 각 숫자 쌍은 a[2i], a[2i+1 ]은 정점 a[2i]와 a[2i+1] 사이의 그래프 가장자리를 각각 지정합니다.
이 기록 형식에는 그래프 방향 여부에 대한 정보가 포함되어 있지 않습니다(두 옵션 모두 가능). digraph 형식을 사용할 때 모서리는 a[2i]에서 a[2i+1]로 향하는 것으로 간주됩니다. 여기 및 아래: 무방향 그래프의 경우 필요한 경우 정점 기록 순서에 대한 요구 사항을 적용할 수 있습니다(예: 할당된 숫자의 값이 낮은 정점이 먼저 옵니다).

C++에서는 std::Vector를 사용하여 인접 벡터를 지정하는 것이 좋습니다. 따라서 이 데이터 구조의 이름이 됩니다.

사례 (a2): 비가중 그래프, 간선 가중치는 정수입니다.

사례 (a1)과 유사하게 정수 간선 가중치를 갖는 가중치 그래프에 대한 인접 벡터를 숫자의 정렬된 집합(동적 배열)(a[3i], a[3i+1], a[3i+2], ..., 여기서 i의 번호는 c 0), 여기서 숫자 a[3i], a[3i+1], a[3i+2]의 각 "삼중항"은 a[3i] 번호의 꼭지점 사이의 그래프 가장자리를 지정합니다. 및 a[3i+1]이며, 값 a [3i+2]는 이 간선의 가중치입니다. 이러한 그래프는 방향이 지정될 수도 있고 그렇지 않을 수도 있습니다.

사례 (b): 비가중 그래프, 정수가 아닌 간선 가중치

예를 들어, 이종 요소를 하나의 배열(벡터)에 저장하는 것은 불가능하므로 다음과 같은 구현이 가능합니다. 그래프는 한 쌍의 벡터에 저장됩니다. 여기서 첫 번째 벡터는 가중치를 지정하지 않은 그래프의 인접 벡터이고 두 번째 벡터에는 해당 가중치가 포함됩니다(C++에 대한 구현 가능: std::pair). ). 따라서 첫 번째 벡터의 인덱스 2i, 2i+1 아래에 있는 정점 쌍으로 정의된 가장자리의 경우 가중치는 두 번째 벡터의 인덱스 i 아래에 있는 요소와 동일합니다.

그렇다면 이것이 왜 필요한가요?

글쎄, 이 줄의 저자는 이것이 여러 문제를 해결하는 데 매우 유용하다는 것을 알았습니다. 음, 공식적인 관점에서 보면 다음과 같은 장점이 있습니다.

• 다른 "열거형" 구조와 마찬가지로 인접 벡터는 매우 컴팩트하고 인접 행렬(희소 그래프의 경우)보다 메모리를 덜 차지하며 상대적으로 구현하기 쉽습니다.
• 그래프의 꼭지점은 원칙적으로 음수로 표시될 수도 있습니다. 그러한 “변태”가 필요하다면 어떻게 될까요?
• 그래프에는 가중치가 서로 다른(양수, 음수, XNUMX까지) 여러 개의 간선과 여러 루프가 포함될 수 있습니다. 여기에는 제한이 없습니다.
• 가장자리에 다른 속성을 할당할 수도 있습니다. 이에 대한 자세한 내용은 섹션 4를 참조하세요.

그러나 이 "목록"이 가장자리에 대한 빠른 액세스를 의미하지는 않는다는 점을 인정해야 합니다. 그리고 여기서 연관 인접 배열(Associative Adjacency Array)이 구출됩니다. 이에 대해서는 아래에서 설명합니다.

3.2 연관 인접 배열

따라서 특정 가장자리에 대한 액세스, 가중치 및 기타 속성이 중요하고 메모리 요구 사항으로 인해 인접 행렬을 사용할 수 없는 경우 인접 벡터를 변경하여 이 문제를 해결하는 방법에 대해 생각해 보겠습니다. 따라서 키는 그래프의 가장자리이며, 순서화된 정수 쌍으로 지정될 수 있습니다. 이것은 어떻게 생겼나요? 연관 배열의 키가 아닌가요? 그렇다면 구현해 보는 것은 어떨까요? 각 키(순수한 정수 쌍)가 값(가장자리의 가중치를 지정하는 정수 또는 실수)과 연관되는 연관 배열을 만들어 보겠습니다. C++에서는 std::map 컨테이너(std::map)를 기반으로 이 구조를 구현하는 것이 좋습니다. , int> 또는 std::map , double>) 또는 std::multimap(여러 모서리가 예상되는 경우). 글쎄요, 우리는 "행렬" 구조보다 메모리를 덜 차지하는 그래프 저장 구조를 가지고 있고, 여러 개의 루프와 모서리가 있는 그래프를 정의할 수 있으며, 꼭지점 번호의 음수가 아닌지에 대한 엄격한 요구 사항도 없습니다(모르겠어요). 누가 이것을 필요로 하지만 여전히).

4. 데이터 구조는 꽉 차 있지만 뭔가 빠졌습니다.

그리고 그것은 사실입니다. 많은 문제를 해결할 때 그래프 가장자리에 몇 가지 특성을 할당하고 그에 따라 저장해야 할 수도 있습니다. 이러한 특성을 명확하게 정수로 줄이는 것이 가능하다면 인접 벡터 및 연관 인접 배열의 확장 버전을 사용하여 이러한 "추가 특성이 있는 그래프"를 저장할 수 있습니다.

예를 들어 정수로 지정된 2개의 추가 기능을 저장하는 데 필요한 각 모서리에 대해 가중치가 적용되지 않은 그래프를 만들어 보겠습니다. 이 경우 인접 벡터를 "쌍"이 아닌 정수 "2중주"(a[2i], a[1i+2], a[2i+2], a)의 순서 집합으로 정의할 수 있습니다. [3i+2]…) 여기서 a[2i+2] 및 a[3i+2]은 해당 가장자리의 특성을 결정합니다. 간선의 정수 가중치를 갖는 그래프의 경우 순서는 일반적으로 유사합니다(유일한 차이점은 속성이 간선의 가중치를 따르고 a[3i+2] 및 a[4i+4] 요소로 지정된다는 것입니다. , 가장자리 자체는 5가 아닌 XNUMX개의 순서 번호로 지정됩니다). 그리고 정수가 아닌 간선 가중치가 있는 그래프의 경우 특징은 가중치가 적용되지 않은 구성 요소에 기록될 수 있습니다.

정수 간선 가중치가 있는 그래프에 대해 연관 인접 배열을 사용하는 경우 단일 숫자가 아닌 간선 가중치 외에 필요한 다른 모든 값을 지정하는 숫자 배열(벡터)을 값으로 지정할 수 있습니다. 특징. 동시에, 정수가 아닌 가중치의 경우 불편한 점은 부동 소수점 숫자로 부호를 지정해야 한다는 것입니다. (예, 불편합니다. 그러나 그러한 부호가 많지 않고 그렇지 않은 경우 너무 "까다롭게" 이중으로 설정하지 마십시오. 그러면 아무것도 아닐 수도 있습니다. 이는 C++에서 확장된 연관 인접 배열을 다음과 같이 정의할 수 있음을 의미합니다: std::map , std::벡터> 또는 std::map , std::벡터, 여기서 "키-값-벡터"의 첫 번째 값은 가장자리의 가중치가 되고 그 다음에는 해당 특성의 숫자 지정이 위치합니다.

문학 :

일반적인 그래프 및 알고리즘 정보:

1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. 알고리즘: 구성 및 분석, 2판: Trans. 영어로부터 – M.: 윌리엄스 출판사, 2011.
2. 하라리 프랭크. 그래프 이론. M.: 미르, 1973.
동일한 벡터 및 인접 요소의 연관 배열에 대한 저자의 보고서:
3. Chernoukhov S.A. 그래프를 표현하고 저장하는 방법으로서의 인접 벡터 및 연관 인접 배열 / SA Chernouhov. 그래프를 표현하기 위한 데이터 구조로서의 인접 벡터 및 인접 맵 // 국제 과학 및 실무 회의의 기사 모음 "혁신적인 개발 결과 구현 문제 및 이를 해결하는 방법"(Saratov, 14.09.2019년 2019월 65일) – Sterlitamak: AMI, 69, p. XNUMX-XNUMX
주제에 대한 유용한 온라인 소스:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

출처 : habr.com