graphl.h

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

#include"Graph.h"
#include"listUnit.h"
#include"LList.h"
class Graphl:public Graph
{
private:
	LList<listUnit>* graList;
public:
	Graphl(int numVert):Graph(numVertex)
	{
		graList=new LList<listUnit>[numVertex];
	}
	~Graphl()
	{
		delete []graList;
	}
	Edge FirstEdge(int oneVertex)              //返回顶点oneVertex的第一条边
	{
		Edge myEdge;                           //边myEdge将作为函数的返回值
		myEdge.from=oneVertex;                 //将顶点oneVertex作为边myEdge的始点
	
		myEdge.to=-1;
		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;//vertex 边的终点，element 表目数据
			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的始点相同
	
		myEdge.to=-1;
		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)
		{
	
			return myEdge;
		}
		
		else               //边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]++;	
			return;
		}
	}

	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]--;			
		}
	}
};