[비선형구조] 그래프(Graph)

 

Graph

 

그래프(Graph)

 

비선형구조에서 대표적인 그래프부터 알아보자.

 

Graph는 크게 점과 점들을 이어주는 선으로 나뉘는데,

 

점을 정점, Node 혹은 Vertex 라고 부르고,

선을 간선, Edge 혹은 Link라고 부른다.

 

그리고 차수 Degree란, 

정점과 이어진 간선의 개수를 말한다.

 

그래프는 크게 무방향 그래프와 방향 그래프로 나뉜다.

 

방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)

 

 

 

방향 그래프는 간선의 방향이 존재하며,

무방향 그래프는 간선의 방향이 존재하지 않는다.

 

즉, 무방향 그래프는 어느 방향이든 이동할 수 있지만,

방향 그래프는 간선의 방향으로만 이동할 수 있다.

 

무방향 그래프 용어

 

인접하다: 간선 하나를 두고 정점 A에서 정점 B로 이동할 수 있는 경우.

 

방향 그래프 용어

 

Indegree: 양방향 간선에서, 들어오는 간선의 수.

 

Outdegree: 양방향 간선에서, 나가는 간선의 수.

 

싸이클: 한 정점에서 출발하여 간선을 따라서, 시작한 정점으로 다시 돌아오는 경로.

 

가중치 그래프(Weighted Graph)

 

 

간선들에 가중치가 있는 형태.

 

멀티 그래프(Multi Graph)

 

 

멀티 그래프는 똑같은 정점 쌍 사이에 여러 개의 간선이 존재하는 형태.

 

중복되는 간선은 빨간색으로 표시하고, 

자신으로 돌아오는 간선은 파란색으로 표시한다.