[자료구조] 가중 그래프

가중 그래프는 일반적인 그래프와 비슷하지만 그래프 간선에 추가적인 정보를 포함한다.

위 그래프의 간선에는 간선이 연결하는 도시 간 항공료가 표시되어 있다. 그래프에 가중치를 추가하려면 배열 대신 해시 테이블을 사용해야 한다. 클래스로 간단하게 표현해 보자.

#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;

class CCity
{
public:
	CCity(string _name) : name(_name) {}

	void add_route(CCity* city, int _price)
	{
		price.insert(pair<CCity*, int>(city, _price));
	}
	int get_price(CCity* city)
	{
		auto p = price.find(city);
		return p->second;
	}

	string name;
	map<CCity*, int> price;
};

int main()
{
	CCity* dallas = new CCity("Dallas");
	CCity* toronto = new CCity("Toronto");
	dallas->add_route(toronto, 138);
	toronto->add_route(dallas, 216);

	cout << "dallas -> toronto price : $" << dallas->get_price(toronto) << endl;
	return 0;
}