[자료구조] 그래프란? (feat. Java)

그래프란?

그래프는 정점(노드)의 집합과  정점(노드)를 이어주는 간선의 집합으로 이루어진 자료구조이다.

 

 

그래프의 종류

 

1. 방향 그래프 / 무방향 그래프

2. 가중치 그래프

3. 비연결 그래프 / 연결 그래프

4. 사이클 / 비순환 그래프

5. 완전 그래프

 

이렇게 나뉜다.

 

그럼 이제 각각의 그래프에 대해서 알아보자.

 

 

1. 방향 그래프 / 무방향 그래프

왼 : 무방향 그래스 오 : 방향 그래프

방향 그래프는 간선에 방향성이 존재하는 그래프로 

A -> B라면 A에서 B로만 갈수 있는 그래프이다.

따라서  (A,B)와 (B,A)는 서로 다르다.

 

하지만 무방향 그래프는 하나의 간선을 통해서 양방향으로 갈수 있다.

따라서 A - B 라는 간선이 존재한다면 (A - B) 와 (B - A)는 서로 같다.

 

 

 

 

 

2. 가중치 그래프

가중치 그래프는 간선에 값이 주어진 그래프이다.

 

 

3. 비연결 그래프 / 연결 그래프

연결 그래프는 무방향 그래프에 서 모든 노드가 서로 연결되어 있는걸 뜻한다.

하지만 비연결 그래프는 노드들 간에 단절이 발생된경우를 비연결 그래프라고 한다.

 

 

 

 

4. 사이클 / 비순환 그래프

왼 : 사이클 그래프 오 : 비순환 그래프

 

사이클 그래프는 위 사진처럼 그래프에 사이클이 존재한다면 사이클 그래프이고

위사진에서 오른쪽 그래프 처럼 사이클이 존재하지 않다면 비순환 그래프이다.

 

 

 

 

5. 완전 그래프

완전 그래프는 한 노드에서 다른 모든 노드들과 연결되어 있어 최대의 간선수를 가진 그래프이다.

노드가 n개 라면 무방향 그래프의 최대 간선수는 n(n-1)/2개 이며 방향 그래프의 경우에는 

두 노드에 대하여 서로 양방향으로 가야하기때문에 위의 무방향 그래프의 2배인

n(n-1)개이다.

 

 

완전 그래프에서의 간선수 

무방향 : n(n-1)/2

방향 : n(n-1)

 

 

 

그래프의 구현 방법

 

그래프를 구현하는 방법에는 두가지 방법이 있다.

 

1. 인접리스트를 활용한 구현

https://wpioneer.tistory.com/128?category=1023663 

[자료구조] 인접리스트 구현 : LinkedList (Java)

2. 인접 행렬을 활용한 방법

https://wpioneer.tistory.com/129

[자료구조] 인접행렬로 구현한 그래프 (Java)

 

각각의 방법에 관한건 아래에 명시된 링크를 통해서 확인해보면 된다.

 

 

그래프의 탐색 방법

 

그래프의 탐색 방법에도 두가지 방법이 있다.

각각의 방법에 관한것도 아래에 명시된 링크를 통해서 확인해보면 된다.

 

1. 깊이 우선 탐색

https://wpioneer.tistory.com/130

[자료구조] DFS(Depth First Search) Java 구현

2. 너비우선 탐색

https://wpioneer.tistory.com/131

[자료구조] BFS(Breadth First Search) Java 구현