直接上代码：代码里面有注释

#pragmaonce#include<assert.h>#include<queue>#include"Heap.hpp"#include"UnionFindSet.hpp"////临接矩阵表示无向图&有向图//template<classV,classW>classGraphMatrix{public:GraphMatrix(constV*vertexs,intsize,boolisDirected):_vertexSize(size),_isDirected(isDirected){//开辟矩阵和边集_matrix=newW*[_vertexSize];_vertexs=newV[_vertexSize];for(inti=0;i<_vertexSize;++i){//初始化矩阵_matrix[i]=newW[_vertexSize];memset(_matrix[i],0,sizeof(W)*_vertexSize);//初始化边集_vertexs[i]=vertexs[i];}}intGetVertexIndex(constV&vtx){for(inti=0;i<_vertexSize;++i){if(_vertexs[i]==vtx){returni;}}return-1;}voidAddEdge(constV&src,constV&dst,constW&weight){intsrcIndex=GetVertexIndex(src);intdstIndex=GetVertexIndex(dst);assert(srcIndex!=-1);assert(dstIndex!=-1);if(_isDirected){_matrix[srcIndex][dstIndex]=weight;}else{_matrix[srcIndex][dstIndex]=weight;_matrix[dstIndex][srcIndex]=weight;}}voidDisplay(){for(inti=0;i<_vertexSize;++i){cout<<_vertexs[i]<<"";}cout<<endl<<endl;for(inti=0;i<_vertexSize;++i){for(intj=0;j<_vertexSize;++j){cout<<_matrix[i][j]<<"";}cout<<endl;}cout<<endl;}private:W**_matrix;//临接矩阵V*_vertexs;//顶点集int_vertexSize;//顶点数//int_edgeSize;//边条数bool_isDirected;};//无向图voidTest1(){GraphMatrix<char,int>g("ABCDE",5,false);g.AddEdge('A','D',10);g.AddEdge('A','E',20);g.AddEdge('B','C',10);g.AddEdge('B','D',20);g.AddEdge('B','E',30);g.AddEdge('C','E',40);g.Display();}//有向图voidTest2(){GraphMatrix<char,int>g("ABCDE",5,true);g.AddEdge('A','D',10);g.AddEdge('E','A',20);g.AddEdge('B','C',10);g.AddEdge('D','B',20);g.AddEdge('E','B',30);g.AddEdge('C','E',40);g.Display();}////临接表//template<classV,classW>structLinkEdge{int_srcIndex;//源顶点下标int_dstIndex;//目标顶点下标W_weight;//权重LinkEdge<V,W>*_next;//指向下一个节点的指针LinkEdge(intsrcIndex=-1,intdstIndex=-1,constW&weight=W()):_srcIndex(srcIndex),_dstIndex(dstIndex),_weight(weight),_next(NULL){}};template<classV,classW>structCompareLinkEdge{booloperator()(LinkEdge<V,W>*lhs,LinkEdge<V,W>*rhs){returnlhs->_weight<rhs->_weight;}};template<classV,classW>classGraphLink{protected:vector<V>_vertexs;//顶点集合vector<LinkEdge<V,W>*>_linkTables;//临接表bool_isDirected;//是否是有向图public:GraphLink(boolisDirected=false):_isDirected(isDirected){}GraphLink(constV*ar,intsize,boolisDirected=false):_isDirected(isDirected){_vertexs.resize(size);_linkTables.resize(size);for(size_ti=0;i<size;++i){_vertexs[i]=ar[i];}}public:intGetVertexIndex(constV&vertex){for(inti=0;i<_vertexs.size();++i){if(_vertexs[i]==vertex)returni;}return-1;}void_AddEdge(intsrcIndex,intdstIndex,constW&weight){LinkEdge<V,W>*tmp=newLinkEdge<V,W>(srcIndex,dstIndex,weight);tmp->_next=_linkTables[srcIndex];_linkTables[srcIndex]=tmp;}voidAddEdge(constV&src,constV&dst,constW&weight){intsrcIndex=GetVertexIndex(src);intdstIndex=GetVertexIndex(dst);assert(srcIndex!=-1);assert(dstIndex!=-1);//无向图if(_isDirected){_AddEdge(srcIndex,dstIndex,weight);}else{_AddEdge(srcIndex,dstIndex,weight);_AddEdge(dstIndex,srcIndex,weight);}}voidDisplay(){for(inti=0;i<_vertexs.size();++i){cout<<_vertexs[i]<<"["<<i<<"]->";LinkEdge<V,W>*begin=_linkTables[0];while(begin){cout<<begin->_weight<<"["<<begin->_dstIndex<<"]""->";begin=begin->_next;}cout<<"NULL"<<endl;}cout<<endl;}//获取临接表里的下一条边LinkEdge<V,W>*_GetNextEdge(intsrc,intcur){LinkEdge<V,W>*edge=_linkTables[src];while(edge){if(edge->_dstIndex==cur){returnedge->_next;}edge=edge->_next;}returnNULL;}voidDFS(){cout<<"DFS:";bool*visited=newbool[_vertexs.size()];memset(visited,false,sizeof(bool)*_vertexs.size());for(size_ti=0;i<_vertexs.size();++i){if(visited[i]==false){//1.访问当前节点cout<<_vertexs[i]<<"";visited[i]=true;_DFS(i,visited);}}delete[]visited;cout<<endl;}void_DFS(intsrc,bool*visited){//2.获取当前临接表的第一个顶点LinkEdge<V,W>*edge=_linkTables[src];//3.依次获取临接表后面的顶点进行深度优先遍历while(edge){if(visited[edge->_dstIndex]==false){cout<<_vertexs[edge->_dstIndex]<<"";visited[edge->_dstIndex]=true;_DFS(edge->_dstIndex,visited);}edge=edge->_next;}}voidBFS(){cout<<"BFS:";bool*visited=newbool[_vertexs.size()];memset(visited,false,sizeof(bool)*_vertexs.size());for(size_ti=0;i<_vertexs.size();++i){if(visited[i]==false){_BFS(i,visited);}}delete[]visited;cout<<endl;}void_BFS(intcur,bool*visited){cout<<_vertexs[cur]<<"";visited[cur]=true;queue<int>q;q.push(cur);while(!q.empty()){cur=q.front();q.pop();LinkEdge<V,W>*edge=_linkTables[cur];while(edge){if(visited[edge->_dstIndex]==false){cout<<_vertexs[edge->_dstIndex]<<"";visited[edge->_dstIndex]=true;q.push(edge->_dstIndex);}edge=edge->_next;}}}boolKruskal(GraphLink&minSpanTree){//1.初始化最小生成树minSpanTree._vertexs=_vertexs;minSpanTree._linkTables.resize(_vertexs.size());minSpanTree._isDirected=_isDirected;////2.将所有的边放到一个最小堆//假设有V个顶点，E条边//Heap<LinkEdge<V,W>*,CompareLinkEdge<V,W>>minHeap;for(inti=0;i<_vertexs.size();++i){LinkEdge<V,W>*begin=_linkTables[i];while(begin){//无向图的边需要进行过滤if(begin->_srcIndex<begin->_dstIndex){minHeap.Push(begin);}begin=begin->_next;}}//3.使用并差集和最小堆构建最小生成树UnionFindSetUFSet(_vertexs.size());intcount=_vertexs.size();while(--count){if(minHeap.Empty()){returnfalse;}LinkEdge<V,W>*edge=minHeap.Top();minHeap.Pop();intsrc=UFSet.FindRoot(edge->_srcIndex);intdst=UFSet.FindRoot(edge->_dstIndex);if(src!=dst){UFSet.Union(src,dst);minSpanTree._AddEdge(edge->_srcIndex,edge->_dstIndex,edge->_weight);}}returntrue;}boolPrim(GraphLink&minSpanTree){//1.初始化最小生成树minSpanTree._vertexs=_vertexs;minSpanTree._linkTables.resize(_vertexs.size());minSpanTree._isDirected=_isDirected;bool*visitedSet=newbool[_vertexs.size()];memset(visitedSet,false,sizeof(bool)*_vertexs.size());intsrc=0;visitedSet[src]=true;Heap<LinkEdge<V,W>*,CompareLinkEdge<V,W>>minHeap;intcount=1;do{//2.取出一个顶点所有未访问过的临接边放到一个最小堆里面LinkEdge<V,W>*edge=_linkTables[src];while(edge){if(visitedSet[edge->_dstIndex]==false){minHeap.Push(edge);}edge=_GetNextEdge(src,edge->_dstIndex);}//2.选出堆中最小的边加入生成树while(!minHeap.Empty()&&count<_vertexs.size()){edge=minHeap.Top();minHeap.Pop();if(visitedSet[edge->_dstIndex]==false){minSpanTree._AddEdge(edge->_srcIndex,edge->_dstIndex,edge->_weight);visitedSet[edge->_dstIndex]=true;src=edge->_dstIndex;++count;break;}}}while(count<_vertexs.size());returntrue;}W_GetWeight(intsrc,intdst,constW&maxValue){if(src==dst)returnmaxValue;LinkEdge<V,W>*edge=_linkTables[src];while(edge){if(edge->_dstIndex==dst){returnedge->_weight;}edge=edge->_next;}returnmaxValue;}//非负单源最短路径--Dijkstra(迪科斯彻)//求src到其他顶点的最短路径void_Dijkstra(intsrc,W*dist,int*path,bool*vSet,intsize,constW&maxValue){////1.dist初始化src到其他顶点的的距离//2.path初始化src到其他顶点的路径//3.初始化顶点集合//for(inti=0;i<size;++i){dist[i]=_GetWeight(src,i,maxValue);path[i]=src;vSet[i]=false;}//将src加入集合vSet[src]=true;intcount=size;while(count--){////选出与src顶点连接的边中最小的边//src->minWmin=maxValue;intminIndex=src;for(intj=0;j<size;++j){if(vSet[j]==false&&dist[j]<min){minIndex=j;min=dist[j];}}vSet[minIndex]=true;for(intk=0;k<size;++k){if(k==src)continue;////更新src->k的距离//如果dist(src,min)+dist(min,k)的权值小于dist(src,k)//则更新dist(src,k)和path(src->min->k)//Ww=_GetWeight(minIndex,k,maxValue);if(vSet[k]==false&&dist[minIndex]+w<dist[k]){dist[k]=dist[minIndex]+w;path[k]=minIndex;}}}}void_Dijkstra_OP(intsrc,W*dist,int*path,bool*vSet,intsize,constW&maxValue){////1.dist初始化src到其他顶点的的距离//2.path初始化src到其他顶点的路径//3.初始化顶点集合//for(inti=0;i<size;++i){dist[i]=_GetWeight(src,i,maxValue);path[i]=src;vSet[i]=false;}structCompare{booloperator()(constpair<W,int>&lhs,constpair<W,int>&rhs){returnlhs.first<rhs.first;}};Heap<pair<W,int>,Compare>minHeap;for(inti=0;i<size;++i){if(dist[i]<maxValue){minHeap.Push(make_pair(dist[i],i));}}//将src加入集合vSet[src]=true;intcount=size;while(count--){////选出与src顶点连接的边中最小的边//src->minif(minHeap.Empty())continue;intminIndex=minHeap.Top().second;minHeap.Pop();vSet[minIndex]=true;for(intk=0;k<size;++k){////如果dist(src->min)+dist(min,k)的权值小于dist(src,k)//则更新dist(src,k)和path(src->min->k)//Ww=_GetWeight(minIndex,k,maxValue);if(vSet[k]==false&&dist[minIndex]+w<dist[k]){dist[k]=dist[minIndex]+w;path[k]=minIndex;minHeap.Push(make_pair(dist[k],k));}}}}voidPrintPath(intsrc,W*dist,int*path,intsize){int*vPath=newint[size];for(inti=0;i<size;++i){if(i!=src){intindex=i,count=0;do{vPath[count++]=index;index=path[index];}while(index!=src);vPath[count++]=src;//cout<<"顶点："<<_linkTable[src]._vertex\<<"->顶点："<<_linkTable[i]._vertex<<"的路径为：";cout<<src<<","<<i<<"的路径为:";while(count){//cout<<_linkTable[vSet[--count]]._vertex<<"->";cout<<vPath[--count]<<"->";}cout<<"路径长度为："<<dist[i]<<endl;}}}voidDijkstra(intsrc,constW&maxValue){W*dist=newW[_vertexs.size()];int*path=newint[_vertexs.size()];bool*vSet=newbool[_vertexs.size()];//_Dijkstra(src,dist,path,vSet,_vertexs.size(),maxValue);_Dijkstra_OP(src,dist,path,vSet,_vertexs.size(),maxValue);//打印最短路径PrintPath(src,dist,path,_vertexs.size());delete[]dist;delete[]path;delete[]vSet;}};//无向图voidTest3(){GraphLink<char,int>g("ABCDE",5,false);g.AddEdge('A','D',10);g.AddEdge('A','E',20);g.AddEdge('B','C',10);g.AddEdge('B','D',20);g.AddEdge('B','E',30);g.AddEdge('C','E',40);g.Display();//生成最小生成树GraphLink<char,int>minSpanTree1(false);g.Kruskal(minSpanTree1);minSpanTree1.Display();//生成最小生成树GraphLink<char,int>minSpanTree2(false);g.Prim(minSpanTree2);minSpanTree2.Display();g.DFS();g.BFS();}//有向图voidTest4(){GraphLink<char,int>g("ABCDE",5,true);g.AddEdge('A','D',10);g.AddEdge('E','A',20);g.AddEdge('B','C',10);g.AddEdge('D','B',20);g.AddEdge('E','B',30);g.AddEdge('C','E',40);g.AddEdge('A','C',50);g.AddEdge('A','E',50);g.Display();g.Dijkstra(0,10000);//g.Dijkstra(1,10000);}

以上