学步园

算法原理参见《算法导论》

//MatrixGraph.h
#pragma once
#include <vector>

struct MatrixGraph
{
	enum{MAXVEX=100};
	static const int INFINITY;
	char vexs[MAXVEX]; //顶点类型 char
	int arc[MAXVEX][MAXVEX]; //邻接矩阵
	int numVerteices; //图中当前的顶点数
	int numEdges; //图中当前的边数
	MatrixGraph();
};

void MBFSTraverse(MatrixGraph & mGraph, int v);
//edgeIdPairs <i, j> 
//i, j为顶点编号 
struct Edge
{
	int i;
	int j;
	int weight;
};
void CreateMatrixGraph(MatrixGraph & mGraph, std::vector<char> & vertexName, std::vector<Edge> & edges);
//void MDFSTraverse(MatrixGraph & mGraph, int v);

//MatrixGraph.cpp
#include "MatrixGraph.h"
#include <iostream>
#include <memory.h>
#include <queue>
const int MatrixGraph::INFINITY = INT_MAX;

bool visited[MatrixGraph::MAXVEX];

MatrixGraph::MatrixGraph()
	:numVerteices(0),
	 numEdges(0)
{
	//temp
	memset(vexs, 0, sizeof(char)*MAXVEX);
	for(int i=0; i<MAXVEX; i++)
	{
		for(int j=0; j<MAXVEX; j++)
		{
			arc[i][j] = INFINITY;
		}
	}

	for(int i=0; i<MAXVEX; i++)
	{
		arc[i][i] = 0;
	}
}



void CreateMatrixGraph(MatrixGraph & mGraph, std::vector<char> & vertexName, std::vector<Edge> & edges)
{
	int count = vertexName.size();
	mGraph.numVerteices = count;

	//生成顶点
	for(int i=0; i<count; i++)
	{
		mGraph.vexs[i] = vertexName[i]; //i为顶点的编号
	}

	//生成边
	count = edges.size(); //一定是偶数
	for(int k=0;k<count; k++)
	{
		mGraph.arc[edges[k].i][edges[k].j] = mGraph.arc[edges[k].j][edges[k].i] = edges[k].weight; //无向图
	}
}

//返回v节点的第一个邻接顶点。若顶点v在图中没有邻接顶点，则返回-1
int FirstAdjVex(MatrixGraph & mGraph, int v)
{
	for(int j=0; j<mGraph.numVerteices; j++)
	{
		//图的边有权重 不相连的边的权重为INFINITY 权重为非负整数
		if(mGraph.arc[v][j] != MatrixGraph::INFINITY && mGraph.arc[v][j] != 0 && !visited[j])
		//if(mGraph.arc[v][j] != MatrixGraph::INFINITY && mGraph.arc[v][j] != 0)
			return j;
	}

	return -1;
}

//返回v的(相对于w的)下一个邻接顶点。若访问完了v的所有顶点，则返回-1
int NextAdjVex(MatrixGraph & mGraph, int v, int w)
{
	for(int j=w; j<mGraph.numVerteices; j++)
	{
		//图的边有权重 不相连的边的权重为INFINITY 权重为非负整数
		if(mGraph.arc[v][j] != MatrixGraph::INFINITY&& !visited[j]) 
		//if(mGraph.arc[v][j] != MatrixGraph::INFINITY) 
		{
			return j;
		}
	}
	return -1;
}

struct MVertex
{
	enum Color
	{
		Color_White,
		Color_Gray,
		Color_Black
	};
	int index;
	Color color;
	int d; //distance
	MVertex()
	{
	}
	MVertex(int _index, Color _color)
		:index(_index), color(_color)
	{
	}
};

//算法导论 22.2 Breadth-first search
void MBFSTraverse(MatrixGraph & mGraph, int startV)
{
	memset(visited, 0, sizeof(bool)*MatrixGraph::MAXVEX);
	//置空的辅助队列Q
	std::vector<MVertex> verticeHelper;
	for(int i=0; i<mGraph.numVerteices; i++)
	{
		verticeHelper.push_back(MVertex(i, MVertex::Color_White));
	}

	std::queue<MVertex> queueHelper;
	verticeHelper[startV].d = 0;
	queueHelper.push(verticeHelper[startV]);
	
	MVertex u;
	while(!queueHelper.empty())
	{
		u = queueHelper.front();
		visited[u.index] = true;
		queueHelper.pop();
		for(int v = FirstAdjVex(mGraph, u.index); v>-1; v=NextAdjVex(mGraph, u.index, v))
		{
			if(verticeHelper[v].color == MVertex::Color_White)
			{
				visited[v]=true;
				verticeHelper[v].d = u.d + 1;
				verticeHelper[v].color = MVertex::Color_Gray;
				queueHelper.push(verticeHelper[v]);
				printf("%c%(%i),",mGraph.vexs[v],verticeHelper[v].d); 
				//std::cout<<mGraph.vexs[v]<"()";	
				
			}
		}
		verticeHelper[u.index].color = MVertex::Color_Black;
	}

}

//TestMGraph.cpp
#include "MatrixGraph.h"

#define DefA 0
#define DefB 1
#define DefC 2
#define DefD 3
#define DefE 4
#define DefF 5
#define DefG 6
#define DefH 7
#define DefI 8

void CreateGraph1(MatrixGraph & mGraph)
{
	std::vector<char> vertexName;
	char arr[]={'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'};
	vertexName.insert(vertexName.begin(), arr, arr+9);

	std::vector<Edge> edges;
	Edge e;
	//1
	e.weight = 1;
	e.i = DefA;e.j=DefB;
	edges.push_back(e);
	//2
	e.i = DefF;e.j=DefE;
	edges.push_back(e);
	//3
	e.i = DefC;e.j=DefD;
	edges.push_back(e);
	//4
	e.i = DefI;e.j=DefD;
	edges.push_back(e);
	//5
	e.i = DefA;e.j=DefF;
	edges.push_back(e);
	//6
	e.i = DefB;e.j=DefG;
	edges.push_back(e);
	//7
	e.i = DefB;e.j=DefC;
	edges.push_back(e);
	//8
	e.i = DefD;e.j=DefE;
	edges.push_back(e);
	//9
	e.i = DefG;e.j=DefD;
	edges.push_back(e);
	//10
	e.i = DefG;e.j=DefF;
	edges.push_back(e);
	//11
	e.i = DefB;e.j=DefI;
	edges.push_back(e);
	//12
	e.i = DefG;e.j=DefH;
	edges.push_back(e);
	//13
	e.i = DefH;e.j=DefD;
	edges.push_back(e);
	//14
	e.i = DefH;e.j=DefE;
	edges.push_back(e);
	//
	e.i = DefC;e.j=DefI;
	edges.push_back(e);

	CreateMatrixGraph(mGraph, vertexName, edges);
}

void TestMGraph()
{
	MatrixGraph mGraph;
	CreateGraph1(mGraph);
	//MDFSTraverse(mGraph, 0);
	MBFSTraverse(mGraph, 0);
}

 结果

B(1),F(1),C(2),G(2),I(2),E(2),D(3),H(3),请按任意键继续. . .