자료구조 - [ 그래프 ]

그래프

정점(Vertext)과 정점을 연결하는 간선(Edge)의 집합으로 구성된 자료구조를 그래프라 부르며 G=(V,E)로 표기한다.

V는 정점의 집합이며, E는 간선의 집합이다. 그리고 정점 u는 정점의 집합 V에 속해있으며, 간선(u,v)는 간선의 집합 E에 속해있다.

 

 

---

완전 그래프

모든 정점끼리 간선으로 연결되어 있는 것을 완전 그래프라고 한다.

 

 

---

무방향 그래프 / 방향 그래프

무방향 그래프는 방향이 없는 간선을 가지고 양방향으로 진행할 수 있으며, 간선은 (u1, v2), (u2, v2)로 표현할 수 있다.

방향 그래프는 방향이 있는 간선을 가지며 각 간선은 한 방향으로만 진행할 수 있다. 간선은 <u1, v2>, <u2, v2>로 표현한다.

 

 

---

차수(Degree)

정점에 접한 간선의 수를 차수라고 한다.

 

무방향 그래프에서는 특정 점점을 기준으로 연결된 간선의 개수가 차수이다.

방향 그래프에서는 아래와 같이 나뉜다.

• In-degree : 특정 정점을 기준으로 안으로 들어오는 방향의 간선의 개수
• Out-degree : 특정 정점을 기준으로 밖으로 나가는 방향의 간선의 개수
• 차수 : In-degree + out-degree

 

 

---

경로

정점 u로 부터 정점 v까지의 정점의 순서열을 경로라고 한다.

한 경로상에 있는 모든 정점들이 서로 다른 경우 단순 경로(Simple Path)라고 한다. 다만 처음과 마지막 정점은 동일할 수 있다.

예시로 2, 0, 1, 2는 단순 경로이나 2, 0, 1, 2, 3은 단순 경로가 아니다.

 

 

---

순환

출발지와 도착지가 같은 단순 경로를 순환이라고 한다.

 

 

 

 

---

가중치가 있는 그래프

간선에 가중치가 존재한다면 특정 경로의 간선의 길이는 가중치의 합이 된다.

 

 

---

그래프와 트리 정리

	그래프	트리
정의	정점과 간선으로 구성	연결된 무방향 비순환 그래프
모델	네트워크	계층
정점/노드	루트 노드가 존재하지 않음 부모 자식간의 관계가 존재하지 않음	루트 노드가 존재 부모 자식간의 관계 형성
간선	간선이 존재할 수도, 존재하지 않을 수도 있음	N개의 노드가 있으면 항상 N-1개의 간선이 존재
방향	방향 그래프, 무방향 그래프	무방향 그래프

 

---

참조

https://www.codelatte.io/courses/java_data_structure

자바 자료구조 강의 - 코드라떼