그래프(Graph)

그래프(Graph)

정점(Vertex)과 간선(Edge)의 집합이다.

• 방향성(Directed) 그래프: 간선에 방향성이 포함된 그래프이다.
• 무방향성(Undirected) 그래프: 방향성이 없는 그래프이다.
• 가중치(Weight) 그래프: 간선에 가중치 정보가 포함된 그래프이다.
• 부분(Sub) 그래프: 그래프의 일부 정점 및 간선으로 이루어진 그래프이다.

 

1. 구현 방법

1) 인접 행렬

정점(V)의 수만큼 2차원 배열을 만들고 인접하면 1, 인접하지 않으면 0을 넣는 방법으로 메모리 낭비(V^2)가 있으나 밀도가 높은 그래프 표현에 적합하다.

 

방향 그래프

무방향 그래프

 

2) 인접 리스트

각 정점마다 리스트를 만들고 인접해 있는 정점들을 연결한 방법으로 검색 시간이 오래 걸리지만 메모리 낭비가 없다.

 

방향 그래프

무방향 그래프

 

2. 그래프 탐색

1) 깊이 우선 탐색(DFS)

• 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 나아가고 더 이상 연결된 정점이 없다면 이전 단계 정점으로 돌아가 연결할 수 있는 정점이 있는지 탐색한다.
• 스택을 사용해 구현한다.

 

2) 너비 우선 탐색(BFS)

• 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다.
• 큐를 사용해 구현하고 최단 경로에 사용한다.

 

3. 최소 신장 트리(Minimum Spanning Tree)

사이클 없이 모든 정점이 연결된 트리(신장 트리) 중 간선의 가중치의 합이 가장 작은 트리이다.

• 크루스칼 알고리즘(Kruskal Algorithm): 사이클을 만들지 않는 범위에서 가중치가 가장 작은 간선을 하나씩 더한다.
• 프림 알고리즘(Prim Algorithm): 한 개의 정점으로 이루어진 초기 그래프 A를 구성한 후 그래프 A와 외부의 정점을 연결하는 간선들 중 가중치가 가장 작은 간선을 찾아 그 정점을 A에 포함한다. 위 과정을 반복하고 모든 정점들이 연결되면 종료한다.

 

4. 위상 정렬

그래프에 선, 후 순서가 있을 경우 순서를 유지하고 그래프의 노드를 방문하는 정렬이다.

 

5. 최단 경로

두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로이다.

• 다익스트라 알고리즘: 음의 가중치를 허용하지 않으며 프림 알고리즘과 비슷하다.
• 벨만 포드 알고리즘: 음의 가중치는 허용하지만 음의 사이클은 허용하지 않는다.