[파이썬] 그래프의 종류와 특성

04 Sep 2023

그래프는 컴퓨터 과학에서 매우 중요한 자료 구조이다. 그래프는 정점(vertex)과 간선(edge)으로 구성되며, 다양한 문제를 해결하는데 사용된다. 이번 글에서는 그래프의 종류와 각각의 특성에 대해 알아보도록 하겠다.

1. 무방향 그래프 (Undirected Graph)

무방향 그래프는 간선에 방향이 없는 그래프이다. 즉, 정점 u와 v가 연결되어 있으면, 정점 u에서 정점 v로도 이동할 수 있고, 정점 v에서 정점 u로도 이동할 수 있다는 의미이다. 아래는 무방향 그래프의 예시이다.

A -- B
|    |
C -- D

방향 그래프는 간선에 방향이 있는 그래프이다. 즉, 정점 u와 v가 연결되어 있으면, 정점 u에서만 정점 v로 이동할 수 있고, 정점 v에서 정점 u로는 이동할 수 없다는 의미이다. 아래는 방향 그래프의 예시이다.

A --> B
|     |
V     V
C --> D

가중치 그래프는 간선에 가중치 또는 비용을 할당할 수 있는 그래프이다. 이러한 가중치는 간선을 통해 이동하는 비용을 나타내는데 사용된다. 가중치 그래프는 최단 경로 문제와 같은 문제를 해결하는데 유용하다. 아래는 가중치 그래프의 예시이다.

   2
A --> B
|  	 |
4 	 3
|  	 |
V  	 V
C --> D
   1

연결 그래프는 그래프 내의 모든 정점이 서로 연결되어 있어서, 어떤 정점에서 다른 정점으로 이동할 수 있는 그래프이다. 즉, 두 정점 사이에 항상 경로가 존재한다는 의미이다. 아래는 연결 그래프의 예시이다.

A -- B
|    |
C -- D

비연결 그래프는 그래프 내의 일부 정점이 서로 연결되어 있지 않아서, 어떤 정점에서 다른 정점으로 이동할 수 없는 그래프이다. 즉, 두 정점 사이에 경로가 반드시 존재하지 않는다는 의미이다. 아래는 비연결 그래프의 예시이다.

A -- B     E -- F
|         |
C -- D     G

위에서 소개한 그래프의 종류와 특성은 그래프 이론에서 매우 중요하다. 그래프를 구현하고 문제를 해결하기 위해서는 각각의 그래프 종류와 특성에 대한 이해가 필요하다. 따라서 그래프를 다루는 프로그램을 작성하는 경우, 위 내용을 참고하여 코드를 작성하면 유용하다.