10-1. 가중치 그래프란?

가중치 그래프(weighted graph)란?

가중치 그래프는 간선에 비용이나 가중치가 할당된 그래프이다.

가중치 그래프는 정점의 연결 정보뿐만 아니라 연결에 필요한 비용(거리, 시간, 비용 등)을 함께 표현할 수 있다.

가중치 그래프의 응용 분야는 매우 다양하다.

위 그림과 같은 지도, 인터넷 망과 같은 컴퓨터 네트워크 등 실생활에 밀접한 그래프를 표현하기에 적합하다.

---

가중치 그래프의 표현

가중치가 없는 그래프에서는 그래프 정보를 저장할 때 정점들 간의 연결 관계만들 저장했다.

연결이 되어 있다면 1, 아니라면 0 이런 식이었다.

 

하지만, 가중치 그래프에서는 단순 연결 관계만을 저장하는 것이 아니다.

간선의 가중치 값이 0이나 1 일수도 있기 때문에 연결 되어 있지 않은 상태를 0으로 저장하면 안된다.

가중치 그래프에서 정점이 연결되어 있다면 간선이 어떤 값을 갖고 있도록 할 것이고, 

정점이 연결되어 있지 않다면 아주 큰 값(INF)을 간선에 할당할 것이다.