그래프(graph): 객체 사이의 연결 관계를 표현할 수 있는 자료 구조
- 그래프 구조는 인접 행렬이나 인접 리스트로 메모리에 표현되고 처리
- 다양한 문제들을 그래프로 표현하여 컴퓨터 프로그래밍으로 해결
그래프의 정의와 용어
그래프: 정점(vertex)과 간선(edge)들의 유한 집합
- 수학적으로는 G=(V, E)와 같이 표시
- V(G)는 그래프 G의 정점들의 집합, E(G)는 그래프 G의 간선들의 집합
- 정점: 여러 가지 특성을 가질 수 있는 객체, 노드(node)
- 간선: 정점들 관의 관계, 링크(link)
무방향 그래프(undirected graph): 간선을 통해서 양방향으로 갈 수 있는 그래프
- 정점 A와 B를 연결하는 간선은 (A, B)로 표현
- (A, B)와 (B, A)는 동일한 간선
방향 그래프(directed graph): 간선에 방향성이 존재하는 그래프
- 간선을 통해 한 방향으로만 갈 수 있음
- 정점 A에서 B로 가는 간선은 <A. B>로 표시
- <A, B>와 <B, A>는 서로 다른 간선
네트워크/가중치 그래프(weighted graph): 간선에 비용이나 가중치가 할당된 그래프
부분 그래프(subgraph): 어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프
- 그래프 G의 부분 그래프 S는 V(S)⊆V(G)와 E(S)⊆E(G)를 만족
인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점
- 무방향 그래프에서 정점의 차수(degree)는 그 정점의 인접 정점 수
- 무방향 그래프에서 모든 정점의 차수를 합하면 간선 수의 2배(하나의 간선이 두 개의 정점에 인접하므로)
- 방향 그래프에서는 외부에서 오는 간선의 개수를 진입 차수(in-degree), 외부로 향하는 간선의 개수를 진출 차수(out-degree)라 함
경로
- 무방향 그래프에서 정점 s로부터 정점 e까지의 경로는 정점의 나열 s, v₁, v₂ , ... vₖ, e
- 나열된 정점들 간에는 반드시 간선 (s, v₁), (v₁, v₂), ..., (vₖ, e)가 존재해야 함
- 방향 그래프라면 <s, v₁>, <v₁, v₂>, ..., <vₖ, e>가 필요
- 경로들 중 반복되는 간선이 없을 경우, 이러한 경로를 단순 경로(simple path)라 함
- 단순 경로의 시작 정점과 종료 정점이 동일하다면 사이클(cycle)
연결 그래프(connected graph)
- 무방향 그래프 G에 있는 모든 정점 쌍에 대하여 항상 경로가 존재한다면 G가 "연결되었다"고 함
- 이때 G는 연결 그래프
- 연결 그래프가 아닌 그래프는 비연결 그래프(unconnected graph)
- 트리는 그래프의 특수한 형태로서, 사이클을 가지지 않는 연결 그래프
완전 그래프(complete graph)
- 그래프에 속해 있는 모든 정점이 서로 연결
- 무방향 완전 그래프의 정점 수를 n이라 할 때, 하나의 정점은 (n-1)개의 다른 정점으로 연결되므로 간선의 수는 n*(n-1)/2
그래프 추상 데이터 타입
