[자료구조] 그래프
1. 그래프(Graph)
그래프는 연결되어있는 원소간의 관계를 표현한 자료구조 이다.
그래프는 연결할 객체를 나타내는 Vertext 와 Edge 로 구성.
G = (V,E) 로 정의, V는 정점의 집합, E는 간선들의 집합을 의미.
2. 그래프 종류
1. Directed Graph (방향 그래프) : 간선에 화살표로 방향이 표시되어 있는 그래프
방향 그래프에서 정점 Vi 와 Vj 를 연결하는 간선을 <Vi, Vj> 로 표현하는데 Vi를 꼬리(tail), Vj를 머리(head)라고 한다. 이때, <Vi,Vj> 와 <Vj, Vi> 는 서로 다른 간선이다. V(G1) = {A,B,C,D} E(G1) = {<A,B>, <A,D>,<B,C>,<B,D>,<C,D>}
2. Undirected Graph(무방향 그래프) :두 정점을 연결하는 간선에 방향이 없는 그래프
무방향 그래프에서 정점 Vi 와 Vj 를 연결하는 간선을 (Vi, Vj) 로 표현하는데, 이때 <Vi,Vj> 와 <Vj, Vi> 는 같은 간선을 나타낸다. (방향그래프와는 반대임)
V(G1) = {A,B,C,D}, E(G1) = {(A,B), (A,D),(B,C), (B,D), (C,D)}
3. Complete Graph(완전 그래프) : 한 정점에서 다른 모든 정점과 연결되어 최대 간선 수를 갖는 그래프.
정점이 n개인 완전 그래프에서 무방향 그래프의 최대 간선 수는 n(n-1)/2 이고, 방향 그래프의 최대 간선 수는 n(n-1)이다.
4. Subgraph (부분 그래프) : 기존의 그래프에서 일부 정점이나 간선을 제외하여 만든 그래프
5. 유향 비순환 그래프(DAG, Directed Acyclic Graph) : 방향 그래프에서 사이클이 없는 그래프
6. Weight Graph(가중 그래프) : 정점을 연결하는 간선에 가중치(weight) 를 할당한 그래프
3. 그래프 용어
그래프에서 두 정점 Vi 와 Vj 가 연결되어 간선 (Vi, Vj) 가 있을 때, 두 정점 Vi와 Vj를 인접(adjacent) 한다 하고, 간선 (Vi, Vj) 는 정점 Vi와 Vj에 부속(incident) 되어 있다고 말한다.
- 차수 (Degree) : 정점에 부속되어 있는 간선의 수
- - 진입 차수(in-degree): 정점을 머리로 하는 간선의 수
- - 진출 차수(out-degree) : 정점을 꼬리로 하는 간선의 수
- 경로(Path) : 정점 Vi에서 Vj까지 간선으로 연결된 정점을 순서대로 나열한 리스트
- - 단순경로 (Simple Path) : 모두 다른 정점으로 구성된 경로
- 경로길이(Path Length) : 경로를 구성하는 간선의 수
- 사이클(Cycle) : 단순 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로
#참고