关节点实验报告.docVIP

关节点实验报告 实验描述：求无向图中的关节点，并把它们输出。 实验算法：利用课本上的ART 算法 实验注意：1.此图是无向图 2.图中的顶点和边要自己输入 3.输出DFN 和 Lu； 实验中的主要数据： CreateA(AGraph g,int n,int e)//创建无向图 min(int x,int y) //判断两个数的大小，返回较小值 ART(AGraph g,int u,int v) //求个节点的DFN Lu的值 About_nodes(AGraph g,int n) //求关节点并输出】 DFN[]，Lu[]是全局数组，存放各个顶点的DFN和Lu数； #include iostream using namespace std; #include malloc.h const int MAXV=100; typedef int ElemType; int num=1,DFN[MAXV]={0},Lu[MAXV];//全局变量DFN Lu； typedef struct ANode{ //边的信息 int adjvex; ANode *nextarc;//下一条边的信息 }ArcNode; typedef struct Vnode{ //顶点信息 ElemType data; ArcNode *firstarc; }VNode; struct AGraph{ //图的定义 VNode adjlsit[MAXV]; int vexnum,arcnum; }; void CreateA(AGraph g,int n,int e)//创建无向图 { int a,b;int i; ArcNode *p,*q; g.vexnum = n; g.arcnum = e; for(i = 0;i g.vexnum;i++) g.adjlsit[i].firstarc = NULL; cout请输入n个顶点：; //输入顶点 for(i = 0;i n;i++) { ElemType ch; cin ch; g.adjlsit[i].data = ch; } cout请输入e条边endl; //输入e条边 for(i = 0;i e;i++) { cin a 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; } } int min(int x,int y) //判断两个数的大小，返回较小值 { if(xy) return y; else return x; } void ART(AGraph g,int u,int v) //求个节点的DFN Lu的值 { 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]); } else if(v!=p-adjvex) { Lu[u]=min(Lu[u],DFN[p-adjvex]); } p=p-nextarc; } } void About_nodes(AGraph g,int n) //求关节点 { ANode *p; int num=0; int i; for(i=1;in;i++) { p=g.adjlsit[i].firstarc; while(p!=NULL) { if(DFN[i] DFN[p-adjvex] DFN[i] = Lu[p-adjvex]) { num++; cout i+1 ; break; } p=p-nextarc; } } if(num==0) coutNO About