[알고리즘] 그래프 이론

 

 

그래프 이론

---

코딩테스트에서 그래프이론을 활용하는 문제들은 대부분 난이도가 좀 있는 편이라고 생각한다. 지금까지 공부한 내용 중에서 DFS, BFS, 최단경로 알고리즘 모두 그래프를 이용하는 개념들이다. 

알고리즘 문제에서 서로 다른 객체가 연결되어있다라는 내용이 내포되어있으면 가장 먼저 그래프 알고리즘 적용 여부를 판단해보아야 한다.

 

 

그래프

그래프는 정점과 간선으로 이루어진 자료구조 형태이다. 트리 또한 그래프의 일종이지만 트리는 방향성이 존재하고, 수직적인 관계를 가지고 있지만 그래프는 수직개념, 루트노드 등과 같은 개념이 없다. 즉 그래프는 네트워크 모델에 대한 관계를 나타낼때 효율적으로 사용될 수 있다. 대표적으로 지하철 노선도를 생각할 수 있다. 

정점 - vertice : 노드라고 불리며 데이터가 저장되는 부분

간선 - edge : 링크라고 불리기도 하며 노드간의 관계를 나타냄

인접 정점 - adjacent vertex : 간선에 의해 연결된 정점

단순 경로 - simple path : 경로 중 반복되는 정점이 없는 것

차수 - degree : 무방향 그래프에서 하나의 정점에 인접한 정점의 수

진출 차수 - out degree : 방향그래프에 적용되고 한 노드에서 외부로 향하는 간선의 수를 나타냄

진입 차수 - in degree : 방향그래프에 적용되고 외부 노드에서 들어오는 간선의 수를 나타냄

 

그래프는 구현되어진 형태에 따라 여러 종류로 나누어진다. 

 - 무방향 그래프

 - 방향 그래프 

 - 가중치 그래프

 - 완전 그래프

 

그래프 기반 알고리즘들은 아래와 같다.

 - DFS

 - BFS

 - 최단경로 알고리즘

 - 크루스칼 알고리즘 (그리디 알고리즘)

 - 위상정렬 알고리즘 (큐 자료구조)