关节点实验报告

《关节点实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、关节点实验报告实验描述：求无向图中的关节点，并把它们输出。实验算法：利用课本上的ART算法实验注意：1.此图是无向图2.图中的顶点和边要自己输入3.输出DFN和Lu；实验中的主要数据：1.CreateA(AGraph&g,intn,inte)//创建无向图2.min(intx,inty)//判断两个数的大小，返回较小值3.ART(AGraph&g,intu,intv)//求个节点的DFNLu的值4.About_nodes(AGraph&g,intn)//求关节点并输出】5.DFN[]，Lu[]是全局数组，存放各个顶点的DFN和Lu数；#include

2、m>usingnamespacestd;#includeconstintMAXV=100;typedefintElemType;intnum=1,DFN[MAXV]={0},Lu[MAXV];//全局变量DFNLu；typedefstructANode{//边的信息intadjvex;ANode*nextarc;//下一条边的信息}ArcNode;typedefstructVnode{//顶点信息ElemTypedata;ArcNode*firstarc;}VNode;structAGraph{//图的定义VNodeadjlsit[MAXV];i

3、ntvexnum,arcnum;};voidCreateA(AGraph&g,intn,inte)//创建无向图{inta,b;inti;ArcNode*p,*q;g.vexnum=n;g.arcnum=e;for(i=0;i>ch;g.adjlsit[i].data=ch;}cout<<"请输入e条边"<>a

4、>>b;q=(ArcNode*)malloc(sizeof(ArcNode));p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=b-1;q->adjvex=a-1;p->nextarc=g.adjlsit[a-1].firstarc;q->nextarc=g.adjlsit[b-1].firstarc;g.adjlsit[a-1].firstarc=p;g.adjlsit[b-1].firstarc=q;}}intmin(intx,inty)//判断两个数的大小，返回较小值{if(x>y)returny;elseretur

5、nx;}voidART(AGraph&g,intu,intv)//求个节点的DFNLu的值{ANode*p=g.adjlsit[u].firstarc;DFN[u]=num;Lu[u]=num;num++;while(p!=NULL){if(DFN[p->adjvex]==0){ART(g,p->adjvex,u);Lu[u]=min(Lu[u],Lu[p->adjvex]);}elseif(v!=p->adjvex){Lu[u]=min(Lu[u],DFN[p->adjvex]);}p=p->nextarc;}}voidAbout_nodes(AGraph&g,i

6、ntn)//求关节点{ANode*p;intnum=0;inti;for(i=1;iadjvex]&&DFN[i]<=Lu[p->adjvex]){num++;cout<nextarc;}}if(num==0)cout<<"NOAboutnodes"<>n>>e;Creat

7、eA(g,n,e);ART(g,0,0);cout<<"输出n个顶点："<