发一些编写过的带权有向图的最短路径，以及拓扑排序的算法实现(算法都集成在GraphDirect<T,E>类中)
首先是带权有向图的GraphDirect<T,E>类的基本实现:所有代码请指教，需要的朋友也可以参考，总之大家共勉。
相信这些算法也是大家最常见的了。
#ifndef GRAPHICDIRECT_H
#define GRAPHICDIRECT_H
#include<iostream.h>
#include<stdlib.h>
#include"SeqStack.h"
const int DefaultVertices=30;
const int maxWeight=100000;
/////////////////////////////////////////////////
//Edge 边结点结构的定义
/////////////////////////////////////////////////
template<class T,class E>
struct Edge
{
int dest; //目的结点的结点号
E cost; //边对应的权值
Edge<T,E>* link; //下一条边结点的指针
Edge(){}; //默认构造函数
Edge(int num,E weight)//带参数的构造函数
:dest(num),cost(weight),link(NULL){};
bool operator!=(Edge<T,E>& R)const
{ //成员重载运算符
if(R.dest==dest) //判断两个边结点是否相等
return true;
else
return false;
};
};
///////////////////////////Edge边结点结构定义结束
/////////////////////////////////////////////////
//Vertex结构 图的顶点结点的定义
/////////////////////////////////////////////////
template<class T,class E>
struct Vertex
{
T data; //结点的数据域
Edge<T,E>* adj;//边链表的首指针
};
///////////////////////////Vertex顶点结构定义结束
/////////////////////////////////////////////////
//Graphlink<T,E>类模板的实现
//以邻接链表方式实现的带权有向图的类模
//板的声明和实现T是顶点数据域类型,E是边的权值类型
/////////////////////////////////////////////////
template<class T,class E>
class GraphDirect
{
private:
Vertex<T,E>* NodeTable; //顶点表数组
bool* visited; //用于标记第i个结点是否被访问的数组
int maxVertices; //图中最大的顶点个数
int numEdges; //当前边的条数
int numVertices; //当前顶点的个数
public:
GraphDirect(int sz=DefaultVertices); //默认构造函数
~GraphDirect(); //析构函数
bool insertVertex(const T vertex); //在图中插入一个顶点vertex
bool insertEdge(int v1,int v2,E cost); //插入一条边以及对应的权值
E getWeight(int v1,int v2); //取得边(v1,v2)上的权值
bool TopologicalSort(); //对当前的有向图进行拓扑排序
void Dijkstra(int v); //迪吉斯特拉算法求单源最短路径
void Bellman(int v); //带负权值单源有向图最短路径求解
void DisplayPath(int v,E* d,int* pa); //显示path数组中保存的最短路径
void Floyd(); //求所有顶点之间的最短路径
//友元重载输出运算符
friend ostream& operator<<(ostream& os,GraphDirect<T,E>& G);
};
/////////////////////Graphlink<T,E>类模板声明结束
/////////////////////////////////////////////////
//构造函数 构造一个空的有向图的类
/////////////////////////////////////////////////
template<class T,class E>
GraphDirect<T,E>::GraphDirect(int sz)
{
maxVertices=sz; //初始化相关数据
numEdges=0;
numVertices=0;
NodeTable=new Vertex<T,E>[maxVertices]; //分配顶点数组的空间
if(NodeTable==NULL) //如果内存分配失败
{
cout<<"顶点数组内存分配失败!"<<endl;
exit(1);
};
for(int i=0;i<maxVertices;i++) //把所有的结点的边链表链接指针清NULL
NodeTable[i].adj=NULL;
};
/////////////////////////////////////构造函数结束
/////////////////////////////////////////////////
//析构函数 释放所有所有结点和边链表的恶内存空间
/////////////////////////////////////////////////
template<class T,class E>
GraphDirect<T,E>::~GraphDirect()
{
for(int i=0;i<numVertices;i++) //释放所有的边链表的内存
{
Edge<T,E>* ptr=NodeTable[i].adj; //获取每个边链表的头指针
Edge<T,E>* pre;
while(ptr!=NULL)
{
pre=ptr;
ptr=ptr->link;
delete pre;
};
};
delete [] NodeTable; //再释放结点数组的内容
};
/////////////////////////////////////析构函数结束
/////////////////////////////////////////////////
//insertVertex()公有成员函数
//在当前的代权有向图中插入一个结点
//T是结点的恶数据类型
/////////////////////////////////////////////////
template<class T,class E>
bool GraphDirect<T,E>::insertVertex(T x)
{
if(numVertices==maxVertices) //如果当前的顶点数组已经满了
return false; //插入失败
NodeTable[numVertices].data=x;
numVertices++; //顶点的个数增加一个
return true; //插入成功
};
///////////////////////////insertVertex()函数结束
/////////////////////////////////////////////////
//insertEdge()公有成员函数 插入一条有向边
//其中参数i是前驱顶点编号,j是后继结点编号,weight是权
/////////////////////////////////////////////////
template<class T,class E>
bool GraphDirect<T,E>::insertEdge(int i,int j,E weight)
{
if(i>=numVertices || j>=numVertices) //结点号错误
return false;
Edge<T,E>* ptr=NodeTable[i].adj; //ptr指向结点i的边链表头
Edge<T,E>* newEdge
=new Edge<T,E>(j,weight); //新建一个边结点
if(ptr==NULL) //如果边链表是空的
{
NodeTable[i].adj=newEdge; //就直接挂入
numEdges++;
return true; //插入成功
};
while(ptr->link!=NULL) //让ptr指向边链表尾
ptr=ptr->link;
ptr->link=newEdge; //在边链表尾插入边结点
numEdges++;
return true;
};
/////////////////////////////insertEdge()函数结束
/////////////////////////////////////////////////
//getWeight()公有成员函数
//得到指定边(v1,v2)上的权值
/////////////////////////////////////////////////
template<class T,class E>
E GraphDirect<T,E>::getWeight(int v1,int v2)
{
Edge<T,E>* ptr=NodeTable[v1].adj;//得到v1结点的边链表的首指针
if(v1==v2) //如果是自环
return 0;
while(ptr!=NULL) //遍历该边链表找结点v2
{
if(ptr->dest==v2) //如果找到就返回
return ptr->cost;
ptr=ptr->link;
}
return maxWeight; //即这两点之间不存在边
};
//////////////////////getWeight()公有成员函数结束
/////////////////////////////////////////////////
//友元重载<<输出运算符
/////////////////////////////////////////////////
template<class T,class E>
ostream& operator<<(ostream& os,GraphDirect<T,E>& G)
{
cout<<"当前图的内容是:"<<endl;
Edge<T,E>* ptr;
for(int i=0;i<G.numVertices;i++)
{
cout<<"第"<<i<<"个顶点"<<T(G.NodeTable[i].data)<<"边结点:";
ptr=G.NodeTable[i].adj;
while(ptr!=NULL)
{
cout<<"("<<ptr->dest<<","<<ptr->cost<<")"<<" ";
ptr=ptr->link;
};
cout<<endl;
};
cout<<"当前图的总结点数是:"<<G.numVertices<<endl;
cout<<"当前图的总边的个数:"<<G.numEdges<<endl;
return os;
};
///////////////////////////////////<<友元重载结束
[[it] 本帖最后由 geninsf009 于 2008-11-29 19:31 编辑 [/it]]
