《利用深度优先搜索求连通图G的所有关节点(共3页).doc》由会员分享，可在线阅读，更多相关《利用深度优先搜索求连通图G的所有关节点(共3页).doc（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上#includeusing namespace std;#define MAX 50int LowMAX,dMAX;typedef struct ENode/定义结点 int AdjVex;/该弧所指向的的顶点位置struct ENode *NextArc;/指向下一条弧的指针int info; ArcNodeMAX;typedef structArcNode vertices;/邻接表int vexnum,arcnum;/顶点数和边数 ALGraph;ALGraph G=*(ALGraph *)malloc(sizeof(ALGraph);void DFS(int
2、u,int p)/p为根节点static int time=0;int v;Lowu=du=time+;for(ENode *w=&(G.verticesu);w;w=w-NextArc)v=w-AdjVex;if(dv=-1)/表示v未访问DFS(v,u);if(LowuLowv)Lowu=Lowv;/当孩子节点的Low值大于父亲节点的Low值，将孩子节点的Low值赋给父亲节点的Low值else if(v!=p&Lowudv)Lowu=dv;/当孩子节点不是根节点且父亲的Low值大于孩子节点的深度时，将孩子节点的深度赋给孩子节点void CreatGraph()int i,j,k,u,n=0
3、;ENode *N;cinG.vexnum;for(u=0;uG.arcnum;for(k=0;kij;/图的初始化N=(ENode *)malloc(sizeof(ENode);N-AdjVex=j;N-NextArc=G.verticesi.NextArc;G.verticesi.NextArc=N;N=(ENode *)malloc(sizeof(ENode);N-AdjVex=i;N-NextArc=G.verticesj.NextArc;G.verticesj.NextArc=N;DFS(G.vertices0.AdjVex,-1);int main()int i;int n=0;CreatGraph();for(i=0;iNextArc)if(Loww-AdjVex=di&i!=G.vertices0.AdjVex)n+;break;coutnendl;return 0;专心-专注-专业