《数据结构图的基本运算代码》由会员分享，可在线阅读，更多相关《数据结构图的基本运算代码（14页珍藏版）》请在金锄头文库上搜索。
1、文档供参考，可复制、编制，期待您的好评与关注！ #includeiostream#includeLGraph.h#includeseqqueue.h#includeMGraph.h#define INFTY 1000templatestruct ENodeENode()nextArc=NULL;ENode(int vertex,T weight,ENode *next)adjVex=vertex;w=weight;nextArc=next;int adjVex;T w;ENode* nextArc;templateclass ExtLGraph:public LGraphpublic:ExtL
2、Graph(int mSize):LGraph(mSize)void DFS();void BFS();void TopoSort(int *order);private:void CalInDegree(int *InDegree);void DFS(int v,bool *visited);void BFS(int v,bool *visited);templatevoid ExtLGraph:DFS()bool *visited=new booln;for(int i=0;in;i+)visitedi=false;for(i=0;in;i+)if(!visitedi) DFS(i,vis
3、ited);delete visited;templatevoid ExtLGraph:DFS(int v,bool *visited)visitedv=true;cout v;for(ENode *t=av;t;t=t-nextArc)if(!visitedt-adjVex)DFS(t-adjVex,visited);templatevoid ExtLGraph:BFS()bool *visited=new booln;for(int i=0;in;i+)visitedi=false;for(i=0;in;i+)if(!visitedi) BFS(i,visited);delete visi
4、ted;templatevoid ExtLGraph:BFS(int v,bool *visited)SeqQueueq(Vertices();visitedv=true;cout v;q.EnQueue(v);while(!q.IsEmpty()q.Front(v);q.DeQueue();for(ENode *t=av;t;t=t-nextArc)if(!visitedt-adjVex)visitedt-adjVex=true;cout adjVex;q.EnQueue(t-adjVex);templatevoid ExtLGraph:CalInDegree(int *InDegree)
5、/计算所有顶点的入度for(int i=0;in;i+)InDegreei=0;for(i=0;in;i+)for(ENode* p=ai;p;p=p-nextArc)InDegreep-adjVex+;templatevoid ExtLGraph:TopoSort(int *order)int *InDegree=new intn;int i,j,k,top=-1;CalInDegree(InDegree);for(i=0;in;i+)if(!InDegreei)InDegreei=top;top=i;for(i=0;in;i+)if(top=-1)coutHas cycle!endl;re
6、turn;elsej=top;top=InDegreetop;orderi=j;coutj ;for(ENode* p=aj;p;p=p-nextArc)k=p-adjVex;InDegreek-;if(!InDegreek)InDegreek=top;top=k;templateclass ExtMGraph:public MGraphpublic:ExtMGraph(int mSize,const T&noedg):MGraph(mSize,noedg)void DFS();void BFS();void DFS(int v);void BFS(int v);int Choose(int
7、*d,bool *s);void Dijkstra(int v,T *d,int *path);void ShowDijkstra(int v,int flag);void DijkstraForHomework(int v);/用于作业，该段代码与实验无关void Floyd(T *d,int *path);void FloydForHomework(int v);/用于作业，该段代码与实验无关private:void DFS(int v,bool *visited);void BFS(int v,bool *visited);templatevoid ExtMGraph:DFS(int v
8、)bool *visited=new booln;for(int i=0;in;i+)visitedi=false;for(i=v;in;i+)if(!visitedi) DFS(i,visited); for(i=0;iv;i+)if(!visitedi) DFS(i,visited); delete visited;templatevoid ExtMGraph:DFS()bool *visited=new booln;for(int i=0;in;i+)visitedi=false;for(i=0;in;i+)if(!visitedi) DFS(i,visited);delete visi
9、ted;templatevoid ExtMGraph:DFS(int v,bool *visited)visitedv=true;cout v;for(int t=0;tn;t+)if(avt!=noEdge&!visitedt)DFS(t,visited);templatevoid ExtMGraph:BFS(int v)bool *visited=new booln;for(int i=0;in;i+)visitedi=false;for(i=v;in;i+)if(!visitedi) BFS(i,visited); for(i=0;iv;i+)if(!visitedi) BFS(i,vi
10、sited); delete visited;templatevoid ExtMGraph:BFS()bool *visited=new booln;for(int i=0;in;i+)visitedi=false;for(i=0;in;i+)if(!visitedi) BFS(i,visited);delete visited;templatevoid ExtMGraph:BFS(int v,bool *visited)SeqQueueq(Vertices();visitedv=true;cout v;q.EnQueue(v);while(!q.IsEmpty()q.Front(v);q.D
11、eQueue();for(int j=0;jn;j+)if(avj!=noEdge&visitedj!=true) cout j;visitedj=true;q.EnQueue(j);templateint ExtMGraph:Choose(int *d,bool *s)int i,minpos;T min;min=INFTY; minpos=-1;for(i=0;in;i+)if(dimin&!si)min=di;minpos=i;return minpos;templatevoid ExtMGraph:Dijkstra(int v,T *d,int *path) int i,k,w;if(vn-1)coutout of bounds!endl;return;bool *s=new booln;for(i=0;in;i+)si=false;di=avi;if(i!=v&diINFTY)pathi=v;else pathi=-1;sv=true;dv=0;for(i=0;in;i+)k=Choose(d,s);if(k=-1) break;/若找不出下一个可连通的定点说明源点也无法到达别的定点，算法结束sk=true;fo
