프로그래밍 기초/자료구조
그래프(Graph)
niamdank
2021. 4. 8. 11:15
그래프
그래프는 연결되어 있는 원소 간의 관계를 표현하는 자료구조이다.
그래프의 구성요소
- 노드(또는 정점) 데이터 저장 및 표현
- 간선 데이터 간의 관계 표현
그래프의 종류
그래프는 방향성과 연결 정도에 따라 구분하며 추가로 간선에 가중치를 할당한 그래프가 존재한다.
- 무방향 그래프(Undirected Graph) 두 노드를 연결하는 간선의 방향이 없는 그래프
- 방향 그래프(Directed Graph) 노드를 연결할 때 간선에 방향이 있는 그래프
- 완전 그래프(Complete Graph) 정점이 모두 서로 연결된 그래프
- 부분 그래프(Subgraph) 완전 그래프에서 특정 간선이 제외된 그래프
- 가중 그래프(Weigh Graph) 간선마다 가중치가 할당된 그래프
그래프의 표현)
그래프는 방향성에 따라 다르게 표현된다. 가령 정점 A, B가 존재하는 완전 그래프 G에 대해 다음과 같이 표현한다.
- 무방향 그래프 V(G) = { A, B } E(G) = { (A, B) }
- 방향 그래프 V(G) = { A, B } E(G) = { <A, B>, <B, A> }
예를 들어 아래 그래프에 대해 무방향 그래프와 방향 그래프의 표현은 다음과 같다.
- V(무방향 그래프) = { A, B, C, D } E(무방향 그래프) = { (A, B), (A, D), (B, C), (B, D), (C, D) }
- V(방향 그래프) = { A, B, C, D } E(방향 그래프) = { <A, B>, <A, D>, <B, C>, <B, D>, <C, A>, <C, D>, <D, A> }
그래프 관련 용어)
- 연결 그래프(Connected Graph) 서로 떨어진 노드가 없는 그래프
- 단절 그래프(Disconnected Graph) 연결 되지 않은 노드가 있는 그래프
- 차수(Degree) 노드에 부속된 간선의 수
- 경로(Path) 특정 노드에서 다른 노드로 갈 수 있는 길을 나열한 것
- 경로 길이(Path Length) 경로를 구성하는 간선의 수
- 단순 경로(Simple Path) 경로가 모두 다른 노드로 구성되는 가장 단순한 경로
- 사이클(Cycle) 단순 경로 중 시작 점과 끝 점이 같은 경로