그래프(추상 데이터 유형)

세 개의 꼭지점(파란색 원)과 세 개의 모서리(검은색 화살표)가 있는 방향 그래프입니다.

컴퓨터 과학에서 그래프는 수학 내 그래프 이론 분야에서 무방향 그래프와 방향 그래프 개념을 구현하기 위한 추상 데이터 유형입니다.

그래프 데이터 구조는 유한한(그리고 아마도 변이 가능한) 정점 집합(노드 또는 점이라고도 함)과 무방향 그래프에 대한 이들 정점의 순서 없는 쌍 집합 또는 방향 그래프에 대한 순서 있는 쌍 집합으로 구성됩니다.이러한 쌍을 에지(링크 또는 선이라고도 함)라고 하며, 방향 그래프의 경우 에지라고도 하지만 화살표 또는 호라고도 합니다.정점은 그래프 구조의 일부이거나 정수 지수 또는 참조로 표현되는 외부 도면요소일 수 있습니다.

그래프 데이터 구조는 심볼 라벨 또는 수치 속성(비용, 용량, 길이 등)과 같은 일부 에지 값을 각 에지에 관련지을 수도 있다.

운용

그래프 데이터 구조 G에 의해 제공되는 기본 연산은 일반적으로 다음과 같습니다.^[1]

인접(G, x, y): 정점 x에서 정점 y까지의 가장자리가 있는지 테스트한다.
neighbors(G, x): 정점 x에서 정점 y까지의 가장자리가 되도록 모든 정점 y를 나열합니다.
add_vertex(G, x): 정점 x가 없는 경우 추가한다.
remove_vertex(G, x): 꼭지점 x가 있는 경우 삭제합니다.
add_edge(G, x, y, z): 모서리 z가 정점 x에서 정점 y에 추가된다(없는 경우).
remove_edge(G, x, y): 꼭지점 x에서 꼭지점 y(있는 경우)까지의 가장자리를 제거합니다.
get_vertex_value(G, x): 정점 x와 관련된 값을 반환합니다.
set_vertex_value(G, x, v): 정점 x와 관련된 값을 v로 설정합니다.

값을 모서리에 연결하는 구조도 일반적으로 다음을 제공합니다.^[1]

get_edge_value(G, x, y): 에지(x, y)와 관련된 값을 반환합니다.
set_edge_value(G, x, y, v): 에지(x, y)와 관련된 값을 v로 설정합니다.

그래프 표현을 위한 공통 데이터 구조

인접 리스트^[2]: 정점은 레코드 또는 객체로 저장되며, 모든 정점은 인접한 정점 목록을 저장합니다.이 데이터 구조를 통해 정점에 추가 데이터를 저장할 수 있습니다.모서리가 개체로도 저장되는 경우 추가 데이터를 저장할 수 있습니다. 이 경우 각 정점은 입사 모서리를 저장하고 각 모서리는 입사 정점을 저장합니다.
인접 행렬^[3]: 행은 소스 정점을 나타내고 열은 대상 정점을 나타내는 2차원 행렬입니다.모서리 및 정점의 데이터는 외부에 저장해야 합니다.각 정점 쌍 사이에 하나의 모서리에 대한 비용만 저장할 수 있습니다.
발생행렬^[4]: 행은 정점을 나타내고 열은 모서리를 나타내는 2차원 행렬입니다.항목은 행의 정점과 열의 모서리 사이의 발생 관계를 나타냅니다.

다음 표는 그래프에서 이러한 표현 각각에 대해 V의 정점 수와 E의 ^{[citation needed]}가장자리 수를 사용하여 다양한 연산을 수행하는 데 소요되는 시간 복잡도 비용을 보여 줍니다.매트릭스 표현에서 엔트리는 에지를 따르는 비용을 부호화합니다.존재하지 않는 에지의 비용은 µ로 가정한다.

	인접 리스트	인접 행렬	발생행렬
그래프 저장	$O(V + E)$	$O(V^{2})$	$O(V \cdot E)$
정점 추가	$O(1)$	$O(V^{2})$	$O(V \cdot E)$
가장자리 추가	$O(1)$	$O(1)$	$O(V \cdot E)$
정점 제거	$O(E)$	$O(V^{2})$	$O(V \cdot E)$
가장자리 제거	$O(V)$	$O(1)$	$O(V \cdot E)$
정점 x와 y가 인접해 있습니까(저장 위치가 알려진 것으로 가정).	$O(V)$	$O(1)$	$O(E)$
언급	모든 정점 또는 모서리를 찾아야 하므로 정점과 모서리를 제거하는 데 시간이 걸립니다.	행렬의 크기를 조정/복사해야 하므로 정점 추가 또는 제거 속도가 느립니다.	행렬의 크기를 조정/복사해야 하므로 정점과 모서리를 추가하거나 제거하는 데 시간이 걸립니다.

일반적으로 인접 리스트는 스퍼스 그래프의 표현에 선호되지만, 그래프의 밀도가 높은 경우(즉, 엣지 수E가 정점 제곱의 V에 가깝거나 2개의 ^[5]^[6]정점을 접속하는 엣지가 있는 경우 신속하게 조회할 수 있어야 하는 경우)에는 인접 매트릭스가 선호됩니다.

병렬 표현

그래프 문제의 병렬화는 데이터 중심 연산, 구조화되지 않은 문제, 낮은 지역성, 높은 데이터 접근률 ^[7]^[8]등 중대한 과제에 직면해 있습니다.병렬 아키텍처에 사용되는 그래프 표현은 이러한 과제에 대처하는 데 중요한 역할을 합니다.표현이 잘못 선택되면 알고리즘의 통신 비용이 불필요하게 증가하여 확장성이 저하될 수 있습니다.여기에서는 공유 메모리 아키텍처와 분산 메모리 아키텍처에 대해 설명합니다.

공유 메모리

공유 메모리 모델의 경우, 그래프 표현(예를 들어 인접 리스트)에 대한 병렬 읽기 전용 액세스가 공유 메모리 내에서 효율적이기 때문에 병렬 처리에 사용되는 그래프 표현은 순차적인 ^[9]경우와 동일하다.

분산 메모리

분산 메모리 모델에서는 그래프의 정점 $집합$ V(\ $displaystyle$ V $)$ 를 $V$ p $(\displaystyle$ p $)$ $V_{0},\dots ,V_{p-1}$ V $V_{0},\dots ,V_{p-1}$ $V_{0},\dots ,V_{p-1}$ $V_{0},\dots ,V_{p-1}$ p - $V_{0},\dots ,V_{p-1}$ (\ $displaystyle V_{0},\dots,V_{p-1$ 로 분할하는 것이 일반적입니다.여기서 p $(\displaystylement$ p $)$ 는 사용 가능한 처리 요소(PE)의 양입니다.그런 다음 정점 집합 파티션은 일치하는 인덱스와 함께 해당 모서리에 추가로 PE로 배포됩니다.모든 PE에는 자체 서브그래프 표현이 있습니다.다른 파티션에 엔드포인트가 있는 엣지는 특별한 주의가 필요합니다.MPI 등의 표준 통신 인터페이스의 경우 다른 쪽 엔드포인트를 소유하는 PE의 ID를 식별할 수 있어야 합니다.분산 그래프 알고리즘의 계산 중에 이러한 에지를 따라 정보를 전달하는 것은 ^[9]통신을 의미합니다.

그래프의 분할은 신중하게 실시할 필요가 있습니다.-낮은 통신과 짝수 크기의^[10] 분할 사이에 균형이 있습니다.그러나 그래프를 분할하는 것은 NP-난해한 문제이기 때문에 계산할 수 없습니다.대신 다음과 같은 휴리스틱이 사용됩니다.

1D 파티셔닝:모든 프로세서는 n $p(\displaystyle$ n $/p)$ 의 $n/p$ 정점과 대응하는 발신 에지를 $n/p$ .이는 인접 행렬의 행 단위 또는 열 단위 분해로 이해할 수 있습니다.이 표현으로 동작하는 알고리즘에서는 각 PE가 다른 모든 ^[11]PE에 대해 발신 에지를 가질 가능성이 있기 때문에 All-to-All 통신 ${\mathcal {O}}(m)$ 과 O $)\displaystyle {O}(m)$ 메시지버퍼 ${\mathcal {O}}(m)$ 사이즈가 필요합니다.

2D 파티셔닝:각 프로세서는 인접 매트릭스의 서브매트릭스를 취득합니다.프로세서가 $p=p_{r}\times p_{c}$ p $p=p_{r}\times p_{c}$ r × $p=p_{r}\times p_{c}$ p $p=p_{r}\times p_{c}$ { $displaystyle$ p $p_{r}$ $= p_{$ $r$ } \ $times$ p_ ${$ c $p=p_{r}\times p_{c}$ 로 정렬되어 있다고 가정합니다. $p_{r}$ 서 p $p_{r}$ r { $displaystyle p_{$ r $p_{r}$ }} 및 $p_{c}$ { $displaystyle p_{c$ }}는 $p_{c}$ 각 행과 열의 처리 요소의 양입니다.다음으로 각 프로세서는 $(n/p_{r})\times (n/p_{c})$ ( $(n/p_{r})\times (n/p_{c})$ / $(n/p_{r})\times (n/p_{c})$ r $(n/p_{r})\times (n/p_{c})$ ) $(n/p_{r})\times (n/p_{c})$ × ( $(n/p_{r})\times (n/p_{c})$ / $(n/p_{r})\times (n/p_{c})$ c $(n/p_{r})\times (n/p_{c})$ ) \ $display$ style ( $n$ / $p$ _ { $r$ ) \ times ( $n$ / $p$ _ { $c$ } $(n/p_{r})\times (n/p_{c})$ 의 인접 매트릭스의 서브 매트릭스를 가져옵니다.이것은 매트릭스에서 ^[11]체커보드 패턴으로 시각화할 수 있습니다.따라서 각 처리 장치는 동일한 행과 열에 있는 PE에 대한 나가는 가장자리만 가질 수 있습니다.이는 각 PE의 통신 파트너의 수를 $p_{r}+p_{c}-1$ $p=p_{r}\times p_{c}$ $p=p_{r}\times p_{c}$ r × $p=p_{r}\times p_{c}$ { $display style$ p $p_{r}+p_{c}-1$ $= p$ _ $r$ } \ $times$ p _ { $c$ $}$ $p=p_{r}\times p_{c}$ 중 $p_{r}+p_{c}-1$ $r$ + p $p_{r}+p_{c}-1$ - $1개$ 로 $p_{r}+p_{c}-1$ $제한$ 합니다.

압축 표현

수조 개의 모서리를 가진 그래프는 기계 학습, 소셜 네트워크 분석 및 기타 영역에서 발생합니다.I/O 및 메모리 요건을 줄이기 위해 압축 그래프 표현이 개발되었습니다.Huffman 코딩 등의 일반적인 기술을 적용할 수 있지만,^[12] 인접 목록 또는 인접 매트릭스를 특정 방법으로 처리하여 효율성을 높일 수 있습니다.

「」를 참조해 주세요.

그래프 워킹 전략을 위한 그래프 트래버설
그래프(데이터 구조) 지속성을 위한 그래프 데이터베이스
그래프의 규칙 기반 변환을 위한 그래프 다시 쓰기(그래프 데이터 구조)
그래프를 그리기 위한 소프트웨어, 시스템 및 시스템 공급자를 위한 그래프 그리기 소프트웨어

레퍼런스

^ ^a ^b 예: Goodrich & Tamassia (2015), 섹션 13.1.2: 그래프에서의 연산, 페이지 360을 참조하십시오.조작의 상세한 것에 대하여는, 을 참조해 주세요.Mehlhorn, K.; Näher, S. (1999). "Chapter 6: Graphs and their data structures". LEDA: A platform for combinatorial and geometric computing (PDF). Cambridge University Press. pp. 240–282.
^ 코멘 등 (2001), 페이지 528–529; Goodrich & Tamassia (2015), 페이지 361-362.
^ 코멘 등 (2001), 페이지 529-530; Goodrich & Tamassia (2015), 페이지 363.
^ 코멘 등 (2001), 연습 22.1-7, 페이지 531.
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 22.1: Representations of graphs". Introduction to Algorithms (Second ed.). MIT Press and McGraw-Hill. pp. 527–531. ISBN 0-262-03293-7.
^ Goodrich, Michael T.; Tamassia, Roberto (2015). "Section 13.1: Graph terminology and representations". Algorithm Design and Applications. Wiley. pp. 355–364. ISBN 978-1-118-33591-8.
^ Bader, David; Meyerhenke, Henning; Sanders, Peter; Wagner, Dorothea (January 2013). Graph Partitioning and Graph Clustering. Contemporary Mathematics. Vol. 588. American Mathematical Society. doi:10.1090/conm/588/11709. ISBN 978-0-8218-9038-7.
^ Lumsdaine, Andrew; Gregor, Douglas; Hendrickson, Bruce; Berry, Jonathan (March 2007). "Challenges in Parallel Graph Processing". Parallel Processing Letters. 17 (1): 5–20. doi:10.1142/s0129626407002843. ISSN 0129-6264.
^ ^a ^b Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox. Springer International Publishing. ISBN 978-3-030-25208-3.
^ "Parallel Processing of Graphs" (PDF).
^ ^a ^b Buluç, A.; Madduri, Kamesh (2011). "Applications". Parallel breadth-first search on distributed memory systems. 2011 International Conference for High Performance Computing, Networking, Storage and Analysis. doi:10.1145/2063384.2063471. ISBN 978-1-4503-0771-0. S2CID 6540738.
^ Besta, Maciej; Hoefler, Torsten (27 April 2019). "Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations". arXiv:1806.01799 [cs.DS].

외부 링크

Boost Graph Library: 강력한 C++ 그래프 라이브러리 s.a.Boost (C++ 라이브러리)
Networkx: Python 그래프 라이브러리
GraphMatcher는 유도/무방향 그래프를 정렬하는 Java 프로그램입니다.
GraphBLAS: 그래프 연산을 위한 라이브러리 인터페이스의 규격으로, 특히 스파스 그래프에 초점을 맞춥니다.

[gt-ops-1] 예: Goodrich & Tamassia (2015), 섹션 13.1.2: 그래프에서의 연산, 페이지 360을 참조하십시오.조작의 상세한 것에 대하여는, 을 참조해 주세요.Mehlhorn, K.; Näher, S. (1999). "Chapter 6: Graphs and their data structures". LEDA: A platform for combinatorial and geometric computing (PDF). Cambridge University Press. pp. 240–282.

[2] 코멘 등 (2001), 페이지 528–529; Goodrich & Tamassia (2015), 페이지 361-362.

[3] 코멘 등 (2001), 페이지 529-530; Goodrich & Tamassia (2015), 페이지 363.

[4] 코멘 등 (2001), 연습 22.1-7, 페이지 531.

[clrs-5] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 22.1: Representations of graphs". Introduction to Algorithms (Second ed.). MIT Press and McGraw-Hill. pp. 527–531. ISBN 0-262-03293-7.

[gt-6] Goodrich, Michael T.; Tamassia, Roberto (2015). "Section 13.1: Graph terminology and representations". Algorithm Design and Applications. Wiley. pp. 355–364. ISBN 978-1-118-33591-8.

[Bader2013-7] Bader, David; Meyerhenke, Henning; Sanders, Peter; Wagner, Dorothea (January 2013). Graph Partitioning and Graph Clustering. Contemporary Mathematics. Vol. 588. American Mathematical Society. doi:10.1090/conm/588/11709. ISBN 978-0-8218-9038-7.

[8] Lumsdaine, Andrew; Gregor, Douglas; Hendrickson, Bruce; Berry, Jonathan (March 2007). "Challenges in Parallel Graph Processing". Parallel Processing Letters. 17 (1): 5–20. doi:10.1142/s0129626407002843. ISSN 0129-6264.

[Sanders2019-9] Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox. Springer International Publishing. ISBN 978-3-030-25208-3.

[10] "Parallel Processing of Graphs" (PDF).

[Buluc2011-11] Buluç, A.; Madduri, Kamesh (2011). "Applications". Parallel breadth-first search on distributed memory systems. 2011 International Conference for High Performance Computing, Networking, Storage and Analysis. doi:10.1145/2063384.2063471. ISBN 978-1-4503-0771-0. S2CID 6540738.

[12] Besta, Maciej; Hoefler, Torsten (27 April 2019). "Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations". arXiv:1806.01799 [cs.DS].

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

v t 그래프 표현
데이터 구조	그래프(추상 데이터 유형) 인접 리스트 에지 리스트 인접 행렬 발생행렬
XML 기반 형식	DGML DotML GEXF GraphML GXL XGMML
텍스트 기반 형식	점 그래프 모델링 언어(GML) 해밀턴 입방 그래프에 대한 LCF 표기법 트리의 Newick 형식 Trivial 그래프 형식
관련 개념	그래프 데이터베이스 그래프 그리기 링크된 데이터

v t 잘 알려진 데이터 구조
종류들	수집 컨테이너.
추상적인	연관 배열 멀티맵 데이터 구조 검색 목록. 스택 큐 더블 엔드 큐 priority 큐 이중 엔드 priority 큐 세트 멀티셋 디조인트 세트
어레이	비트 배열 순환 버퍼 다이내믹 어레이 해시 테이블 해시 어레이 트리 희박 행렬
링크되어 있다	어소시에이션리스트 링크 리스트 스킵 리스트 언롤링된 링크 리스트 XOR 링크 리스트
나무들	B-트리 이진 검색 트리 AA나무 AVL 트리 붉은색-검은색 셀프밸런싱 트리 스플레이 트리 히프 이진 힙 이항 힙 피보나치 힙 R 트리 R* 트리 R+ 트리 힐베르트 R-트리 트리 해시 트리
그래프	이항 결정도 방향 비순환 그래프 지시 비순환 단어 그래프
데이터 구조 목록

Search

그래프(추상 데이터 유형)

네임스페이스

더

목차

운용

그래프 표현을 위한 공통 데이터 구조

병렬 표현

공유 메모리

분산 메모리

압축 표현

「」를 참조해 주세요.

레퍼런스

외부 링크

Search

그래프(추상 데이터 유형)

운용

그래프 표현을 위한 공통 데이터 구조

병렬 표현

공유 메모리

분산 메모리

압축 표현

「 」를 참조해 주세요.

레퍼런스

외부 링크

「」를 참조해 주세요.