数据结构最短路径(c++)

#include "SeqList.h" #include "SeqQueue.h" #include<assert.h> #include<iostream> using namespace std; #include<iostream> #include<stdlib.h> using namespace std; const int MaxVertices=10; const int MaxWeight=10000; const int MaxListSize=1000; class AdjMWGraph { private: SeqList Vertices; int Edge[MaxVertices][MaxVertices]; int numOfEdges; public: AdjMWGraph(const int sz=MaxVertices); int GarphEmpty()const { return Vertices.ListEmpty(); } int NumOfVertices(void) { return Vertices.ListSize(); } int NumOfEdges(void) { return numOfEdges; } VerT GetValue(const int i); int GetWeight(const int v1,const int v2); void InsertVertex(const VerT &vertex); void InsertEdge(const int v1,const int v2,int weight); void DeleteVertex(const int i); void DeleteEdge(const int v1,const int v2); int GetFirstNeighbor(const int v); int GetNextNeighbor(const int v1,const int v2); void DepthFirstSearch(const int v,int visited[],void vist(VerT item)); void BroadFirstSearch(const int v1,int visited[],void visit(VerT item)); void DepthFirstSearch(void visit(VerT item)); void BroadFirstSearch(void vist(VerT item)); }; AdjMWGraph::AdjMWGraph(const int sz) { for(int i=0;i<sz;i++) for(int j=0;j<sz;j++) { if(i==j)Edge[i][j]=0; else Edge[i][j]=MaxWeight; } numOfEdges=0; } VerT AdjMWGraph::GetValue(const int i) { if(i<0||i>Vertices.ListSize()) { cerr<<"参数i越界出错!"<<endl; exit(1); } return Vertices.GetData(i); } int AdjMWGraph::GetWeight(const int v1,const int v2) { if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize()) { exit(1); } return Edge[v1][v2]; } void AdjMWGraph::InsertVertex(const VerT &vertex) { Vertices.Insert(vertex,Vertices.ListSize()); } void AdjMWGraph::InsertEdge(const int v1,const int v2,int weight) { if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize()) { exit(1); } Edge[v1][v2]=weight; numOfEdges++; } void AdjMWGraph::DeleteVertex(const int v) { for(int i=0;i<Vertices.ListSize();i++) for(int j=0;j<Vertices.ListSize();j++) if((i==v||j==v)&&Edge[i][j]>0&&Edge[i][j]<MaxWeight) { Edge[i][j]=MaxWeight; numOfEdges--; } Vertices.Delete(v); } void AdjMWGraph::DeleteEdge(const int v1,const int v2) { if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize()) exit(1); Edge[v1][v2]=MaxWeight; numOfEdges--; } int AdjMWGraph::GetFirstNeighbor(const int v) { if(v<0||v>Vertices.ListSize()) exit(1); for(int col=0;col<Vertices.ListSize();col++) if(Edge[v][col]>0&&Edge[v][col]<MaxWeight) return col; return -1; } int AdjMWGraph::GetNextNeighbor(const int v1,const int v2) { if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize()) exit(1); for(int col=v2+1;col<Vertices.ListSize();col++) if(Edge[v1][col]>0&&Edge[v1][col]<MaxWeight) return col; return -1; } void AdjMWGraph::DepthFirstSearch(const int v,int visited[],void visit(VerT item)) { visit(GetValue(v)); visited[v]=1; int w=GetFirstNeighbor(v); while(w!=-1) { if(!visited[w]) DepthFirstSearch(w,visited,visit); w=GetNextNeighbor(v,w); } } void AdjMWGraph::BroadFirstSearch(const int v,int visited[],void visit(VerT item)) { int u; int w; SeqQueue queue; visit(GetValue(v)); visited[v]=1; queue.EnQue(v); while(!queue.IsEmpty()) { u=queue.DeQue(); w=GetFirstNeighbor(v); while(w!=-1) { if(!visited[w]) { visit(GetValue(w)); visited[w]=1; queue.EnQue(w); } w=GetNextNeighbor(u,w); } } } void AdjMWGraph::DepthFirstSearch(void visit(VerT item)) { int *visited=new int[NumOfVertices()]; for(int i=0;i<NumOfVertices();i++) visited[i]=0; for(int i=0;i<NumOfVertices();i++) if(!visited[i]) DepthFirstSearch(i,visited,visit); delete []visited; } void AdjMWGraph::BroadFirstSearch(void visit(VerT item)) { int *visited=new int[NumOfVertices()]; for(int i=0;i<NumOfVertices();i++) visited[i]=0; for(int i=0;i<NumOfVertices();i++) if(!visited[i]) BroadFirstSearch(i,visited,visit); delete []visited; } //Dijkstra.h void Dijkstra(AdjMWGraph &G,int v0,int distance[],int path[]) { int n=G.NumOfVertices(); int *s=new int[n]; int minDis,i,j,u; for(i=0;i<n;i++) { distance[i]=G.GetWeight(v0,i); s[i]=0; if(i!=v0&&distance[i]<MaxWeight) path[i]=v0; else path[i]=-1; } s[v0]=1; for(i=1;i<n;i++) { minDis=MaxWeight; for(j=0;j<n;j++) if(s[j]==0&&distance[j]<minDis) { u=j; minDis=distance[j]; } if(minDis==MaxWeight) return; s[u]=1; for(j=0;j<n;j++) if(s[j]==0&&G.GetWeight(u,j)<MaxWeight&&distance[u]+G.GetWeight(u,j)<distance[j]){ distance[j]=distance[u]+G.GetWeight(u,j); path[j]=u; } } } class SeqList { // DataType data[MaxListSize]; int size; public: SeqList(void); ~SeqList(void); int ListSize(void)const; int ListEmpty(void)const; // int Find(DataType &item); // DataType GetData(int pos)const; // void Insert(const DataType &item,int pos); // DataType Delete(const int pos); void ClearList(void); }; SeqList::SeqList(void):size(0){} SeqList::~SeqList(void){} int SeqList::ListSize(void)const { return size; } int SeqList::ListEmpty(void)const { if(size==0) return 1; else return 0; } /*int SeqList::Find(DataType &item) { if(size==0) return -1; int i=0; while(i<size&&item!=data[i])i++; return i; }*/ DataType SeqList::GetData(int pos) { if(pos<0||pos>size-1) { cerr<<"参数pos越界!"<<endl; exit(1); } return data[pos]; } void SeqList::Insert(const DataType &item,int pos) { if(pos<0||pos>size) { cerr<<"参数越界!"<<endl; exit(1); } if(size==MaxListSize-1) { cerr<<"顺序表已经满!"<<endl; exit(1); } for(int i=size;i>pos;i--) data[i]=data[i-1]; data[pos]=item; size++; } DataType SeqList::Delete(const int pos) { if(size==0) { cerr<<"顺序表已空无元素可删!"<<endl; exit(1); } if(pos<0||pos>size-1) { cerr<<"参数越界!"<<endl; exit(1); } DataType temp=data[pos]; for(int i=pos;i<size-1;i++) data[i]=data[i+1]; size--; return temp; } void SeqList::ClearList() { size=0; } class SeqQueue{ int rear,front; DataType *element; int maxsize; public: SeqQueue(){rear=front=0;element=new char[100];} SeqQueue(int ms); ~SeqQueue(){delete []element;} bool IsEmpty()const{return rear==front;} bool IsFull()const{return (rear+1)%maxsize==front;} int Length()const{return (rear-front+maxsize)%maxsize;} void EnQue(const &data); DataType DeQue(); DataType GetNum(); }; SeqQueue::SeqQueue(int ms) { maxsize=ms; element=new char[maxsize]; rear=front=0; assert(element!=NULL); } void SeqQueue::EnQue(const &data) { assert(!IsFull()); rear=(rear+1)%maxsize; element[rear]=data; } DataType SeqQueue::DeQue() { assert(!IsEmpty()); front=(front+1)%maxsize; return element[front]; } DataType SeqQueue::GetNum() { assert(!IsEmpty()); front=(front+1)%maxsize; return element[front];