그래프는 정점(Node, Vertex)와 간선(Edge)로 이루어진 자료구조이며, 방향성이 있는 방향 그래프(Directed Graph)와 방향성이 없는 무방향 그래프(Undirected Graph)로 나뉜다. 더불어 정점과 정점을 잇는 간선에는 가중치(Weight)가 존재할 수 있다.
트리(Tree)또한 그래프의 일종이지만, 그래프는 트리와 달리 정점마다 간선이 존재하지 않을 수 있으며, 루트, 부모, 자식 노드의 개념이 존재하지 않는다.
그래프 자료구조는 컴퓨터 네트워크, 교통 시스템, 소셜 미디어와 같은 다양한 현실 세계의 문제를 모델링하는데 사용된다.
출처 - https://pangtrue.tistory.com/147
그래프 관련 용어
정점(Node, Vertext) - 데이터를 나타냄
간선(Edge) - 두 정점의 관계를 나타냄
차수(Degree) - 어떠한 정점 V에 대한 차수는 그래프 G 에서 V와 인접한 정점의 수를 의미
오일러 정리
그래프에 존재하는 모든 간선을 한 번만 통과하면서 처음 정점으로 돌아오는 경로
그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다 - 오일러 정리
그래프의 구현 방법
그래프의 구현 방법으로는 인접 행렬(Adjacency Matrix)와 인접 리스트(Adjacency List)를 사용하는 방법이 있다.
인접 행렬은 2차원 배열을 사용하여 노드 간의 연결 관계를 행렬 형태로 나타내는 방식이다. 노드 간의 연결 여부를 빠르게 확인할 수 있다는 장점이 있지만, 간선의 수와 무관하게 항상 N^2크기의 2차원 배열이 필요하므로 메모리가 낭비되며, 그래프의 모든 간선 수를 알기 위해서는 인접행렬 전체를 확인해야 하므로 O(N^2)의 시간이 소요된다.
인접리스트는 각 노드에 인접한 노드들을 연결리스트로 표현하는 방법이다. 즉 노드의 개수만큼 인접리스트가 존재하며, 각각의 인접리스트에는 각 노드에 인접한 노드 정보가 저장된다.
출처 - https://velog.io/@falling_star3
그래프 알고리즘 종류
그래프 탐색 알고리즘
그래프에서 특정 정점을 찾는 알고리즘, 이렇게 그래프 내 특정 정점을 찾기 위해서는 그래프의 각 정점을 순회하면서 방문해야 하므로, 그래프 순회 알고리즘이라 부르며 대표적으로 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)가 있다.
최단 경로 알고리즘
가중치가 있는 그래프에서 두 정점 간의 최소 가중치 합을 가지는 경로를 찾는 알고리즘
다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드 알고리즘
그 밖의 알고리즘
방향성이 있는 그래프에서 각 정점을 선후 관계에 따라 나열하는 위상 정렬 알고리즘
모든 정점을 최소한의 간선으로 연결하는 부분 그래프를 찾는 최소 신장 트리 알고리즘 (대표적으로 크루스칼, 프림)
