【データ構造】図の隣接マトリクス格納が実現

図の隣接表格納実現:http://blog.csdn.net/wenqian1991/article/details/24667287
図の隣接表DFSとBFSアルゴリズム:http://blog.csdn.net/wenqian1991/article/details/24812393
ここでは、図のもう一つの記憶方式を紹介します.隣接マトリクスです.参考資料「大話データ構造」「Cアルゴリズム:巻二」
一、図のデータ構造
図の隣接マトリクス格納方式は、2つのデータで表しています.1次元配列は、図中の頂点情報を記憶し、1つの2次元配列(隣接マトリクスという)は、図中の辺の情報を記憶する.
下の図を見てください.(画像は「大話データ構造」から来ています.)
                  

/*        */
typedef int VertexType;
typedef int EdgeType;
#define MAXVEX 100
#define INFI 65535

typedef struct 
{
	VertexType vexs[MAXVEX];           /*   */
	EdgeType matrix[MAXVEX][MAXVEX];   /*    */
	unsigned int numVertexes;          /*   */
	unsigned int numEdges;             /*  */
}Graph;

二、図を作成する

/*           */
Graph* CreateGraph()
{
	Graph *pGragh = new Graph;
	if (NULL == pGragh)
		return NULL;

	cout << "        ：" << endl;
	cin >> pGragh->numVertexes >> pGragh->numEdges;

	for (int i = 0; i < pGragh->numVertexes; ++i)/*     */
		(pGragh->vexs)[i] = i;
	for (int i = 0; i < pGragh->numVertexes; ++i)/*       */
	{
		for (int j = 0; j < pGragh->numVertexes; ++j)
		{
			(pGragh->matrix)[i][j] = INFI;
			if (i == j)
				(pGragh->matrix)[i][j] = 0;
		}
	}
	for (int k = 0; k < pGragh->numEdges; ++k)
	{
		int i, j, w;
		cout << "   (vi,vj)    i，  j   w：" << endl;
		cin >> i >> j >> w;
		(pGragh->matrix)[i][j] = w;
		(pGragh->matrix)[j][i] = (pGragh->matrix)[i][j];//        
	}
	return pGragh;
}

/*           */
Graph* CreateDiGraph()
{
	Graph *pGragh = new Graph;
	if (NULL == pGragh)
		return NULL;

	cout << "        ：" << endl;
	cin >> pGragh->numVertexes >> pGragh->numEdges;

	for (int i = 0; i < pGragh->numVertexes; ++i)/*     */
		(pGragh->vexs)[i] = i;
	for (int i = 0; i < pGragh->numVertexes; ++i)/*       */
	{
		for (int j = 0; j < pGragh->numVertexes; ++j)
		{
			(pGragh->matrix)[i][j] = INFI;
			if (i == j)
				(pGragh->matrix)[i][j] = 0;
		}
	}
	for (int k = 0; k < pGragh->numEdges; ++k)
	{
		int i, j, w;
		cout << "   <vi,vj>    i，  j   w：" << endl;
		cin >> i >> j >> w;
		(pGragh->matrix)[i][j] = w;//         ，          
	}
	return pGragh;
}

三、図中の二つの頂点の間に辺があるかどうかを確認する.

/*            
         ，     。               */
bool GraphHasEdge(Graph *pGraph, unsigned int begin, unsigned int end)
{
	if (NULL == pGraph || begin >= pGraph->numVertexes || end >= pGraph->numVertexes)
		return false;
	if (begin == end)
		return false;

	return ((pGraph->matrix)[begin][end] != INFI) ? true : false;
}

四、DFS
DFSとBFSについての紹介はオープンリンクを参照してください.

/*DFS*/
/*             */
void DFSUtil(Graph *pGraph, int start, bool visited[])
{
	visited[start] = true;
	cout << start << endl;

	for (int j = 0; j < pGraph->numVertexes; ++j)
	{
		if ((pGraph->matrix)[start][j] != 0 && (pGraph->matrix)[start][j] != INFI && !visited[j])
			DFSUtil(pGraph, j, visited);
	}
}
/*           */
void DFS(Graph *pGraph)
{
	if (NULL == pGraph)
		return;
	bool *visited = new bool[pGraph->numVertexes];
	memset(visited, false, pGraph->numVertexes);

	for (int i = 0; i < pGraph->numVertexes; ++i)
	{
		if (!visited[i])
			DFSUtil(pGraph, i, visited);
	}
	delete[] visited;
}

五、BFS

/*BFS*/
void BFS(Graph *pGraph)
{
	if (NULL == pGraph)
		return;

	bool *visited = new bool[pGraph->numVertexes];
	memset(visited, false, pGraph->numVertexes);

	list<int> queue;//          
	for (int i = 0; i < pGraph->numVertexes; ++i)
	{
		if (!visited[i])
		{
			visited[i] = true;
			cout << pGraph->vexs[i] << endl;
			queue.push_back(i);
			while (!queue.empty())
			{
				i = *queue.begin();
				queue.pop_front();
				for (int j = 0; j < pGraph->numVertexes; ++j)
				{
					if ((pGraph->matrix)[i][j] != 0 && (pGraph->matrix)[i][j] != INFI && !visited[j])
					{
						visited[j] = true;
						cout << pGraph->vexs[j] << endl;
						queue.push_back(j);
					}
				}
			}
		}
	}
}

ここでは関連コードのみを提供します.コードはテストされました.理論部分は関連資料を参照してください.