关节点实验报告.doc

关节点实验报告实验描述：求无向图中的关节点，并把它们输出。实验算法：利用课本上的ART 算法实验注意：1.此图是无向图 2.图中的顶点和边要自己输入 3.输出DFN 和 Lu；实验中的主要数据：1. CreateA(AGraph &g,int n,int e)/创建无向图2. min(int x,int y) /判断两个数的大小，返回较小值3. ART(AGraph &g,int u,int v) /求个节点的DFN Lu的值4. About_nodes(AGraph &g,int n) /求关节点并输出】5. DFN，Lu是全局数组，存放各个顶点的DFN和Lu数；#include using namespace std;#include const int MAXV=100;typedef int ElemType;int num=1,DFNMAXV=0,LuMAXV;/全局变量DFN Lu；typedef struct ANode /边的信息int adjvex;ANode *nextarc;/下一条边的信息ArcNode;typedef struct Vnode /顶点信息ElemType data;ArcNode *firstarc;VNode;struct AGraph /图的定义VNode adjlsitMAXV;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.adjlsiti.firstarc = NULL;cout请输入n个顶点：; /输入顶点for(i = 0;i ch;g.adjlsiti.data = ch;cout请输入e条边endl; /输入e条边 for(i = 0;i a b;q = (ArcNode*)malloc(sizeof(ArcNode); p = (ArcNode*)malloc(sizeof(ArcNode); p-adjvex = b-1;q-adjvex = a-1;p-nextarc = g.adjlsita-1.firstarc;q-nextarc = g.adjlsitb-1.firstarc;g.adjlsita-1.firstarc = p; g.adjlsitb-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.adjlsitu.firstarc; DFNu=num; Luu=num; num+; while(p!=NULL) if(DFNp-adjvex=0) ART(g,p-adjvex,u);Luu=min(Luu,Lup-adjvex);else if(v!=p-adjvex) Luu=min(Luu,DFNp-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.adjlsiti.firstarc;while(p!=NULL)if(DFNi adjvex & DFNi adjvex) num+;cout i+1 nextarc;if(num=0)coutNO About nodesendl;int main() /主函数AGraph g;int n,e,i;coutne; CreateA(g,n,e); ART(g,0,0);cout输出n个顶点：endl; for(i=0;in;i+)coutg.adjlsiti.data ;coutendl;cout输出深度优先数DNF:endl; for(i=0;in;i+)coutDFNi ;couten