数据结构DFS、BFS算法、Prim算法、Kruskal算法、Dijstra算法、Floyd算法

/**************************************** 定义采用邻接矩阵存储的图结构 封装DFS、BFS算法、Prim算法、Kruskal算法、Dijstra算法、Floyd算法 ****************************************************/ #include <iostream> #include <math.h> #include <limits.h> #include <Queue> #define UNVISITED 1; #define VISITED 0; using namespace std; template <class T> class MinHeap { private: T * heapArray; int CurrentSize; int MaxSize; void BuildHeap() { for(int i=CurrentSize/2-1;i>0;i--) SiftDown(i); } public: MinHeap(const int n) { if (n<=0) return; CurrentSize=0; MaxSize=n; heapArray=new T [MaxSize]; BuildHeap(); } ~MinHeap() { delete []heapArray; } bool isLeaf(int pos) { return((pos>=CurrentSize/2)&&(pos<CurrentSize)); } int leftChild(int pos)const { return 2*pos+1; } int rightChild(int pos)const { return 2*pos+2; } int parent(int pos)const { return (pos-1)/2; } bool Remove(int pos)//, T& node)//删除指定下标的元素 { if ((pos < 0) || (pos >= CurrentSize)) return false; heapArray[pos] = heapArray[- -CurrentSize]; // 用最后的元素值替代删除位置的元素 if (heapArray[parent(pos)] > heapArray[pos]) SiftUp(pos); // 当前元素小于父结点，需要上升调整 else SiftDown(pos); // 当前元素大于父结点，向下筛 return true; } bool Insert(const T & newNode) { if (CurrentSize == MaxSize) return false; // 堆空间已经满 heapArray[CurrentSize] = newNode; SiftUp(CurrentSize); // 向上调整 CurrentSize++; return true; } T RemoveMin() { T item; if (CurrentSize == 0) { cout<< "Can't Delete"; } else { item=heapArray[0]; heapArray[0]=heapArray[CurrentSize-1]; heapArray[--CurrentSize]=item; if (CurrentSize>1) SiftDown(0); } return item; } void SiftUp(int pos) { int tempposition=pos; T temp=heapArray[tempposition]; while((tempposition>0)&&(heapArray[parent(tempposition)]>temp)) { heapArray[tempposition]=heapArray[parent(tempposition)]; tempposition=parent(tempposition); } heapArray[tempposition]=temp; } void SiftDown(int pos) { int i=pos; int j=leftChild(i); T temp=heapArray[i]; while(j<CurrentSize) { if((j<CurrentSize-1)&&heapArray[j]>heapArray[j+1]) j++; if(temp>heapArray[j]) { heapArray[i]=heapArray[j]; i=j; j=leftChild(j); } else break; } heapArray[i]=temp; } void print() { for(int i=0;i<CurrentSize;i++) { cout<<heapArray[i]<<' '; } cout<<endl; } bool IsEmpty() { return CurrentSize==0; } }; class Edge { public: int from; int to; int weight; Edge() { from=to=-1; weight=0; } Edge(int st,int en, int w) { from=st; to=en; weight=w; } bool operator >(Edge oneEdge) { return weight>oneEdge.weight; } bool operator <(Edge oneEdge) { return weight<oneEdge.weight; } }; class Graph { public: int numVertex;//图的顶点个数 int numEdge;//图的边的数目 int *Mark;//保存有图的顶点是否被访问过的数组 int *Indegree;//保存有图的顶点的入度的数组 Graph(int verticesNum) { numVertex=verticesNum; numEdge=0; Mark=new int [numVertex]; Indegree=new int [numVertex]; for(int i=0;i<numVertex;i++) { Mark[i]=UNVISITED; Indegree[i]=0; } } ~Graph() { delete [] Mark; delete [] Indegree; } virtual Edge FirstEdge(int oneVertex)=0;//返回与顶点关联的第一条边 virtual Edge NextEdge(Edge oneEdge)=0; virtual void setEdge(int from,int to,int weight)=0; virtual void delEdge(int from,int to)=0; void visit(int i) { cout<<i+1<<' '; } int VerticesNum() { return numVertex; } int EdgesNum() { return numEdge; } bool IsEdge(Edge oneEdge) { if((oneEdge.weight > 0)&&(oneEdge.weight < INT_MAX)&&(oneEdge.to >= 0))return true; else return false; } int FromVertex(Edge oneEdge) { return oneEdge.from; } int ToVertex(Edge oneEdge) { return oneEdge.to; } int Weight(Edge oneEdge) { return oneEdge.weight; } void GDFS(int v) { Mark[v]=VISITED; visit(v); for(Edge e=FirstEdge(v);IsEdge(e);e=NextEdge(e)) { if(Mark[ToVertex(e)]==1) GDFS(ToVertex(e)); } } void DFSTraverse() { cout<<"深度优先搜索DFS："<<endl; for(int i=0;i<VerticesNum();i++) { Mark[i]=1; } for(int r=0;r<VerticesNum();r++) { if(Mark[r]==1) GDFS(r); } cout<<endl; } void GBFS(int v) { queue<int> Q; Mark[v]=0; visit(v); Q.push(v); while(!Q.empty()) { v = Q.front(); Q.pop(); for(Edge e = FirstEdge(v);IsEdge(e); e = NextEdge(e)) { if(Mark[ToVertex(e)] == 1) { visit(ToVertex(e)); Mark[ToVertex(e)] = 0; Q.push(ToVertex(e)); } } } } void BFSTraverse() { cout<<endl<<"广度优先搜索BFS："<<endl; int i=0; for(i=0;i<VerticesNum();i++) { Mark[i] = 1; } for(i=0;i<VerticesNum();i++) { if(Mark[i] == 1) GBFS(i); } cout<<endl; } int StartVertex(Edge oneEdge){//返回边的始点 return oneEdge.from; } int EndVertex(Edge oneEdge){//返回边的终点 return oneEdge.to; } }; class AdjGraph : public Graph { private: int **matrix; public: AdjGraph(int verticesNum):Graph(verticesNum) { int i,j; matrix=(int **)new int *[numVertex]; for(i=0;i<numVertex;i++) matrix[i]=new int [numVertex]; for(i=0;i<numVertex;i++) for(j=0;j<numVertex;j++) matrix[i][j]=0; } ~AdjGraph() { for(int i=0;i<numVertex;i++) delete[]matrix[i]; delete []matrix; } Edge FirstEdge(int oneVertex) { Edge myEdge; myEdge.from=oneVertex; myEdge.to=-1; for(int i=0;i<numVertex;i++) { if(matrix[oneVertex][i]!=0) { myEdge.to=i; myEdge.weight=matrix[oneVertex][i]; break; } } return myEdge; } Edge NextEdge(Edge preEdge) { Edge myEdge; myEdge.from=preEdge.from; myEdge.to=-1; for(int i=preEdge.to+1;i<numVertex;i++) { if(matrix[preEdge.from][i]!=0) { myEdge.to=i; myEdge.weight=matrix[preEdge.from][i]; break; } } return myEdge; } void setEdge(int from,int to,int weight) { if(matrix[from][to]<=0) { numEdge++; Indegree[to]++; } mat