const int MAXSIZE = 50; //顶点最大数目
#include <vector>
using namespace std;
template<typename T>
class CGraph
{
public:
CGraph(void);
~CGraph(void);
private:
vector<T> vecNodes;//顶点列表
int edge[MAXSIZE][MAXSIZE];//边表
int numVertexs;//顶点数
int numEdges;//边数
bool visited[MAXSIZE];//用于图的遍历
int FindVertex(const T& vertex,const vector<T> &lst);
void ClearVisitFlag();
vector<T>& GraphDepthFirstSearch(const T& beginVertex);//深度遍历图
vector<T>& GraphBreadthFirstSearch();//广度遍历
public:
bool GraphEmpty(void)const;
bool GraphFull(void)const;
int NumberOfVertices(void)const;//获取顶点数
int NumberOfEdges(void)const;//获取边数
int GetWeight(const T&vertex1,const T& vertex2);//获取指定两个顶点间的权值
vector<T>& GetNeighbors(const T& vertex);//获取指定顶点的邻接顶点
void CreateGraph();//创建图
int GetVertexPos(const T& vertex);//获取指定顶点的位置
int InsertVertex(const T& vertex);//插入顶点
void InsertEdge(const T& vertex1,const T& vertex2,int weight);//插入边
void DeleteVertex(const T& vertex);//删除顶点
void DeleteEdge(const T& vertex1,const T& vertex2);//删除边
//int MinimumPath(const T& sVertex,const T& desVertex);最短路径
void DepthFirstSearch();//深度遍历图
void BreadthFirstSearch();//广度遍历图
};
复制代码
图的实现代码
测试程序：
复制代码
#include "Graph.cpp"
#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
CGraph<int> *graph1 = new CGraph<int>();
graph1->CreateGraph();
graph1->DepthFirstSearch();
graph1->BreadthFirstSearch();
system("pause");
return 0;
}
复制代码
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2008/07/23/1249996.html，如需转载请自行联系原作者
