#include<iostream.h>typedefintelemtype;constMAX=100;boolvisited[MAX];classlink{public:elemtypedata;link*next;};classnode{public:linka[MAX];voidcreatlink3(node&g,intn,inte);voidbfs2(nodeg,inti);voiddfs1(nodeg,inti);voidtopsort(node&g,intn);};voidnode::creatlink3(node&g,intn,inte)//建立带入度的邻接表{inti,j,k;link*s;for(i=1;i<=n;i++)//建立邻接表头结点{g.a[i].data=0;//入度值为0g.a[i].next=NULL;}for(k=1;k<=e;k++){cout<<"请输入一条弧:";cin>>i>>j;//输入一条弧<i,j>cout<<endl;s=newlink;//申请一个动态存储单元s->data=j;s->next=g.a[i].next;g.a[i].next=s;g.a[j].data++;//入度加1}}voidnode::topsort(node&g,intn)//拓扑排序{inttop=0,m=0;for(inti=1;i<=n;i++)//入度为0的顶点进栈if(g.a[i].data==0){g.a[i].data=top;top=i;}while(top>0){i=top;top=g.a[top].data,//出栈cout<<i<<"";//输出入度为0的顶点m++;//输出结点个数增1link*p=g.a[i].next;while(p!=NULL){intk=p->data;g.a[k].data--;//删除一条边，顶点入度值减1if(g.a[k].data==0){g.a[k].data=top;top=k;}//入度为0进栈p=p->next;}}if(m<n)cout<<"网络中出现环路";}voidnode::bfs2(nodeg,inti){intq[MAX];intf,r;link*p;f=r=0;cout<<i<<"";visited[i]=true;r++;q[r]=i;while(f<r){f++;i=q[f];p=g.a[i].next;while(p!=NULL){if(!visited[p->data]){cout<<p->data<<"";visited[p->data]=true;r++;q[r]=p->data;}p=p->next;}}}voidnode::dfs1(nodeg,inti){link*p;cout<<i<<"";visited[i]=true;p=g.a[i].next;while(p!=NULL){if(!visited[p->data])dfs1(g,p->data);p=p->next;}}voidmain(){nodeg;intyn=1;while(yn==1){intn1,e1;cout<<"请输入要建立的有向图的元素个数：";cin>>n1;cout<<endl;cout<<"请输入要建立的有向图的边数：";cin>>e1;cout<<endl;cout<<"########################################################################"<<endl;cout<<"################建立邻接表################"<<endl;g.creatlink3(g,n1,e1);intflag=1;while(flag==1){for(inti=1;i<=n1;i++)visited[i]=false;cout<<"深度优先搜索遍历序列为："<<endl;for(i=1;i<=n1;i++)if(!visited[i])g.dfs1(g,i);cout<<endl;cout<<"########################################################################"<<endl;for(i=1;i<=n1;i++)visited[i]=false