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

그래프란?

그래프라는 말은 많이 들어보았지만 자료구조에서 그래프란 정점과 간선으로 이루어진 자료구조를 말한다. 조금 더 구체적으로 말하면 각 정점들의 관계(연결)을 나타낸 조직도라고 이해하면 편하다. 대중교통의 노선도, 도로등 다양한 것들을 그래프로 나타낼 수 있다. 따라서 그래프를 잘 구현하고 활용할 줄 알아야 알고리즘을 해결할 수 있다.

그래프 용어

그래프를 이해하기 위해서는 용어를 알아두는 것이 편리하다.

1. 정점(Node) : vertice 라고도 하며 정점에는 데이터가 정장되어있다.
2. 간선(Edge) : link 라고도 하며 노드간의 관계를 나타낸다.
3. 인접정점(adjacent node) : 간선에 의해 연결된 정점
4. 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수

그래프 구현 방식

1.인접행렬(Adjacency)

​

​ 그래프의 노드를 2차원 배열로 만들어 나타낸 것이다. 해당 노드가 다른 노드에 연결되어있으면 1, 연결되어 있지 않으면 0으로 나타낸다. 인접행렬로 그래프를 나타내는 방식은 다음과 같은 장단점이 존재한다.

장점

1. 2차원 배열 안에 모든 노드들의 정보를 담기 때문에 배열의 위치를 확인하면 두 점에 대한 연결 정보를 조회할 수 있어 시간복잡도가 낮다(O(1))
2. 구현이 상대적으로 간편하다.

단점

1. 모든 노드에 대한 정보를 담아야하기에 O(n²)의 시간복잡도가 요소된다.
2. 무조건 2차원 배열이 필요하기에 필요이상의 공간을 차지한다.

2.인접리스트(Adjacency List)

​ 인접리스트란 그래프의 노드들을 리스트로 나타낸 것이다. 연결리스트 역시 다음과 같은 장단점을 가진다.

장점

1. 노드들의 연결 정보를 탐색할때 O(n)의 시간복잡도
2. 공간의 낭비가 적다.

단점

1. 특정 두 점이 연결되어있는지 확인하기가 까다로움
2. 구현이 어려움

그래프의 종류

1. 무방향 그래프 : 노드를 연결하는 링크에 방향이 없는 그래프
2. 방향 그래프 : 링크에 방향이 존재하는 그래프로써 해당 방향으로만 이동할 수 있다.
3. 가중치 그래프 : 노드를 이동할 때 지정한 비용이 드는 그래프
4. 완전 그래프 : 모든 노드가 서로 연결되어있는 그래프

그래프 탐색 방법

​ 그래프 탐색은 그래프의 한 정점에서 모든 정점들을 한 번씩 방문하는 것을 말한다. 이 그래프 탐색에는 DFS와 BFS 가 있는데 이는 다음번에 더 자세하게 공부하도록 하겠다.