[자료구조] 그래프

그래프(Graph) : 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조

ex) 지하철 노선도, 지도, tree(선형자료구조들이나 트리를 그래프의 한 종류로 볼 수 있다.)

 

그래프 구성

그래프는 G(V,E)로 표시

- 정점(vertices) 또는 노드(node) 

• 여러가지 특성을 가질 수 있는 객체 의미
• V(G) : 그래프 G의 정점들의 집합

- 간선(edge) 또는 링크(link)

• 정점들 간의 관계 의미
• E(G) : 그래프 G간의 간선들의 집합

그래프의 정점과 간선

 

그래프의 종류

- 무방향 그래프

• 간선을 통해서 양방향으로 갈 수 있음
• (A,B)로 표현
• (A,B)=(B,A)

- 방향 그래프

• 간선을 통해서 한쪽 방향으로만 갈 수 있음
• 일방통행 길
• <A,B>로 표현
• <A,B> ≠ <B,A>

- 가중치 그래프

• 네트워크(network)라고도 함
• 간선에 비용(cost)이나 가중치(weight)가 할당된 그래프

- 부분 그래프

• 정점 집합 V(G)와 간선 집합E(G)의 부분집합으로 이루어진 그래프

 

그래프의 용어

G1

-인접 정점 : 간선에 의해 직접 연결된 정점

 

-정점의 차수(degree) : 그 정점에 연결된 간선의 수를 말한다. 무방향 그래프에서는 정점에 인접한 정점의 수를 말하는데, G1의 정점 0은 차수가 3이다.

 

-경로(path) : 간선을 따라 갈 수 있는 길을 말하며, 정점의 나열로 표시된다. 그래프 G1에서 0,1,2,3은 경로지만 0,1,3,2는 경로가 아니다(나열된 정점들 간에는 반드시 간선이 존재해야 한다.)

 

-경로의 길이 : 경로를 구성하는데 사용된 간선의 수

 

-단순 경로와 사이클 : 경로 중에서 반복되는 간선이 없는 경로를 단순 경로라 한다. 그리고 단순 경로의 시작 정점과 종료 정점이 같다면 이러한 경로를 사이클이라고 한다.

단순 경로와 사이클

 

-연결 그래프 : 그래프 G의 모든 정점들 사이에 경로가 존재하면 G를 연결 그래프라 부른다. 이 그래프에서는 떨어진 정점이 없다. 그렇지 않은 그래프는 비연결 그래프라고 한다.

 

-트리(Tree) : 그래프의 특수한 형태로서 사이클을 가지지 않는 연결그래프를 트리라 한다.

 

-완전 그래프 : 모든 정점 간에 간선이 존재하는 그래프를 완전 그래프라고 한다. 

완전 그래프의 예