最小生成树.cpp

KRUSAL算法实现最小生成数的 最小生成数的 最小生成数的

//链表，这个链表除了头定义以外没有任何操作函数，

//链表元素
#define UNVISITED 0
#define VISITED 1
#define INFINITY 9999999
#define ROOT -1
#include <queue>
#include <iostream.h>
#include <fstream.h>
template<class Elem>
class Link
{
public:
	Elem element;      //表目的数据
	Link *next;        //表目指针，指向下一个表目
	Link(const Elem& elemval,Link *nextval=NULL)  //构造函数
	{ element=elemval; next=nextval; }
	Link(Link *nextval=NULL) { next=nextval; }    //构造函数
};

//链表
template<class Elem>
class LList
{
public:
	Link<Elem>* head;  //head指针并不储存任何实际元素，其存在只是为了操作方便
	
	LList()            //构造函数
	{
		head=new Link<Elem>();
	}

	void removeall()        //释放边表所有表目占据的空间
	{
		Link<Elem> *fence;
		while(head!=NULL)   //逐步释放每个表目占据的空间
		{  
			fence=head;
			head=head->next;
			delete fence;
		}
	}

	~LList() { removeall(); } //析构函数
};
//最小堆

//自定义的swap函数
template<class Elem>
swap(Elem A[],int x,int y)
{
	Elem temp=A[x];
	A[x]=A[y];
	A[y]=temp;
}

//最小堆
template <class Elem>
class minheap
{
private:
	Elem *Heap;                         //堆指针
	int size;						    //堆大小
	int n;								//堆中实际元素个数

public:	
	//构造函数，以一个已有的数组为依据	
	minheap(Elem *A,int num,int max)    
	{
		Heap=A;                     //指向已有数组
		n=num;
		size=max;
		buildHeap();
	}

	bool isempty() const
	{
		return n<=0;
	}

	bool isLeaf(int pos)            //判断是否为叶
	{
		return (pos>=n/2)&&(pos<n);
	}
	int leftchild(int pos)          //左儿子
	{
		return 2*pos+1;
	}
	int rightchild(int pos)         //右儿子
	{
		return 2*pos+2;
	}
	int parent(int pos)             //父亲
	{
		return (pos-1)/2;
	}
	void buildHeap()                //建堆，参考siftdown函数
	{
		for(int i=n/2-1;i>=0;i--)
			siftdown(i);
	}
	//该函数将每一个元素放入其在堆中的合适位置
	void siftdown(int pos)
	{
		while(!isLeaf(pos))
		{
			int j=leftchild(pos);
			int rc=rightchild(pos);
			if((rc<n)&&(Heap[j]>Heap[rc]))    //取较小的儿子
				j=rc;
			if(!(Heap[pos]>Heap[j])) return;  //结束
			//比小儿子大，和小儿子交换
			swap(Heap,pos,j);
			pos=j;
		}
	}
	bool insert(Elem &val)
	{
		if(n>=size) return false;
		int curr=n++;               //先将插入的元素放到堆的末尾
		Heap[curr]=val;
		//这其实是一个siftup的过程
		while((curr!=0)&&(Heap[curr]<Heap[parent(curr)]))
		{
			swap(Heap,curr,parent(curr));
			curr=parent(curr);
		}
		return true;
	}
	Elem removemin()               //取最小元素
	{
		swap(Heap,0,--n);          //先将最小元素放到堆的末尾
		if(n!=0) siftdown(0);      //重建堆
		return Heap[n];
	}
	//取任何一个元素，比上面的函数多一个siftup的过程，注意siftup和siftdown两个过程只执行其中的一个
	bool remove(int pos,Elem &it)  
	{
		if((pos<0)||(pos>=n)) return false;
		swap(Heap,pos,--n);
		while(pos!=0&&(Heap[pos]<Heap[parent(pos)]))
		{
			swap(Heap,pos,parent(pos));
			pos=parent(pos);
		}
		//siftdown(pos);
		it=Heap[n];
		return true;
	}
};

//数据结构部分:

/**************** 图的边的定义 ***************/
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;
};


/**************** 相邻矩阵方式实现的图 ***************/
class Graphm: public Graph   
{
private:
	int **matrix;           //指向相邻矩阵的指针
	
public:
	
	Graphm(int numVert):Graph(numVert)    //构造函数
	{
		int i,j;                          //i,j仅仅作为for循环中的计数器		

		matrix=(int**)new int*[numVertex];     //申请matrix数组,该数组有numVertex个元素,每个元素是整型指针类型
		for(i=0;i<numVertex;i++)               //matrix数组的每个元素,都指向一个具有numVertex个元素的数组
			matrix[i] = new int[numVertex];
		for(i=0;i<numVertex;i++)               //相邻矩阵的所有元素都初始化为0,如果矩阵元素matrix[i][j]不为0,则表明顶点i与顶点j之间有一条边,边的权即为matrix[i][j]的值
			for(j=0;j<numVertex;j++)
				matrix[i][j]=0;
	}

	~Graphm()                        //析构函数
	{
		for(int i=0;i<numVertex;i++) //释放每个matrix[i]申请的空间
			delete [] matrix[i];
		delete [] matrix;            //释放matrix指针指向的空间
	}

	Edge FirstEdge(int oneVertex)    //返回顶点oneVertex的第一条边
	{
		Edge myEdge;                 //边myEdge将作为函数的返回值
		myEdge.from=oneVertex;       //将顶点oneVertex作为边myEdge的始点
		for(int i=0;i<numVertex;i++) //寻找第一个使得matrix[oneVertex][i]不为0的i值,那么(oneVertex,i)或者<oneVertex,i>即为顶点oneVertex的第一条边
		{
			if(matrix[oneVertex][i]!=0)
			{
				myEdge.to=i;         //将顶点i作为边myEdge的终点
				myEdge.weight=matrix[oneVertex][i];   //边myEdge的权为矩阵元素matrix[oneVertex][i]的值
				break;
			}			
		}
		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的始点相同
	   
		for(int i=preEdge.to+1;i<numVertex;i++) //寻找下一个使得matrix[preEdge.from][i]不为0的i值,那么(preEdge.from,i)或者<preEdge.from,i>即为顶点preEdge.from的下一条边
		{
			if(matrix[preEdge.from][i]!=0)
			{
				myEdge.to=i;
				myEdge.weight=matrix[preEdge.from][i];
				break;
			}
		}
		
		return myEdge;                //如果找到了顶点preEdge.from的下一条边,则返回的myEdge确实是一条边;如果没有找到顶点preEdge.from的下一条边,则myEdge的成员变量to为-1,根据IsEdge函数判断可知myEdge不是一条边
	}

	void setEdge(int from,int to,int weight)      //为图设定一条边
	{
		if(matrix[from][to]==0)                   //如果matrix[from][to]==0，则边(from,to)或者<from,to>将是新增的一条边，否则该边已经存在（现在只是对该边进行修改）
		{
			numEdge++;
			Indegree[to]++;
		}
		matrix[from][to]=weight;  		      
	}

	void delEdge(int from,int to)               //删掉图的一条边
	{
		if(matrix[from][to]!=0)					//如果matrix[from][to]!=0，则边(from,to)或者<from,to>确实存在，否则该边实际上并不存在（从而不必对图的边数和顶点to的入度进行修改）
		{
			numEdge--;
			Indegree[to]--;
		}
		matrix[from][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 DFS(Graph& G, int V)
{
	G.Mark[V]= VISITED;                           //标记该点
	cout<<V<<"\t";								  //打印
	for(Edge e=G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e))  //由该点所连的边进行深度优先周游
	{
	
		if(G.Mark[G.ToVertex(e)]==UNVISITED)               //访问V邻接到的未被访问过的顶点，并递归地按照深度优先的方式进行周游
			DFS(G, G.ToVertex(e));	
	}
}

//广度优先周游（从一个点开始周游）：
void BFS(Graph& G, int V)
{
	using std::queue;
	queue<int> Q;                   //初始化广度优先周游要用到的队列
	
	G.Mark[V]= VISITED;             //访问顶点V，并标记其标志位