그래프 (자료 구조)

3. 그래프 표현의 선택

그래프의 크기, 밀도, 그리고 수행할 연산의 종류에 따라 적절한 표현 방식을 선택해야 한다. 희소 그래프는 인접 리스트가, 조밀 그래프는 인접 행렬이 일반적으로 효율적이다. 알고리즘의 요구 사항에 따라 추가적인 데이터를 저장해야 하는 경우도 있다.^[5][6]

• 인접 리스트: 정점은 레코드 또는 객체로 저장되며, 각 정점은 인접한 정점의 리스트를 저장한다. 이 데이터 구조를 사용하면 정점에 대한 추가 데이터를 저장할 수 있다. 간선도 객체로 저장하는 경우, 각 정점은 연결된 간선을 저장하고 각 간선은 연결된 정점을 저장하므로 추가 데이터를 저장할 수 있다.^[2]
• 인접 행렬: 2차원 행렬로, 행은 출발 정점을 나타내고 열은 도착 정점을 나타낸다. 간선 및 정점에 대한 데이터는 외부에 저장해야 한다. 각 정점 쌍 사이에 하나의 간선에 대한 비용만 저장할 수 있다.^[3]
• 사고 행렬: 2차원 행렬로, 행은 정점을 나타내고 열은 간선을 나타낸다. 항목은 행의 정점과 열의 간선 사이의 사고 관계를 나타낸다.^[4]

일반적으로 희소 그래프는 인접 리스트로 표현하는 것이 좋고, 그래프가 조밀하여 간선 $|E|$의 수가 정점의 제곱 $|V|^2$에 가깝거나, 두 정점을 연결하는 간선이 있는지 빠르게 찾아야 하는 경우에는 인접 행렬이 선호된다. 매우 큰 그래프에서 간선에 어떠한 규칙성이 있는 경우, 심볼릭 그래프라는 표현도 고려할 수 있다.

4. 그래프 연산

4. 1. 기본 연산

• adjacent(''G'', ''x'', ''y''): 정점 ''x''에서 정점 ''y''로의 간선이 있는지 확인한다.
• neighbors(''G'', ''x''): 정점 ''x''에 인접한 모든 정점 ''y''를 나열한다.
• add_vertex(''G'', ''x''): 정점 ''x''를 추가한다.
• remove_vertex(''G'', ''x''): 정점 ''x''를 제거한다.
• add_edge(''G'', ''x'', ''y'', ''z''): 정점 ''x''에서 정점 ''y''로의 간선 ''z''를 추가한다.
• remove_edge(''G'', ''x'', ''y''): 정점 ''x''에서 정점 ''y''로의 간선을 제거한다.
• get_vertex_value(''G'', ''x''): 정점 ''x''와 연관된 값을 반환한다.
• set_vertex_value(''G'', ''x'', ''v''): 정점 ''x''와 연관된 값을 ''v''로 설정한다.

• get_edge_value(''G'', ''x'', ''y''): 간선 (''x'', ''y'')와 연관된 값을 반환한다.
• set_edge_value(''G'', ''x'', ''y'', ''v''): 간선 (''x'', ''y'')와 연관된 값을 ''v''로 설정한다.

4. 2. 그래프 탐색

4. 2. 1. 너비 우선 탐색 (BFS, Breadth-First Search)

4. 2. 2. 깊이 우선 탐색 (DFS, Depth-First Search)

4. 3. 최단 경로 알고리즘

4. 4. 최대 유량 알고리즘

5. 병렬 그래프 표현

병렬 아키텍처에 사용되는 그래프 표현은 데이터 기반 계산, 비정형 문제, 낮은 지역성, 높은 데이터 접근 대 계산 비율과 같은 과제에 대처하는 데 중요한 역할을 한다.^[8][9] 잘못된 표현은 알고리즘의 통신 비용을 불필요하게 증가시켜 확장성을 감소시킬 수 있다.

공유 메모리 모델의 경우, 병렬 처리에 사용되는 그래프 표현은 순차적인 경우와 동일하다.^[10] 인접 리스트와 같은 공유 메모리에서 그래프 표현에 대한 병렬 읽기 전용 접근이 효율적이기 때문이다.

분산 메모리 모델에서는 그래프의 정점 집합 $V$를 사용 가능한 처리 요소(PE)의 수 $p$개의 집합 $V\_0,\; \backslash dots,\; V\_\{p-1\}$로 분할한다. 분할된 정점 집합은 해당 간선과 함께 일치하는 인덱스를 가진 PE에 분산된다. 각 PE는 자체 부분 그래프 표현을 가지며, 다른 분할에 끝점을 가진 간선은 특별한 주의가 필요하다. MPI와 같은 표준 통신 인터페이스를 사용하는 경우, 다른 끝점을 소유한 PE의 ID를 식별할 수 있어야 한다. 분산 그래프 알고리즘에서 이러한 간선을 따라 정보를 전달하는 것은 통신을 의미한다.^[10]

그래프 분할은 통신량 감소와 균등한 크기 분할 사이의 상충 관계를 고려하여 신중하게 수행해야 한다.^[11] 그러나 그래프 분할은 NP-hard 문제이므로, 다음과 같은 휴리스틱이 사용된다.

• 1D 분할: 각 프로세서는 $n/p$개의 정점과 해당 발신 간선을 얻는다. 이는 인접 행렬의 행별 또는 열별 분해로 이해할 수 있다. 이 경우 각 PE가 잠재적으로 다른 모든 PE로 발신 간선을 가질 수 있으므로 All-to-All 통신 단계와 $\backslash mathcal\{O\}(m)$ 메시지 버퍼 크기가 필요하다.^[12]

• 2D 분할: 각 프로세서는 인접 행렬의 부분 행렬을 얻는다. 프로세서가 직사각형 $p\; =\; p\_r\; \backslash times\; p\_c$로 정렬되어 있다고 가정하면( $p\_r$와 $p\_c$는 각각 각 행과 열의 처리 요소 수), 각 프로세서는 $(n/p\_r)\backslash times(n/p\_c)$ 차원의 인접 행렬의 부분 행렬을 얻는다. 이는 행렬의 체커보드 패턴으로 시각화할 수 있다.^[12] 각 처리 장치는 동일한 행과 열의 PE로만 발신 간선을 가질 수 있으므로, 각 PE에 대한 통신 파트너 수는 $p\_r\; +\; p\_c\; -\; 1$개로 제한된다.

6. 압축된 그래프 표현

그래프는 수조 개의 간선을 가질 수 있으며, 이는 기계 학습, 소셜 네트워크 분석 및 기타 분야에서 발생한다. 압축된 그래프 표현은 입출력 및 메모리 요구 사항을 줄이기 위해 개발되었다. 허프만 코딩과 같은 일반적인 기술을 적용할 수 있지만, 인접 리스트 또는 인접 행렬을 특정 방식으로 처리하여 효율성을 높일 수 있다.^[13]

참조

_[1] 서적 Operations on graphs
_[2] 서적
_[3] 서적
_[4] 서적 Exercise 22.1-7
_[5] 서적 Introduction to Algorithms MIT Press and McGraw-Hill
_[6] 서적 Algorithm Design and Applications Wiley
_[7] 서적 Introduction to Algorithms Massachusetts Institute of Technology
_[8] 서적 Graph Partitioning and Graph Clustering https://www.ams.org/[...] American Mathematical Society 2013-01
_[9] 간행물 Challenges in Parallel Graph Processing 2007-03
_[10] 서적 Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox https://www.springer[...] Springer International Publishing 2019
_[11] 웹사이트 Parallel Processing of Graphs https://www.grapheng[...] 2020-03-09
_[12] conference Parallel breadth-first search on distributed memory systems 2011
_[13] arXiv Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations 2019-04-27
_[14] 간행물 Graph Traversals and its Applications http://ijrar.com/upl[...] 2018-07