그래프 ( Graph )

그래프 ( Graph ) 

그래프란 정점 ( Vertex ) 과 간선 ( Edge ) 으로 이루어진 자료구조 이다.

정확히는 정점 ( Vertex ) 간의 관계를 표현하는 조직도라고 볼 수 있다.

이러한 면에서 트리는 그래프의 일종인 셈이다.

---

그래프와 트리의 차이점

---

그래프와 관련된 용어

• 정점 ( Vertex ) : 노드 ( Node ) 라고도 하며 정점에는 데이터가 저장된다.
• 간선 ( Edge ) : 정점 ( 노드 ) 를 연결하는 선으로 link, brach 라고도 부른다.
• 인접 정점 ( adjacent Vertex ) : 간선에 의해 직접 연결된 정점 ( 0과 2는 인접정점 )
• 단순 경로 ( simple path ) : 경로 중에서 반복되는 정점이 없는 경우, 한붓그리기와 같이 같은 간선을 지나가지 않는 경로 ( 0 > 3 > 2 > 1 는 단순경로 ) 
• 차수 ( degree ) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 ( 0 의 차수는 3 )
• 진출 차수 ( in-degree ) : 방향 그래프에서 외부로 향하는 간선의 수
• 진입 차수 ( out-degree ) : 방향 그래프에서 외부에서 향하는 간선의 수
• 경로 길이 ( path length ) : 경로를 구성하는데 사용된 간선의 수
• 사이클 ( cycle ) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우

[자료구조] 그래프 (Graph) - 인접행렬 vs 인접리스트, DFS, BFS, Connected Component, Spanning Tree

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

---

그래프의 종류

1. 무방향 그래프 : ( 간선의 ) 방향이 없는 그래프
2. 방향 그래프 : 방향성이 있는 그래프
3. 가중치 그래프 : 간선의 가중치값이 존재하는 그래프
4. 루트없는 그래프 : 간선을 통해 정점 간 잇는 방법이 한가지인 그래프 
5. 이분 그래프 : 그래프의 정점을 겹치지 않게 두 그룹을로 나눈 후 다른 그룹끼리만 간선이 존재하게 분할하 수 있는 그래프
6. 사이클이 없는 방향 그래프 : 정점에서 출발해 자기 자신으로 돌아오는 경로 ( 사이클 ) 가 없는 그래프

[자료구조 1] 그래프(Graph) 이해하기

---

 

그래프 구현 방법

그래프를 구현하는 방법에는 인접행렬, 인접리스트 방식이 있다. 두개의 구현 방식은 각각의 상반된 장단점을 가지고 있는데 대부분 인접리스트 형식을 많이 사용한다.

---

인접행렬 방식

인접행렬은 그래프 노드를 2차원 배열로 만든 것이다. 완성된 배열의 모양은 1,2,3,4,5,6 의 정점을 연결하는 노드에 다른 노드들이 인접 정점이라면 1, 아니면 0을 넣어준다.

 

인접행렬의 장점

1. 2차원 배열 안에 모든 정점들의 간선 정보를 담기 때문에 배열의 위치를 확인하면 두 점에 대한 연결 정보를 조회할 때 O(1) 의 시간 복잡도면 가능하다

2. 구현이 비교적 간편하다

 

인접행렬의 단점

1. 모든 정점에 대해 간선 정보를 대입해야 하므로 O(n²)의 시간복잡도가 소요된다

2. 무조건 2차원 배열이 필요하기에 필요 이상의 공간이 낭비된다

---

인접리스트 방식

인접리스트란 그래프의 노드들을 리스트로 표현한 것이다. 주로 정점의 리스트 배열을 만들어 관계를 설정해줌으로써 구현한다.

 

인접리스트의 장점

1. 정점들의 연결 정보를 탐색하 때 O(n) 의 시간이면 가능하다.

2. 필요한 만큼의 공간만 사용하기때문에 공간의 낭비가 적다.

 

인접리스트의 단점

1. 특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래 걸린다.2. 구현이 비교적 어렵다.

---

 

[JAVA] 그래프 구현하기 (인접 행렬, 인접 리스트)