graph.cpp

数据结构中图的相关算法的 应用与分析

#define UNVISITED 0
#define VISITED 1
#define INFINITY 9999999
#include <iostream.h>
#include <fstream.h>
#include "LList.h"
#include <queue>

class Edge//边
{
public:
	int from,to,weight;    //from是边的始点,to是边的终点,weight是边的权
	Edge()                 //构造函数
	{
		from=-1;   
		to=-1;  
		weight=0;
	}	
	Edge(int f,int t,int w)  //构造函数
	{
		from=f;   
		to=t;   
		weight=w;
	}
	bool operator >(Edge oneEdge)   //定义比较运算符>,边的大小比较即为边的权的大小比较
	{
		return weight>oneEdge.weight;
	}
	bool operator <(Edge oneEdge)  
	{
		return weight<oneEdge.weight;
	}
};
class Graph//图的定义
{
public:
	int numVertex;	//图的顶点的个数
	int numEdge;    //图的边的个数
	int *Mark;      //Mark指针指向保存有图的顶点的标志位的数组,标志位用来标记某顶点是否被访问过
	int *Indegree;  //Indegree指针指向保存有图的顶点的入度的数组		
	Graph(int numVert)               //构造函数
	{
		numVertex=numVert;           //确定图的顶点的个数
		numEdge=0;                   //确定图的边数的个数
		Indegree=new int[numVertex]; //为保存图的顶点的入度申请数组,Indegree为数组指针
		Mark=new int[numVertex];     //为图的顶点的标志位申请数组,Mark为数组指针
		for(int i=0;i<numVertex;i++) //确定图的顶点的标志位和入度,即所有顶点的标志位初始化为未被访问过,入度初始化为0
		{
			Mark[i]=UNVISITED;
			Indegree[i]=0;
		}
	}
	~Graph()                         //析构函数
	{
		delete [] Mark;              //释放Mark数组
		delete [] Indegree;          //释放Indegree数组
	}
	virtual Edge FirstEdge(int oneVertex)=0;  //返回与顶点oneVertex相关联的第一条边
    virtual Edge NextEdge(Edge preEdge)=0;    //返回与边PreEdge有相同关联顶点oneVertex的下一条边
    int VerticesNum()              //返回图的顶点个数
	{
		return numVertex;
	}
    int EdgesNum()                 //返回图的边数
	{
		return numEdge;
	}  
    bool IsEdge(Edge oneEdge)      //如果oneEdge是边则返回TRUE，否则返回FALSE
	{
		if(oneEdge.weight>0&&oneEdge.weight<INFINITY&&oneEdge.to>=0) 				
		{
			return true;
		}
		else 
		{
			return false;
		}
	}
	int FromVertex(Edge oneEdge)   //返回边oneEdge的始点
	{
		return oneEdge.from;
	}
	int ToVertex(Edge oneEdge)     //返回边oneEdge的终点
	{
		return oneEdge.to;
	}
	int Weight(Edge oneEdge)	   //返回边oneEdge的权
	{
		return oneEdge.weight;
	}
	virtual void setEdge(int from,int to,int weight)=0;
	virtual void delEdge(int from,int to)=0;
};
struct listUnit      //邻接表表目中 数据部分的结构定义
{
	int vertex;      //边的终点
	int weight;      //边的权
};
class Graphl: public Graph                    
{
private:
	LList<listUnit> *graList;    //graList是保存所有边表的数组	
public:
	Graphl(int numVert):Graph(numVert)          //构造函数
	{
		graList=new LList<listUnit>[numVertex]; //为graList数组申请空间，图有numVertex个顶点，则有numVertex个边表
	}
	~Graphl()                                   //析构函数
	{
		delete []graList;						//释放空间
	}
	
	Edge FirstEdge(int oneVertex)              //返回顶点oneVertex的第一条边
	{
		Edge myEdge;                           //边myEdge将作为函数的返回值
		myEdge.from=oneVertex;                 //将顶点oneVertex作为边myEdge的始点
		Link<listUnit> *temp=graList[oneVertex].head;  //graList[oneVertex].head保存的是顶点oneVertex的边表，temp->next指向顶点oneVertex的第一条边(如果temp->next不为null)
		if(temp->next!=NULL)                   //如果顶点oneVertex的第一条边确实存在
		{
			myEdge.to=temp->next->element.vertex;
			myEdge.weight=temp->next->element.weight;
		}
		return myEdge;	                      //如果找到了顶点oneVertex的第一条边,则返回的myEdge确实是一条边;如果没有找到顶点oneVertex的第一条边,则myEdge的成员变量to为-1,根据IsEdge函数判断可知myEdge不是一条边
	}	
	Edge NextEdge(Edge preEdge)               //返回与边PreEdge有相同关联顶点oneVertex的下一条边
	{
		Edge myEdge;                          //边myEdge将作为函数的返回值
		myEdge.from=preEdge.from;             //将边myEdge的始点置为与上一条边preEdge的始点相同
		Link<listUnit> *temp=graList[preEdge.from].head;           //graList[oneVertex].head保存的是顶点oneVertex的边表，temp->next指向顶点oneVertex的第一条边(如果temp->next不为null)
		while(temp->next!=NULL&&temp->next->element.vertex<=preEdge.to)  //确定边preEdge在边表中的位置,如果边preEdge的下一条边确实存在，则temp->next指针指向下一条边的表目
		{
			temp=temp->next;
		}
		if(temp->next!=NULL)                 //边preEdge的下一条边存在			                                
		{
			myEdge.to=temp->next->element.vertex;
			myEdge.weight=temp->next->element.weight;			
		}
		return myEdge;
	}	
	void setEdge(int from,int to,int weight)   //为图设定一条边
	{
		Link<listUnit> *temp=graList[from].head;  //graList[from].head保存的是顶点from的边表，temp->next指向顶点from的第一条边(如果temp->next不为null)
		while(temp->next!=NULL&&temp->next->element.vertex<to)   //确定边(from,to)或<from,to>在边表中的位置,如果不存在,则边(from,to)或<from,to>为新加的一条边
		{
			temp=temp->next;
		}
		if(temp->next==NULL)                //边(from,to)或<from,to>在边表中不存在且在边表中其后已无其它边,则在边表中加入这条边
		{
			temp->next=new Link<listUnit>;
			temp->next->element.vertex=to;
			temp->next->element.weight=weight;
			numEdge++;
			Indegree[to]++;
			return;
		}
		if(temp->next->element.vertex==to) //边(from,to)或<from,to>在边表中已存在,故只需要改变边的权值
		{
            temp->next->element.weight=weight;
			return;
		}
		if(temp->next->element.vertex>to) //边(from,to)或<from,to>在边表中不存在,但在边表中其后存在其它边,则在边表中插入这条边
		{
			Link<listUnit> * other=temp->next;
			temp->next=new Link<listUnit>;
			temp->next->element.vertex=to;
			temp->next->element.weight=weight;
			temp->next->next=other;
			numEdge++;
			Indegree[to]++;			
		}
	}
	void delEdge(int from,int to)      //删掉图的一条边
	{
		Link<listUnit> *temp=graList[from].head;      //graList[from].head保存的是顶点from的边表，temp->next指向顶点from的第一条边(如果temp->next不为null)
		while(temp->next!=NULL&&temp->next->element.vertex<to)   //确定边(from,to)或<from,to>在边表中的位置(如果该边存在)
		{
			temp=temp->next;
		}
		if(temp->next==NULL) return;   //边(from,to)或<from,to>在边表中不存在,则不需要做任何操作	
		if(temp->next->element.vertex==to)  //边(from,to)或<from,to>在边表中存在且确定了该边在边表中的位置,则从边表中将其删掉
		{
			Link<listUnit> *other=temp->next->next;
			delete temp->next;
			temp->next=other;
			numEdge--;
			Indegree[to]--;			
		}
	}
};