//AdjMWGraph.h
#include "SeqList.h" #include "SeqQueue.h"
const int MaxVertices=10; const int MaxWeight=10000; 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; } } }
//GraphLib.h
struct RowColWeight{ int cow; int col; int wieght; }; void CreatGarph(AdjMWGraph &G,DataType V[],int n,RowColWeight E[],int e){ for(int i=0;i<n;i++) G.InsertVertex(V[i]); for(int k=0;k<e;k++) G.InsertEdge(E[k].cow,E[k].col,E[k].wieght); } void Printchar(char item) { cout<<item<<" "; }
//SeqList.h #include<iostream> #include<stdlib.h> using namespace std;
const int MaxListSize=100; 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)const{ 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; }
//SeqQueue.h #include<assert.h> #include<iostream> using namespace std; 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]; }
厉害！
