// 圖
namespace Matrix
{
	// V頂點(diǎn)類型 W邊權(quán)值類型 MAX_W表示邊不存在的值 Direction表示圖是否有向
	template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
	class Graph
	{
	public:
		Graph(const V* vertexs, size_t n)
		{
			_vertexs.reserve(n);
			for (size_t i = 0; i < n; ++i)
			{
				_vertexs.push_back(vertexs[i]);
				_vIndexMap[vertexs[i]] = i;
			}
			// MAX_W 作為不存在邊的標(biāo)識(shí)值
			// 初始化時(shí)默認(rèn)沒有邊，邊需要一條一條手動(dòng)添加，用AddEdge函數(shù)
			_matrix.resize(n);
			for (auto& e : _matrix)
			{
				e.resize(n, MAX_W);
			}
		}
		// 找到一個(gè)頂點(diǎn)的映射下標(biāo)
		size_t GetVertexIndex(const V& v)
		{
			auto ret = _vIndexMap.find(v);
			if (ret != _vIndexMap.end())
			{
				return ret->second;
			}
			else
			{
				throw invalid_argument("不存在的頂點(diǎn)");
				return -1;
			}
		}
		// 添加一條邊，src和dst代表兩端頂點(diǎn)，w是權(quán)值
		void AddEdge(const V& src, const V& dst, const W& w)
		{
			size_t srci = GetVertexIndex(src);
			size_t dsti = GetVertexIndex(dst);
			_matrix[srci][dsti] = w;
			//如果是無向圖，則[dsti][srci]也需添加邊
			if (Direction == false)
			{
				_matrix[dsti][srci] = w;
			}
		}
	private:
		map<V, size_t> _vIndexMap;   // 頂點(diǎn)到下標(biāo)的映射
		vector<V> _vertexs;			 // 頂點(diǎn)集合
		vector<vector<W>> _matrix;   // 領(lǐng)接矩陣 存儲(chǔ)邊
	};
}

// 臨接表
namespace LinkTable
{
	// 定義邊結(jié)構(gòu), W是權(quán)值類型
	template<class W>
	struct LinkEdge
	{
		int _srcIndex;
		int _dstIndex;
		W _w;
		LinkEdge<W>* _next;
		LinkEdge(const W& w)
			: _srcIndex(-1)
			, _dstIndex(-1)
			, _w(w)
			, _next(nullptr)
		{ }
	};
	template<class V, class W, bool Direction = false>
	class Graph
	{
		typedef LinkEdge<W> Edge;
	public:
		Graph(const V* vertexs, size_t n)
		{
			_vertexs.reserve(n);
			for (size_t i = 0; i < n; ++i)
			{
				_vertexs.push_back(vertexs[i]);
				_vIndexMap[vertexs[i]] = i;
			}
			_linkTable.resize(n, nullptr);
		}
		size_t GetVertexIndex(const V& v)
		{
			auto ret = _vIndexMap.find(v);
			if (ret != _vIndexMap.end())
			{
				return ret->second;
			}
			else
			{
				throw invalid_argument("不存在的頂點(diǎn)");
				return -1;
			}
		}
		// 添加邊
		void AddEdge(const V& src, const V& dst, const W& w)
		{
			size_t srcindex = GetVertexIndex(src);
			size_t dstindex = GetVertexIndex(dst);
			Edge* sd_edge = new Edge(w);
			sd_edge->_srcIndex = srcindex;
			sd_edge->_dstIndex = dstindex;
			sd_edge->_next = _linkTable[srcindex];
			_linkTable[srcindex] = sd_edge;
			// 如果是無向圖，還要反過來添加一次
			if (Direction == false)
			{
				Edge* ds_edge = new Edge(w);
				ds_edge->_srcIndex = dstindex;
				ds_edge->_dstIndex = srcindex;
				ds_edge->_next = _linkTable[dstindex];
				_linkTable[dstindex] = ds_edge;
			}
		}
	private:
		map<string, int> _vIndexMap; // 頂點(diǎn)到下標(biāo)的映射
		vector<V> _vertexs;			 // 頂點(diǎn)集合
		vector<Edge*> _linkTable;    // 邊的集合的領(lǐng)接表
	};
}