자료구조 - 그래프(graphe)

그래프가 무엇인지는 안다.
한 그림으로 정의하자면 이거다.

 

그러나 자료구조에서의 그래프는 애매하다.

데이터를 그래프화 시킨 것인지? 아니면 테이블 형식의 데이터를 그래프형이라고 하는건지?
문뜩 자료구조 라는 항목을 왜 만들었는지 이해가지 않는다.

쨋든 사전적인 의미는
단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조,
즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다.

위 사진처럼 각 점(N)들이 존재하며, 점들이 간선(E)으로 이어져 있다.
자료구조의 측면에서 각 노드들을 객체로 보며, 객체끼리 이어져 있는 관계, 거리 를 보는 것으로 파악된다.

트리도 그렇고 그래프도 그렇고 자료구조의 측면에서 보니 이해가 잘 안된다만,
듣기로는 상당히 많이 쓰인다고 한다.
그래프와 트리의 특징들을 아래 표로 정리해 보았다.

그래프와 트리의 차이점.

그렇다면 굳이 그래프를 데이터 출력을 위해서가 아닌, 자료구조로써 알아야 할 이유가 있을까??

자료구조로써의 그래프란, 네트워크 모델로써 맨 위의 사진과는 다르게 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 것으로 봐야한다.
이를 이용하면 지도에서 길찾기나 간접 경로찾기 등을 쉽게 구현할 수 있다.

• 포털 사이트의 검색 엔진, SNS에서 사람들과의 관계, 네비게이션 (길찾기) 등은 자료구조의 그래프를 사용한다.
• 세 가지 모두 수많은 정점을 가지고 있고, 서로 관계가 있는 정점은 간선으로 이어져 있다.
• 세 가지 중에서 네비게이션 시스템이 어떤 방식으로 자료구조 그래프를 사용하는지 살펴보자.

이런 이점이 있기에 자료구조 로써의 그래프를 배워두면 좋을 것이다.

그래프(graph)의 종류

- 무방향 그래프 (간선을 통해서 양 방향으로 갈 수 있는 그래프, 양쪽 노드로 갈 수 있다.)

- 방향 그래프 (간선에 방향이 존재하는 그래프, 한쪽 방향으로만 갈 수 있다.)

- 연결 그래프 (무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우)

- 비연결 그래프 (무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우)

- 싸이클 (단순 경로의 시작 정점과 종료 정점이 동일할 경우)
 % 단순 경로(Simple Path): 경로 중에서 반복되는 정점이 없는 경우

- 비순환 그래프(Acyclic Graph) (싸이클이 없는 그래프)

- 완전 그래프 ( 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프)

그래프(Graph)의 구현 2가지

1. 인접 행렬(Adjacency Materix)

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

인접행렬 장점

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

인접행렬 단점

1. 모든 정점에 대해 간선 정보를 대입해야 하므로 O(n²) 의 시간복잡도가 소요된다.
2. 무조건 2차원 배열이 필요하기에 필요 이상의 공간이 낭비된다.

2. 인접 리스트(Adjacency List)  

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

인접리스트 장점

1. 정점들의 연결 정보를 탐색할 때 O(n) 의 시간이면 가능합니다. (n: 간선의 갯수)
2. 필요한 만큼의 공간만 사용하기때문에 공간의 낭비가 적다.

인접리스트 단점

1. 특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래 걸린다. (배열보다 search 속도느림)
2. 구현이 비교적 어렵다.