my.cpp

此程序为有向无环的代码

#define UNVISITED 0
#define VISITED 1
#define INFINITY 9999999
#define ROOT -1

#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                    
{
	friend class Graphdup;       //Graphdup是下面我们将讨论的邻接多重表的实现方式

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]--;			
		}
	}
};
//算法部分:
void TopsortbyQueue(Graph& G)                     
{
	for(int i=0;i<G.VerticesNum();i++)     //初始化Mark数组
		G.Mark[i]=UNVISITED;

    using std::queue;
	queue<int> Q;                          //初始化队列
	
	for(i=0; i<G.VerticesNum(); i++)       //图中入度为0的顶点入队
	{
		if(G.Indegree[i]==0)    
		{
			Q.push(i);                            
		}
	}

	while(!Q.empty())                 //如果队列中还有图的顶点
	{
		int V=Q.front();		
		G.Mark[V]=VISITED;
		Q.pop();                     //一个顶点出队
			
		for(Edge e= G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e))  //所有与之相邻的点入度-1
		{				
			G.Indegree[G.ToVertex(e)]--;   //边e的终点的入度值减1
			if(G.Indegree[G.ToVertex(e)]==0)
			{
				Q.push(G.ToVertex(e));    //入度为0的顶点入队				
			}
		}
	}
	
	cout<<endl;

	for(i=0; i<G.VerticesNum(); i++)
	{ 
      if(G.Mark[i]==UNVISITED)
	  {            
	    cout<<"此图有环！"<<endl;        //图有环
        break;
      }
	}       
if(i=G.VerticesNum())	cout<<"此图无环！"<<endl;        //图有环    
}
void main()
{
	//依用户的选择实现功能
	cout<<"——————第一步：构造图——————"<<endl;
	cout<<"邻接表构造图"<<endl;
	int choice=2;
	int isDirected;                        //标记是否有向图
	int numVertex;                         //图的顶点个数（边数将在setEdge中被自动修改）
	int from,to,weight;                    //读入每条边的起点，终点和权
	ifstream GraphSou;                     //输入文件流
	//文件格式必须正确无误，否则无法工作
	cout<<"请输入构图文件（例如，输入a.txt，然后回车。请确保构图文件是正确的格式，可参见同目录下文件a.txt的格式及说明文件readme.txt）:";
	char filename[20];
	cin>>filename;                         //获取文件名
	
	GraphSou.open(filename);
	GraphSou>>isDirected;                  //是否有向
	if(isDirected!=1&&isDirected!=0)
	{
		cout<<"文件格式不正确，请重新输入。"<<endl;
		return;
	}

	GraphSou>>numVertex;                   //顶点个数
	Graph *myGra;                          //图本身
   	myGra=new Graphl(numVertex);   //因为邻接多重表是通过邻接表来初始化的
	while(!GraphSou.eof())                 //顺次读取边的信息
	{
		GraphSou>>from>>to>>weight;
		if(from>=0&&to>=0&&weight>0&&from<numVertex&&to<numVertex)
		{
			myGra->setEdge(from,to,weight);
			if(!isDirected)
				myGra->setEdge(to,from,weight);
		}
		else
		{
			cout<<"文件数据非法，请重新输入。"<<endl;
			return;
		}
	}	
	cout<<endl;
	//输出图的构造情况以便用户检查
	cout<<"**********你所构造的图具体情况如下：**********"<<endl;
	if(isDirected)
		cout<<"该图为有向图。"<<endl;
	else
		cout<<"该图为无向图。"<<endl;
	cout<<"顶点数——"<<myGra->VerticesNum()<<endl;
	cout<<"存在边如下——"<<endl;
	for(int i=0;i<myGra->VerticesNum();i++)
	{
		for(Edge e=myGra->FirstEdge(i);myGra->IsEdge(e);e=myGra->NextEdge(e))
		{			
			cout<<"始点："<<e.from<<" 终点："<<e.to<<" 权："<<e.weight<<endl;			
		}
		cout<<endl;
	}	
	
	//依据用户的选择来验证各种算法
	cout<<"——————第二步：验证图的算法——————"<<endl;
	choice=3;
		 if(choice==3)
		{
			if(!isDirected)
			{
				cout<<"此图是无向图!"<<endl;
			} 
			else 
			TopsortbyQueue(*myGra);
		} 		
		cout<<"此图是有向无环图！"<<endl; 
		cout<<endl;
}