无向图的最小支撑树Kruskal算法的实现 -- RocketMan'sRoom-- 编程爱好者博客

// 无向图的最小支撑树Kruskal算法的实现//主题：用邻接表的方式实现最小支撑树Kruskal算法 //作者：Andyhou //时间：2008年4月28日 //具体算法实现：// 采用的是最小堆的方式找最小边，用等价类的方式步步合并最小的边。// 程序中还声明了一个等价类。#include <iostream>using namespace std; const int MaxNode=100;const int VISITED=1;const int UNVISITED=0;const int ROOT=-1;const int INFINITY=9999; struct Node{ int adjvex; //终点顶点 int weight; //权 struct Node *next; //指向下个顶点的指针};class VNode{public: int data; struct Node* first; //指向第一个邻接顶点 VNode(){} VNode(int Data,struct Node* firstVal) { data=Data; first=firstVal; } VNode(struct Node* firstVal) { first=firstVal; } };//用于最小支撑树的边类class Edge{public: int 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; } bool operator==(Edge oneEdge) { return weight==oneEdge.weight; }}; //用于”父指针"发表示等价类的类class Gentree{private: int *Array; int size;public: Gentree(int sz) { size=sz; Array=new int[sz+1]; for(int i=1;i<=sz;i++) Array[i]=ROOT; //整个数的根节点 } ~Gentree() { delete[] Array; } int FIND(int curr) //寻找根的函数 { while(Array[curr]!=ROOT) curr=Array[curr]; return curr; } void UNION(int a,int b) //将a和b合并到一个等价类中，a和b在一个等价类中就他们相同的根。 { int root1=FIND(a); int root2=FIND(b); if(root1!=root2) Array[root2]=root1; } bool differ(int a,int b) //判断a和b是否等价。 { int root1=FIND(a); int root2=FIND(b); return root1!=root2; }}; //最小值堆的建立template <class T>class MinHeap {private: T* heapArray; int CurrentSize; int MaxSize; public: MinHeap(const int n); virtual ~MinHeap() {delete []heapArray;}; void BuildHeap(); bool isLeaf(int pos) const; int leftchild(int pos) const; int rightchild(int pos) const; // Return parent position int parent(int pos) const; // 删除给定下标的元素 bool Remove(int pos, T& node); void SiftDown(int left); //从position向上开始调整，使序列成为堆 void SiftUp(int position); bool Insert(const T& newNode); T& RemoveMin(); bool empty() { if(CurrentSize>0) return false; else return true; }}; template<class T>MinHeap<T>::MinHeap(const int n){ if(n<=0) return; CurrentSize=0; MaxSize=n; heapArray=new T[MaxSize]; BuildHeap();} template<class T>void MinHeap<T>::BuildHeap(){ for (int i=CurrentSize/2-1; i>=0; i--) SiftDown(i); } template<class T>bool MinHeap<T>::isLeaf(int pos) const{ return (pos>=CurrentSize/2)&&(pos<CurrentSize);} template<class T>int MinHeap<T>::leftchild(int pos) const{ return 2*pos+1; //返回左孩子位置} template<class T>int MinHeap<T>::rightchild(int pos) const{ return 2*pos+2; //返回右孩子位置} template<class T>int MinHeap<T>::parent(int pos) const // 返回父节点位置{ return (pos-1)/2;} template<class T>void MinHeap<T>::SiftDown(int left){ //准备 int i=left; //标识父结点 int j=2*i+1; //标识关键值较小的子结点 T temp=heapArray[i]; //保存父结点 //过筛 while(j<CurrentSize) { if((j<CurrentSize-1)&&(heapArray[j]>heapArray[j+1])) j++; //j指向右子结点 if(temp>heapArray[j]) { heapArray[i]=heapArray[j]; i=j; j=2*j+1; } else break; } heapArray[i]=temp;} template<class T>void MinHeap<T>::SiftUp(int position) {//从position向上开始调整，使序列成为堆 int temppos=position; T temp=heapArray[temppos]; while((temppos>0)&&(heapArray[parent(temppos)]>temp)) { heapArray[temppos]=heapArray[parent(temppos)]; temppos=parent(temppos); } heapArray[temppos]=temp;} template<class T>bool MinHeap<T>::Insert(const T& newNode){//向堆中插入一个结点 if(CurrentSize==MaxSize) return false; heapArray[CurrentSize]=newNode; SiftUp(CurrentSize); CurrentSize++; return true;} template<class T>T& MinHeap<T>::RemoveMin(){ if(CurrentSize==0) { cout<<"Can't Delete"; } else { T temp=heapArray[0]; //取堆顶元素 heapArray[0]=heapArray[CurrentSize-1]; //堆末元素上升至堆顶 CurrentSize--; if(CurrentSize>1) SiftDown(0); //从堆顶开始筛选 return temp; }} template<class T>bool MinHeap<T>::Remove(int pos, T& node){// 删除给定下标的元素 if((pos<0)||(pos>=CurrentSize)) return false; T temp=heapArray[pos]; heapArray[pos]=heapArray[--CurrentSize]; //指定元素置于最后 SiftUp(pos); //上升筛 SiftDown(pos); //向下筛 node=temp; return true;} class ADJ{private: int e; //边数 VNode *AdjList; //邻接表 int NNode; //顶点数 int MARK[MaxNode]; //访问标记数组public: ADJ(int itE,int itMaxNode) { e=itE; NNode=itMaxNode; AdjList=new VNode[NNode+1]; for(int i=0;i<NNode;i++) { AdjList[i].data=0; AdjList[i].first=NULL; } } ~ADJ() { delete[] AdjList; } void CreateAdj() { int i,j; int item; struct Node* S; for(int a=1;a<=NNode;a++) { cout<<"输入第"<<a<<"个顶点数据"; cin>>AdjList[a].data; AdjList[a].first=NULL; } for(int k=0;k<e;k++) { cout<<"输入边<Vi,Vj>的顶点对序列号："; cin>>i; cin>>j; cout<<"输入边的权："; cin>>item; S=new struct Node(); S->adjvex=j; S->weight=item; S->next=AdjList[i].first; AdjList[i].first=S; //连接两个顶点 S=new struct Node(); S->adjvex=i; S->weight=item; S->next=AdjList[j].first; AdjList[j].first=S; } } void printAll() { cout<<"打印所有顶点的连接情况;"<<endl; for(int i=1;i<=NNode;i++) { struct Node* temp=AdjList[i].first; cout<<i; cout<<"("<<AdjList[i].data<<")"; if(temp!=NULL) cout<<"---"<<temp->weight<<"-->"; while(temp!=NULL) { cout<<temp->adjvex; cout<<"("<<AdjList[temp->adjvex].data<<")"<<"--"<<temp->weight<<"-->"; temp=temp->next; } cout<<"---->NULL"; cout<<endl; } cout<<"输出了所有数据！"<<endl; } void AddEdgetoMST(Edge &E,Edge *MST,int tag) { MST[tag].from=E.from; MST[tag].to=E.to; MST[tag].weight=E.weight; } void Krushal(); };void ADJ::Krushal(){ Gentree A(NNode); //等价类 MinHeap<Edge> H(e); //最小值堆 struct Node *temp; Edge * MST=new Edge[NNode-1]; //最小支撑树 int MSTtag=1; //最小支撑树的边的标记 Edge Ne; for(int i=1;i<=NNode;i++) //将图的所有边插入最小值堆H中 { temp=AdjList[i].first; while(temp!=NULL) { if(i<temp->adjvex) //因为是无向图，所有应防止重复插入 { Ne.from=i; Ne.to=temp->adjvex; Ne.weight=temp->weight; H.Insert(Ne); } temp=temp->next; } } int EquNum=NNode; //开始有|V|个等价类 while(EquNum>1) //合并等价类 { Ne=H.RemoveMin(); //获得下一条权最小的边 if(Ne.weight==INFINITY) { cout<<"不存在最小支撑树:"; delete[] MST; MST=NULL; return ; } int from=Ne.from; //纪录该条边的信息 int to=Ne.to; if(A.differ(from,to)) //如果边Ne的两个顶点不在一个等价类 { A.UNION(from,to); //将边Ne的连个顶点在的两个等价类合并为一个 AddEdgetoMST(Ne,MST,MSTtag++); //将边e加到MST EquNum--; //将等价类的个数减1 } } cout<<"输出无向图的最小支撑树的边和权："; for(int i=1;i<NNode;i++) cout<<MST[i].from<<"--"<<MST[i].to<<"("<<MST[i].weight<<")\t"; cout<<endl;} int main(){ int E,MaxNode; cout<<"输入无向图的顶点数和边数：:"; cin>>MaxNode>>E; ADJ T(E,MaxNode); T.CreateAdj(); T.printAll(); cout<<endl; cout<<"Kruskal算法的执行："<<endl; T.Krushal(); return 0;}

博客介绍

正文

无向图的最小支撑树Kruskal算法的实现2008-04-28 01:26:00

评论