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

// 无向图的最小支撑树Prim算法的实现//主题：实现最小支撑树的算法 //作者：Andyhou //时间：2008年4月27日 //具体重要算法：// 采用了最小堆来实现取最小边，定义了一个边的类。// Prim算法的具体实现。// 顶点的存储都是从1开始。#include <iostream>using namespace std; const int MaxNode=100;const int VISITED=1;const int UNVISITED=0; 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; }}; //最小值堆的建立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 Prim(int s);}; //最小支撑树的实现void ADJ::Prim(int s){ int MSTtag=1; //最小支撑树边的标号，存储都是从1开始的。 struct Node* temp; Edge* MST=new Edge[NNode]; Edge Ne; MinHeap<Edge> H(e); //最小值堆 for(int i=1;i<=NNode;i++) //初识化标记数组 MARK[i]=UNVISITED; int v=s; MARK[v]=VISITED; //开始顶点首先被标记 do{ //将以v为顶点，另一顶点未被标记的边插入最小值堆H中。 temp=AdjList[v].first; while(temp!=NULL) { if(MARK[temp->adjvex]==UNVISITED) { Ne.from=v; Ne.to=temp->adjvex; Ne.weight=temp->weight; H.Insert(Ne); } temp=temp->next; } //寻找下条权最小的边 bool Found=false; while(!H.empty()) { Ne=H.RemoveMin(); if(MARK[Ne.to]==UNVISITED) { Found=true; break; } } if(!Found) { cout<<"不存在最小支撑树。"<<endl; delete []MST; MST=NULL; return ; } v=Ne.to; MARK[v]=VISITED; //在顶点v的标记位上做已访问的标记。 AddEdgetoMST(Ne,MST,MSTtag++); //将边Ne加到MST中 }while(MSTtag<NNode); //注意是以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; int item; cout<<"输入无向图顶点数和边数：:"; cin>>MaxNode>>E; ADJ T(E,MaxNode); T.CreateAdj(); T.printAll(); cout<<"输入任意无向图的一个点:"; cin>>item; T.Prim(item); return 0;}

博客介绍

正文

无向图的最小支撑树Prim算法的实现2008-04-28 00:45:00

评论