g_graph.h

一个求无向无权图的最短路径的算法

//?:(005)g_graph.h
//:G_GRAPH.H header file (class file)
#ifndef G_GRAPH_H
#define G_GRAPH_H
typedef struct
{
	int row;							//row mark
	int col;							//column mark
	int weight;							//weight value
}rcw;
#include "l_list.h"
template<class T>
class g_graph
{
	int n_edge;							//The number of the edges
public:
	l_list<T> vertices;					//Used to store the vertices
int edge[maxvertices][maxvertices];	//A matrix used to store the edges
public:
	g_graph();
	void g_init(int n);
	void ins_vertex(T vertex);
	void ins_edge(int v1,int v2,int weight);
	void del_edge(int v1,int v2);
	int get_first_vex(int v);
	int get_next_vex(int v1,int v2);
	void creat_graph(T v[],int n,rcw e[],int e1);
	~g_graph();
};
template<class T>
g_graph<T>::g_graph()
{
}
template<class T>
void g_graph<T>::g_init(int n)
{
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			if(i==j) edge[i][j]=0;
			else edge[i][j]=maxweight;
		}
	n_edge=0;
}
template<class T>
void g_graph<T>::ins_vertex(T vertex)
{
	vertices.l_insert(vertices.get_size(),vertex);
}
template<class T>
void g_graph<T>::ins_edge(int v1,int v2,int weight)
{
	if(v1<0||v1>vertices.get_size()
		||v2<0||v2>vertices.get_size())
		exit(1);
	edge[v1][v2]=weight;
	edge[v2][v1]=weight;
	n_edge+=2;
}
template<class T>
void g_graph<T>::del_edge(int v1,int v2)
{
	if(v1<0||v1>vertices.get_size()||v2<0
		||v2>vertices.get_size()||v1==v2)
		exit(1);
	edge[v1][v2]=maxweight;
	edge[v2][v1]=maxweight;
	n_edge-=2;
}
template<class T>
int g_graph<T>::get_first_vex(int v)
{
	if(v<0||v>vertices.get_size())
		exit(1);
	for(int col=0;col<=vertices.get_size();col++)
		if(edge[v][col]>0&&edge[v][col]<maxweight) 
			return col;
	return -1;
}
template<class T>
int g_graph<T>::get_next_vex(int v1,int v2)
{
	if(v1<0||v1>vertices.get_size()||v2<0||
		v2>vertices.get_size())
		exit(1);
	for(int col=v2+1;col<vertices.get_size();col++)
		if(edge[v1][col]>0&&edge[v1][col]<maxweight)
			return col;
	return -1;
}
template<class T>
void g_graph<T>::creat_graph(T v[],int n,rcw e[],int e1)
{
	for(int i=0;i<n;i++)
		ins_vertex(v[i]);
	for(int k=0;k<e1;k++)
		ins_edge(e[k].row,e[k].col,e[k].weight);
}
template<class T>
g_graph<T>::~g_graph()
{
}
#endif
//:End the header file