図の記憶

図:頂点セット(vertex)と頂点間の関係セットからなる線形構造.
図の記憶:臨接行列:すべての頂点の情報を1つの頂点テーブルに整理し、各頂点間の臨接関係を行列で表し、臨接行列と呼ぶ.
隣接テーブル:配列を使用して頂点セットを格納し、チェーンテーブルを使用してエッジの関係をリンクします.
図の隣接マトリクス記憶実装コード:

#pragma once

#include<assert.h>

template<class V, class W>
class GraphMatrix
{
public:
	GraphMatrix(const V* vArray, int size, bool IsDigraph = false)
		:_vArray(new V[size])
		, _vSize(size)
		, IsDigraph(IsDigraph)
	{
		_Matrix = new W*[_vSize];
		for (int i = 0; i < size; ++i)
		{
			_vArray[i] = vArray[i];
			_Matrix[i] = new W[_vSize];
			memset(_Matrix[i], 0, sizeof(W)*_vSize);
		}
	}

	int GetVertexIndex(const V& vt)
	{
		for (int i = 0; i < _vSize; ++i)
		{
			if (_vArray[i] == vt)
			{
				return i;
			}
		}
		return -1;
	}

	void AddEdge(const V& src, const V& dst, const W& weight)
	{
		int srcIndex = GetVertexIndex(src);
		int dstIndex = GetVertexIndex(dst);

		assert(srcIndex != -1);
		assert(dstIndex != -1);

		if (IsDigraph)
		{
			_Matrix[srcIndex][dstIndex] = weight;
		}
		else
		{
			_Matrix[srcIndex][dstIndex] = weight;
			_Matrix[dstIndex][srcIndex] = weight;
		}
	}

	void Display()
	{
		for (int i = 0; i < _vSize; ++i)
		{
			cout << _vArray[i] << " ";
		}
		cout << endl;

		for (int i = 0; i < _vSize; ++i)
		{
			for (int j = 0; j < _vSize; ++j)
			{
				cout << _Matrix[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;
	}

	~GraphMatrix()
	{
		if (_vArray != NULL)
		{
			delete[] _vArray;
			_vArray = NULL;
			for (int i = 0; i < _vSize; ++i)
			{
				delete[] _Matrix[i];
				_Matrix[i] = NULL;
			}
			delete[] _Matrix;
			_Matrix = NULL;
		}	
	}

private:
	V* _vArray;           //   
	int _vSize;          //   
	W** _Matrix;         //    
	bool IsDigraph;
};

テスト例:

void TestGraphMatrix1()
{
	GraphMatrix<char, int> gm("ABCDE", 5);
	gm.AddEdge('A', 'D', 10);
	gm.AddEdge('A', 'E', 20);
	gm.AddEdge('B', 'C', 10);
	gm.AddEdge('B', 'D', 20);
	gm.AddEdge('B', 'E', 30);
	gm.AddEdge('C', 'E', 40);
	gm.Display();
}

//   
void TestGraphMatrix2()
{
	GraphMatrix<char, int> gm("ABCDE", 5, true);
	gm.AddEdge('A', 'D', 10);
	gm.AddEdge('E', 'A', 20);
	gm.AddEdge('B', 'C', 10);
	gm.AddEdge('D', 'B', 20);
	gm.AddEdge('E', 'B', 30);
	gm.AddEdge('C', 'E', 40);
	gm.Display();
}

図の隣接表は実現コードを記憶する:

#pragma once

template<class V, class W>
struct LinkEdge
{
	W _w;
	size_t _srcIndex;
	size_t _dstIndex;
	LinkEdge<V, W>* _next;

	LinkEdge(size_t srcIndex, size_t dstIndex, const W& w)
		: _w(w)
		, _srcIndex(srcIndex)
		, _dstIndex(dstIndex)
		, _next(NULL)
	{}
};

template<class V, class W>
struct LinkVertex
{
	V _vertex;
	LinkEdge<V, W>* _head;

	LinkVertex(const V& vertex = V())
		:_vertex(vertex)
		, _head(NULL)
	{}
};

template<class V, class W>
class GraphLink
{
public:
	GraphLink(const V* vArray, int size, bool IsDigraph = false)
		:_vSize(size)
		, _IsDigraph(IsDigraph)
	{
		_LinkTable = new LinkVertex<V, W>[size];
		for (int i = 0; i < size; i++)
		{
			_LinkTable[i]._vertex = vArray[i];
		}
	}

public:
	void AddEdge(const V& src, const V& dst, const W& weight)
	{
		int srcIndex = GetVertexIndex(src);
		int dstIndex = GetVertexIndex(dst);

		assert(srcIndex != -1);
		assert(dstIndex != -1);

		if (_IsDigraph)
		{
			_AddEdge(srcIndex, dstIndex, weight);	
		}
		else
		{
			_AddEdge(srcIndex, dstIndex, weight);
			_AddEdge(dstIndex, srcIndex, weight);
		}
	}

	void Display()
	{
		for (int i = 0; i < _vSize; i++)
		{
			cout << _LinkTable[i]._vertex << "[" << i << "]->";
			LinkEdge<V, W>* cur = _LinkTable[i]._head;
			while (cur != NULL)
			{
				cout << cur->_w << "[" << cur->_dstIndex << "]->";
				cur = cur->_next;
			}
			cout << "NULL" << endl;
		}
		cout << endl;
	}

protected:
	int GetVertexIndex(const V& vertex)
	{
		for (int i = 0; i < _vSize; i++)
		{
			if (_LinkTable[i]._vertex == vertex)
			{
				return i;
			}
		}
		return -1;
	}

	void _AddEdge(const V& srcIndex, const V& dstIndex, const W& weight)
	{
		LinkEdge<V, W>* head = _LinkTable[srcIndex]._head;
		LinkEdge<V, W>* tmp = new LinkEdge<V, W>(srcIndex, dstIndex, weight);

		tmp->_next = head;
		_LinkTable[srcIndex]._head = tmp;
	}

private:
	LinkVertex<V, W>* _LinkTable;
	int _vSize;
	bool _IsDigraph;
};

テスト例:

//   
void TestGraphLink1()
{
	GraphLink<char, int> gl("ABCDE", 5);
	gl.AddEdge('A', 'D', 10);
	gl.AddEdge('A', 'E', 20);
	gl.AddEdge('B', 'C', 10);
	gl.AddEdge('B', 'D', 20);
	gl.AddEdge('B', 'E', 30);
	gl.AddEdge('C', 'E', 40);
	gl.Display();
}

//   
void TestGraphLink2()
{
	GraphLink<char, int> gl("ABCDE", 5, true);
	gl.AddEdge('A', 'D', 10);
	gl.AddEdge('E', 'A', 20);
	gl.AddEdge('B', 'C', 10);
	gl.AddEdge('D', 'B', 20);
	gl.AddEdge('E', 'B', 30);
	gl.AddEdge('C', 'E', 40);
	gl.Display();
}