Related to: Data Structure
그래프
그래프(Graph)는 연결되어있는 원소간의 관계를 표현한 자료구조입니다.
· 그래프는 연결할 객체를 나타내는 정점(Vertext)과 객체를 연결하는 간선(Edge)의 집합으로 구성됩니다.
· 그래프 G를 G=(V, E)로 정의하는데, V는 정점의 집합, E는 간선들의 집합을 의미합니다.
그래프 종류
- 무방향 그래프
무방향 그래프(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)}
- 방향 그래프
방향 그래프(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>}
- 완전 그래프
완전 그래프(Complete Graph)는 한 정점에서 다른 모든 정점과 연결되어 최대 간선 수를 갖는 그래프.
· 정점이 n개인 완전 그래프에서 무방향 그래프의 최대 간선 수는 n(n-1)/2이고 방향 그래프의 최대 간선 수는 n(n-1)입니다.
- 부분 그래프
부분 그래프(Subgraph)는 기존의 그래프에서 일부 정점이나 간선을 제외하여 만든 그래프.
- 가중 그래프
가중 그래프(Weight Graph)는 정점을 연결하는 간선에 가중치(weight)를 할당한 그래프.
- 유향 비순환 그래프(DAG, Directed Acyclic Graph)
방향 그래프에서 사이클이 없는 그래프.
- 연결 그래프(Connected Graph)
떨어져 있는 정점이 없는 그래프.
연결 그래프 G9
- 단절 그래프(Disconnected Graph)
연결되지 않은 정점이 있는 그래프.
그래프 용어
그래프에서 두 정점 Vi와 Vj가 연결되어 간선 (Vi, Vj)가 있을 때, 두 정점 Vi와 Vj를 인접(adjacent)한다 하고, 간선 (Vi, Vj)는 정점 Vi와 Vj에 부속(incident)되어 있다고 말합니다.
- 차수(Dgree): 정점에 부속되어 있는 간선의 수
- 진입차수(in-degree): 정점을 머리로 하는 간선의 수
- 진출차수(out-degree): 정점을 꼬리로 하는 간선의 수
- 경로(Path): 정점 Vi에서 Vj까지 간선으로 연결된 정점을 순서대로 나열한 리스트
- 단순 경로(Simple Path): 모두 다른 정점으로 구성된 경로
- 경로 길이(Path Length): 경로를 구성하는 간선의 수
- 사이클(Cycle): 단순 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로