그래프(Graph)

  그래프 

그래프는 연결되어 있는 원소 간의 관계를 표현하는 자료구조이다.

 

그래프의 구성요소

• 노드(또는 정점) 데이터 저장 및 표현
• 간선 데이터 간의 관계 표현

그래프의 종류

그래프는 방향성과 연결 정도에 따라 구분하며 추가로 간선에 가중치를 할당한 그래프가 존재한다.

• 무방향 그래프(Undirected Graph) 두 노드를 연결하는 간선의 방향이 없는 그래프
• 방향 그래프(Directed Graph) 노드를 연결할 때 간선에 방향이 있는 그래프
• 완전 그래프(Complete Graph) 정점이 모두 서로 연결된 그래프
• 부분 그래프(Subgraph) 완전 그래프에서 특정 간선이 제외된 그래프
• 가중 그래프(Weigh Graph) 간선마다 가중치가 할당된 그래프

 

그래프의 표현)

그래프는 방향성에 따라 다르게 표현된다. 가령 정점 A, B가 존재하는 완전 그래프 G에 대해 다음과 같이 표현한다.

• 무방향 그래프 V(G) = { A, B }  E(G) = { (A, B) }
• 방향 그래프 V(G) = { A, B }  E(G) = { <A, B>, <B, A> }

 

예를 들어 아래 그래프에 대해 무방향 그래프와 방향 그래프의 표현은 다음과 같다.

• V(무방향 그래프) = { A, B, C, D }  E(무방향 그래프) = { (A, B), (A, D), (B, C), (B, D), (C, D) }
• V(방향 그래프) = { A, B, C, D }  E(방향 그래프) = { <A, B>, <A, D>, <B, C>, <B, D>, <C, A>, <C, D>, <D, A> }

 

그래프 관련 용어)

• 연결 그래프(Connected Graph) 서로 떨어진 노드가 없는 그래프
• 단절 그래프(Disconnected Graph) 연결 되지 않은 노드가 있는 그래프

• 차수(Degree) 노드에 부속된 간선의 수
• 경로(Path) 특정 노드에서 다른 노드로 갈 수 있는 길을 나열한 것
• 경로 길이(Path Length) 경로를 구성하는 간선의 수
• 단순 경로(Simple Path) 경로가 모두 다른 노드로 구성되는 가장 단순한 경로
• 사이클(Cycle) 단순 경로 중 시작 점과 끝 점이 같은 경로

 

참고문헌

이지영.(2013.07.30).C로 배우는 쉬운 자료구조