数据结构图的基本运算代码.doc

《数据结构图的基本运算代码.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、#include"iostream"#include"LGraph.h"#include"seqqueue.h"#include"MGraph.h"#defineINFTY1000templatestructENode{ENode(){nextArc=NULL;}ENode(intvertex,Tweight,ENode*next){adjVex=vertex;w=weight;nextArc=next;}intadjVex;Tw;ENode*nextArc;};templateclassExtLGraph:publicLGrap

2、h{public:ExtLGraph(intmSize):LGraph(mSize){}voidDFS();voidBFS();voidTopoSort(int*order);private:voidCalInDegree(int*InDegree);voidDFS(intv,bool*visited);voidBFS(intv,bool*visited);};templatevoidExtLGraph::DFS(){bool*visited=newbool[n];for(inti=0;i

3、lse;for(i=0;ivoidExtLGraph::DFS(intv,bool*visited){visited[v]=true;cout<<""<*t=a[v];t;t=t->nextArc)if(!visited[t->adjVex])DFS(t->adjVex,visited);}templatevoidExtLGraph::BFS(){bool*visit

4、ed=newbool[n];for(inti=0;ivoidExtLGraph::BFS(intv,bool*visited){SeqQueueq(Vertices());visited[v]=true;cout<<""<

5、(ENode*t=a[v];t;t=t->nextArc)if(!visited[t->adjVex]){visited[t->adjVex]=true;cout<<""<adjVex;}q.EnQueue(t->adjVex);}}templatevoidExtLGraph::CalInDegree(int*InDegree)//计算所有顶点的入度{for(inti=0;i*p=a[i];p;p=p->nextArc)InDeg

6、ree[p->adjVex]++;}templatevoidExtLGraph::TopoSort(int*order){int*InDegree=newint[n];inti,j,k,top=-1;CalInDegree(InDegree);for(i=0;i

7、[i]=j;cout<*p=a[j];p;p=p->nextArc){k=p->adjVex;InDegree[k]--;if(!InDegree[k]){InDegree[k]=top;top=k;}}}}}templateclassExtMGraph:publicMGraph{public:ExtMGraph(intmSize,constT&noedg):MGraph(mSize,noedg){}voidDFS();voidBFS();voidDFS(intv);voidBFS(intv);i

8、ntChoose(int