有向图的邻接表的建立和个类算法的实现 -- RocketMan'sRoom-- 编程爱好者博客

// 有向图的邻接表的建立和个类算法的实现//主题：用邻接表的方式实现有向图的一些算法 //作者：侯永华 //时间：2008年4月26日 //内容：具体实现：创建向图的邻接存储方式。打印邻接表的个顶点数据， //建立邻接表 void CreateAdj(); //打印邻接表 //void printAll(); //删除邻接表 //void Del(); //深度优先搜索 //void DFS(int V); //广度优先搜索 //void BFS(int V); //队列实现拓扑排序 //void TopSortQueue(); //递归的拓扑排序 //void TopSortbyDFS(); //void Do_topsort(int V,int *result,int &tag); //Dijkstra算法的实现 //void Dijkstra(int s); //Floyd算法的实现 //void Floyd(Dist** &D); //其中很多用到的辅助的类，堆的方式在程序中都写出来了。用到队列的才用的VC中自带的队列。//任务：测试所有数据的正确性。//注意：本程序没有采用头文件形式，所有的节点存储都是从1开始的。 #include <iostream>#include <queue>using namespace std; const int MaxNode=100;const int VISITED=1;const int UNVISITED=0;const int INFINITY=10000; struct Node{ int adjvex; //边终点节点。 int weight; struct Node *next; //指向下个节点的指针。};class VNode{public: char data; //节点数据 struct Node* first; //第一个节点边 VNode(){} VNode(char Data,struct Node* firstVal) { data=Data; first=firstVal; } VNode(struct Node* firstVal) { first=firstVal; } };//最小值堆的建立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;} //Dijkstra的附加类class Dist{public: int index; int length; int pre; Dist(){} ~Dist(){} bool operator<( const Dist &arg) { return (this->length<arg.length); } bool operator==(const Dist& arg) { return (this->length==arg.length); } bool operator>(const Dist& arg) { return (this->length>arg.length); } bool operator<=(const Dist &arg) { return (this->length<=arg.length); } bool operator>=(const Dist& arg) { return (this->length>=arg.length); }}; class ADJ{private: int e; //边数 VNode *AdjList; //顶点的邻接头 int NNode; //顶点数 int MARK[MaxNode]; //标记数组 int Indegree[MaxNode]; //入度的记数public: ADJ(int itE,int itMaxNode) { e=itE; NNode=itMaxNode; AdjList=new VNode[NNode+1]; //所有的存储数组都是从1开始的。 for(int i=0;i<NNode;i++) { AdjList[i].data=0; AdjList[i].first=NULL; } for(int j=0;j<MaxNode;j++) Indegree[j]=0; } ~ADJ() { delete[] AdjList; } //标记的位的清除 void clearMark() { for(int i=0;i<MaxNode;i++) MARK[i]=0; } //建立邻接表 void CreateAdj(); //打印邻接表 void printAll(); //深度优先搜索 void DFS(int V); //广度优先搜索 void BFS(int V); //队列实现拓扑排序 void TopSortQueue(); //递归的拓扑排序 void TopSortbyDFS(); void Do_topsort(int V,int *result,int &tag); //Dijkstra算法的实现 void Dijkstra(int s); //Floyd算法的实现 void Floyd(Dist** &D); }; //建立邻接表void ADJ::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; //连接下个节点。 Indegree[j]++; //入度记熟。 }} //打印图的所有接点 void ADJ::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 ADJ::DFS(int V){ struct Node* Temp; cout<<AdjList[V].data<<"====>>"; MARK[V]=VISITED; Temp=AdjList[V].first; while(Temp!=NULL) { if(MARK[Temp->adjvex]==UNVISITED) DFS(Temp->adjvex); Temp=Temp->next; }} //广度优先搜索算法的队列实现void ADJ::BFS(int V){ using std::queue; queue<int> Q; struct Node* temp; cout<<AdjList[V].data<<"-->"; MARK[V]=VISITED; Q.push(V); while(!Q.empty()) { int V=Q.front(); Q.pop(); temp=AdjList[V].first; while(temp!=NULL) { if(MARK[temp->adjvex]==UNVISITED) { cout<<AdjList[temp->adjvex].data<<"-->"; MARK[temp->adjvex]=VISITED; Q.push(temp->adjvex); } temp=temp->next; } }} //拓扑排序的队列实现void ADJ::TopSortQueue(){ clearMark(); using std::queue; queue<int> Q; struct Node* temp; for(int i=1;i<=NNode;i++) if(Indegree[i]==0) Q.push(i); while(!Q.empty()) { int V=Q.front(); Q.pop(); cout<<AdjList[V].data<<"-->"; MARK[V]=VISITED; temp=AdjList[V].first; while(temp!=NULL) { Indegree[temp->adjvex]--; if(Indegree[temp->adjvex]==0) Q.push(temp->adjvex); temp=temp->next; } } for(int i=1;i<=NNode;i++) if(MARK[i]==UNVISITED) { cout<<"此图有环！"; break; }}//DFS实现的拓扑排序void ADJ::TopSortbyDFS(){ clearMark(); int *result=new int[NNode]; int tag=1; for(int i=1;i<=NNode;i++) if(MARK[i]==UNVISITED) Do_topsort(i,result,tag); for(int i=NNode;i>=1;i--) cout<<result[i]<<"--->";} void ADJ::Do_topsort(int V,int *result,int &tag){ MARK[V]=VISITED; struct Node *temp=AdjList[V].first; while(temp!=NULL) { if(MARK[temp->adjvex]==UNVISITED) Do_topsort(temp->adjvex,result,tag); temp=temp->next; } result[tag++]=V;}//Dijkstra算法的实现 void ADJ::Dijkstra(int s ){ Dist *D=new Dist[NNode+1]; for(int i=1;i<=NNode;i++) { MARK[i]=UNVISITED; D[i].index=i; D[i].length=INFINITY; D[i].pre=s; } D[s].length=0; MinHeap<Dist> H(NNode); H.Insert(D[s]); for(int i=1;i<=NNode;i++) { bool FOUND=false; Dist d; while(!H.empty()) { d=H.RemoveMin(); if(MARK[d.index]==UNVISITED) { FOUND=true; break; } } if(!FOUND) break; int v=d.index; MARK[v]=VISITED; cout<<AdjList[v].data<<"--->"; struct Node *temp=AdjList[v].first; while(temp!=NULL) { if((D[temp->adjvex].length>(D[v].length+temp->weight))&&MARK[temp->adjvex]==UNVISITED) { D[temp->adjvex].length=D[v].length+temp->weight; D[temp->adjvex].pre=v; H.Insert(D[temp->adjvex]); } temp=temp->next; } } cout<<"输出重新刷新权值号的个顶点的最短路径权值！"; for(int j=1;j<=NNode;j++) cout<<j<<"("<<D[j].length<<") -->";} //Floyd算法的实现 void ADJ:: Floyd(Dist** &D){ int i,j,v; struct Node* temp; D=new Dist*[NNode+1]; for(i=1;i<=NNode;i++) D[i]=new Dist[NNode+1]; for(i=1;i<=NNode;i++) for(j=1;j<=NNode;j++) if(i==j) { D[i][j].length=0; D[i][j].pre=i; } else { D[i][j].length=INFINITY; D[i][j].pre=0; } for(v=1;v<=NNode;v++) { temp=AdjList[v].first; while(temp!=NULL) { D[v][temp->adjvex].length=temp->weight; D[v][temp->adjvex].pre=v; temp=temp->next; } } for(v=1;v<=NNode;v++) for(i=1;i<=NNode;i++) for(j=1;j<=NNode;j++) if(D[i][j].length>(D[i][v].length + D[v][j].length)) { D[i][j].length=D[i][v].length+D[v][j].length; D[i][j].pre=v; } for(i=1;i<=NNode;i++) { //打印前一顶点的矩阵 for(j=1;j<=NNode;j++) cout<<D[i][j].pre<<"\t"; cout<<endl; } cout<<"打印最短路径矩阵："<<endl; for(i=1;i<=NNode;i++) { for(j=1;j<=NNode;j++) cout<<D[i][j].length<<"\t"; cout<<endl; } } void DefineProgram(){ cout<<"-------------------------------------------------------------"<<endl; cout<<"\t0----退出程序不做任何的输出信息:"<<endl; cout<<"\t1----打印所有顶点的信息："<<endl; cout<<"\t2----深度优先搜索顶点："<<endl; cout<<"\t3----广度优先搜索顶点："<<endl; cout<<"\t4----队列实现拓扑排序："<<endl; cout<<"\t5----DFS实现拓扑排序："<<endl; cout<<"\t6----单源的最短路径的实现"<<endl; cout<<"\t7----两顶点间的最短路径："<<endl; cout<<"-------------------------------------------------------------"<<endl; cout<<"请输入你需要的选择项："<<endl; } int main(){ int E,MaxNode; int item,item2; int tag=100; Dist **D; cout<<"输入有向图的顶点数和边数：:"; cin>>MaxNode>>E; ADJ T(E,MaxNode); T.CreateAdj(); DefineProgram(); cin>>tag; while(tag!=0) { switch(tag) { case 1: T.printAll(); cout<<endl; break; case 2: cout<<"输入你要开始的深度优先搜索顶点："; cin>>item; cout<<"输出顶点的深度优先搜索顺序："; T.clearMark(); T.DFS(item); cout<<endl; break; case 3: cout<<"输入你要开始的广度优先搜索顶点："; cin>>item; T.clearMark(); cout<<endl; cout<<"输出顶点的广度优先搜索顺序："; T.BFS(item); cout<<endl; break; case 4: T.clearMark(); cout<<endl; cout<<"输出队列实现的拓扑排序："; T.TopSortQueue(); cout<<endl; break; case 5: cout<<"输出DFS实现的拓扑排序："; T.TopSortbyDFS(); cout<<endl; break; case 6: cout<<"输入一个顶点到其他顶点最近的距离:"; cin>>item2; cout<<endl; cout<<"单源的最短路径"; T.clearMark(); T.Dijkstra(item2); cout<<endl; break; case 7: cout<<"查看两个顶点的最小距离："<<endl; T.Floyd(D); cout<<endl; break; default: cout<<"请重新输入正确数字："<<endl; break; } DefineProgram(); cin>>tag; } return 0;} 注: 此程序在VC2005中运行通过的。

博客介绍

正文

有向图的邻接表的建立和个类算法的实现2008-04-26 15:58:00

评论