[자료구조] 그래프

1. 개념

정점(노드)과 간선(에지)으로 이루어진 자료구조. 정점은 고유한 식별자를 가지고 있고, 간선은 정점들끼리의 관계를 나타낸다.

 

2. 종류

1) 방향 그래프

간선에 방향성이 있는 그래프를 의미한다. A에서 출발해서 B로 가는 간선이 존재한다면 이는 A에서 B로 가는 방향을 가진 간선이고, 이러한 정점과 간선을 모아 놓으면 방향 그래프이다. A에서 B로는 갈 수 있지만, B에서 A로 가는 길은 없다.

2) 무방향 그래프

간선에 방향이 없다. A에서 B가 연결되어 있으면 출발과 도착이 없고 그냥 둘이 연결 된 거다. A에서 B로 갈 수 있고, B에서 A로도 갈 수 있다. 

3) 가중치 그래프

A와 B가 연결이 되어 있는데 그 연결된 간선에 가중치가 부여된 것이다. 이러한 가중치는 두 정점 사이의 거리, 비용, 시간등이 될 수 있다.

4) 연결 그래프

그래프의 모든 노드가 적어도 한 경로를 통해 연결된 그래프이다.

5) 트리

무방향 그래프이면서, 사이클이 없는 연결 그래프이다.

6) 이분 그래프

어떤 그래프에 있는 노드를 두 집합으로 나눴을 때, 같은 집합 내의 노드끼리는 간선으로 연결되어 있지 않고, 다른 집합의 노드끼리는 간선으로 연결되어 있는 그래프. 이분그래프가 되려면 서로 다른 그룹의 노드끼리는 모두 연결이 가능해야한다.