Data Structure - Graph Structure

왜 그래프 구조인가 - 가장 보편적인 구조

atomic -> 선형구조 -> 부분 순서 구조 -> 자유 구조 -> 해슁 구조

 

그래프의 형식적 정의 G(V,E)

- vertex / edge / {vertex, edge} induced subgraph / simple graph와 general graph / connectedness, connected component / path와 trail, cycle

 

Graph는 vertex와 edge로 이루어진 한정된 자료구조를 의미함. / vertex는 정점, edge는 정점과 정점을 연결하는 간선. /  연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조( ex: 지도, 지하철 노선도의 최단 경로, 전기회로의 소자들, 도로 등) / 그래프는 여러개의 고립된 부분 그래프(Isolated subgraphs)로 구성될 수 있음.

 

그래프와 트리의 차이

정의

- 그래프 : node와 그 node를 연결하는 edge를 하나로 모아놓은 자료구조 

- 트리 : 그래프의 한 종류, Directed Acyclic Graph(방향성이 있는 비순환 그래프)의 한 종류

방향성

- 그래프 : 방향(Directed) 그래프, 무방향(Undirected) 그래프 모두 존재

- 트리 : 방향(Directed) 그래프

사이클

- 그래프 : 사이클(cycle) 가능, 자체 간선(self-loop)도 가능, 순환 그래프(Cyclic), 비순환 그래프(Acyclic) 모두 존재

- 트리 : 사이클(cycle) 불가능, 자체 간선(self-loop)도 불가능, 비순환 그래프(Acyclic)

루트 노드

- 그래프 : root node의 개념이 없음

- 트리 : 한 개의 root node만이 존재, 모든 자식 노드는 한개의 부모 노드만을 가짐

부모-자식

- 그래프 : parent-child의 개념이 없음

- 트리 : parent-child 관계, top-bottom이나 bottom-top으로 이루어짐

모델

- 그래프 : Network model

- 트리 : Hierarchy model

순회

- 그래프 : DFS, BFS

- 트리 : DFS, BFS만의 Pre-, In-, Post-order

Edge의 수

- 그래프 : 그래프에 따라 edge의 수가 다름. edge가 없을 수도 있음

- 트리 : node가 n인 트리는 항상 n-1의 edge를 가짐

경로

- 그래프 : x

- 트리 : 임의의 두 node간의 경로는 유일

예시 및 종류

- 그래프 : 지도, 지하철 노선도의 최단 경로, 전기회로의 소자들, 도로 등

- 트리 : binary tree, binary search tree, balanced tree(AVL tree, red-black tree), binary heap(최대힙, 최소힙) 등

 

컴퓨터 시스템에 그래프를 저장하는 방법들 ) 리스트와 행렬 구조 중의 하나로 구별 가능. 하지만 실제 사용에 있어서 최적의 자료 구조는 이 두 구조의 조합된 형태를 띔. 리스트 구조는 종종 sparse graphs(밀집 그래프)에 적합하며 적은 메모리 공간을 요구함. 행렬 구조는 많은 양의 메모리를 필요로하지만 더욱 빠른 접근을 제공함.

 

리스트 자료구조

ㆍIncidence list(발생 리스트) : edge들은 edge로 연결된 두 vertex(방향이 있다면 순서 존재함)와 weight(가중치), 다른 특정 데이터들을 포함하는 배열로 표현됨. edge로 연결된 두 vertex는 서로 adjacent한 관계.

ㆍAdjacency list(인접 리스트) : Incidence list와 비슷하게, 각 vertex가 인접한 vertex들의 리스트를 가짐. -> 방향성을 가지지 않은 그래프에서는 불필요한 정보가 생기게 됨. 만약 a와 b가 인접하다면 a의 인접 리스트는 b를 포함하고 동시에 b도 a를 포함. 추가적인 저장 공간에 대한 비용이 있다면 인접 정보를 얻는 것은 빨라짐.

 

행렬 자료구조

ㆍIncidence matrix(발생 행렬) : 그래프는 edge를 열로 하고 vertex는 행으로하는 행렬로 표현되며, 행렬은 edge의 끝점에 대한 데이터를 가짐. 행렬의 크기는 V*E(vertex의 수 * edge의 수)

ㆍAdjacency matrix(인접 행렬) : 인접 행렬의 크기는 V*V(vertex의 수)로 나타냄. vertex x에서 vertex y로 edge가 존재하면 행렬 성분 x행y열의 값은 1이고 그렇지 않으면 0. 이것은 subgraph(부분그래프), reverse(역그래프)를 쉽게 찾게 해줌.