그래프(Graph)

- 그래프 (Graph)

정점의 집합과 간선의 집합으로 구성된 비선형 데이터 구조

 - 정점 : 자료를 저장하려는 자료의 단위 (= 노드)

 - 간선 : 정점 사이를 연결하는 선으로 두 정점 쌍(n1, n2)으로 표현

 

- 방향성(유향) 간선 (Directed edge) : 뱡향을 가진 정점의 쌍(u, v)으로 화살표로 표현하고 단방향을 가리킴

u는 출발점 v는 도착점을 의미. 방향성 간선을 가진 그래프를 방향성 그래프(Directed Graph)라고 함.

 

- 무방향성(무향) 간선 (Undirected edge) : 방향이 없는 정점의 (u, v)으로 직선을 표현하며 양방향을 가리킴

간선 (u, v)와 (v, u)는 같다. 무방향성 간선을 가진 그래프를 무방향성 그래프(Undirected Graph)라고 함.

 

- 그래프 유형

 

  - 무방향성 그래프(Undirected Graph) : 무방향성 간선을 가진 그래프, 모든 간선이 양방향

  - 방향성 그래프(Directed Graph) : 방향성 간선을 가진 그래프, 모든 간선이 단방향

  - 가중치 그래프(Weighted Graph) : 각 간선에 가중치 또는 비용이 할당된 그래프

 

 

  - 단순 그래프(SImple Graph) : 중복된 간선과 loop가 없는 그래프, 정점의 개수가 n일 때 최대 n - 1개의 간선을 가짐

 

 

  - 완전 그래프(Complete Graph) : 간선의 수가 최대인 그래프, 정점의 개수가 n일 때 n*(n-1) / 2개의 간선을 가짐

 

 

  - 연결 그래프(Connected Graph) : 모든 정점이 연결되어 있음 (G1)

  - 비연결 그래프(Disconnected Graph) : 연결 그래프의 반대 (G2)

 

 

  - 순환 그래프(Cyclic Graph) : 순환을 가지고 있음

  - 비순환 그래프(Acyclic Graph) : 순환을 가지고 있지 않음

 

  - 희소 그래프(Sparse Graph) : 노드 수보다 간선 수가 적은 그래프

  - 밀집 그래프(Dense Graph) : 노드 수보다 간선 수가 더 많은 그래프 

 

 

  - 트리(Tree) : 연결된 비순환 무방향성 그래프

    간선의 수 = 정점의 수 - 1

    두 정점은 단일 단순 경로로 연결됨

    트리에 간선을 하나 추가하면 순환을 가짐

    트리에 어떤 간선을 제거하면 더 이상 연결되지 않음

 

 - 포레스트(Forest) : 서로 중복되지 않는 트리들의 집합 (트리를 분리한 집합)