그래프(Graph)

그래프(graph)는 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조다.

1. 그래프의 표현

정점(Vertex)와 간선(Edge)들의 집합으로 구성된다.

G=(V,E)

정점은 여러 가지 특성을 가질 수 있는 객체를 의미하고, 간선은 이러한 정점들 간의 관계를 의미한다.

 

간선의 종류에 따라  무방향 그래프(Undirected graph)와 방향 그래프(Directed graph)로 구분된다.

• 무방향 그래프: 간선을 통해서 양 방향으로 갈수 잇음을 나타내며 정점 A와 정점 B를 연결하는 간선은 (A,B)와 같이 정점의 쌍으로 표현한다. 즉 (A,B)와 (B,A)는 동일한 간선이다.
• 방향 그래프: 간선에 방향성이 존재하는 그래프로서 도로의 일방 통행길과 마찬가지로 간선을 통하여 한쪽 방향으로만 갈 수 있음을 나타낸다. 정점 A에서 정점 B로만 갈 수 있는 간선은 <A,B>로 표시한다. 방향 그래프에서 <A,B>와<B,A>는 서로 다른 간선이다.