[자료구조] 그래프 (Graph) 란?

그래프 란?

노드(node, vertex : 정점, 꼭지점) 집합 V 와 엣지(edge : 간선, 변) 집합 E로 구성된 자료구조의 일종입니다.

일반적으로 노드엔 데이터, 엣지엔 노드와 노드 사이의 관계 정보가 포함되어 있습니다.

그래프 노드 와 간선 관계도

 

그래프의 종류

무방향 그래프 (Undirected Graph)

두 정점을 연결하는 간선에 방향이 없는 그래프이다.

무방향 그래프 (Undirected Graph)

 

무방향 그래프에서 정점 V1 와 V2 를 연결하는 간선을 (V1, V2) 로 표현하는데,

이때 (V1, V2) 와 (V2, V1) 는 같은 간선을 나타냅니다.

• V(G1) = {A, B, C, D}
• E(G1) = {(A,B), (A,D), (B, C), (B, D), (C, D)}

 

방향 그래프 (Directed Graph)

간선에 방향이 있는 그래프 이다.

방향 그래프 (Directed Graph)

 

정점 V1 와 V2를 연결하는 간선을 <V1, V2> 로 표현하는데, V1 (꼬리 : tail), V2 (머리 : head) 라고 합니다.

이때 <V1, V2> 와 <V2, V1> 는 서로 다른 간선입니다.

• V(G1) = {A, B, C, D}
• E(G1) = {<A, B>, <A, D>, <B, C>, <B, D>, <C, D>}

 

완전 그래프 (Complete Graph)

정점에서 다른 모든 정점과 연결되어 최대 간선 수를 갖는 그래프이다.

 

완전 그래프 (Complete Graph)

 

정점이 n개인 완전 그래프에서 무방향 그래프의 최대 간선 수는 n^(n-1)/2 이고,

방향 그래프의 최대 간선수는  n^(n-1) 입니다.

 

부분 그래프 (Subgraph)

기존의 그래프에서 일부 정점이나 간선을 제외하여 만든 그래프이다.

 

그래프 와 부분 그래프 (Subgraph)

 

 

가중 그래프 (Weight Graph)

정점을 연결하는 간선에 가중치를 할당한 그래프이다.

 

가중 그래프 (Weight Graph)

 

유향 비순환 그래프 (DAG, Directed Acyclic Graph)

방향 그래프에서 사이클이 없는 그래프이다.

 

유향 비순환 그래프 (DAG, Directed Acyclic Graph)

 

연결 그래프 (Connected Graph)

단절된 정점이 없는 그래프이다.

 

연결 그래프 (Connected Graph)

 

단절 그래프 (Disconnected Graph)

단절된 정점이 있는 그래프이다.

 

단절 그래프 (Disconnected Graph)