试设计一个算法 判断一个无环路有向图G中是否存在这样的顶点 该顶点到其他任意顶点都有一条路径

正确答案：算法的基本设计思想：若存在这样的顶点该顶点到其他任意结点都有一条有向路径又因为该有向图是无环路的那么该顶点到这些结点之间的路径构成一棵树此树的结点数应该等于图的结点数。若不等于则不存在这样的结点。因此从任意结点开始遍历此图(DFS、BFS均可)若visited的结点数等于图的结点数则存在否则不存在。算法的代码： Struct node( int adjvex; node*next； } ／／结点的数据类型定义 struct g{ vertextype data ; node *firstarc； }typedef ADJLIST; ／／邻接表的数据类型定义 方法一：广度优先遍历(使用队列) int rbfs(ADJLIST gint viint vj) { int icountyes； yes=0； ／／yes用来判断是否遍历到所有顶点 count=1； ／／用来对已遍历顶点计数 Queue Q； for(i=0；iadj data ; if(viSited[W]==0) { viSited[W]=1; cOUnt++； EnQueue(WQ); } elSe P=P->next； } } if(count==V) ／／V为有向图结点总数 yeS=1； return yeS； }／／rbfS 方法二：深度优先遍历(使用栈) int rdfs(ADJLIST gint viint vj) { int icountyeS； yes=0； Count=1 ; Stack S； for(i=0；iadjdata)) { P=P->next： if(p==NULL) Pop(S); e1Se { w=p一>adj data; viSited[W]=1； COUnt++; PuSh(WS)； } } } if(count==v; ／／v为有向图结点总数 yeS=1； return yes； }／／rbfs
算法的基本设计思想：若存在这样的顶点,该顶点到其他任意结点都有一条有向路径,又因为该有向图是无环路的,那么该顶点到这些结点之间的路径构成一棵树,此树的结点数应该等于图的结点数。若不等于,则不存在这样的结点。因此,从任意结点开始,遍历此图(DFS、BFS均可),若visited的结点数等于图的结点数,则存在,否则不存在。算法的代码：Structnode(intadjvex;node*next；}／／结点的数据类型定义structg{vertextypedata;node*firstarc；}typedefADJLIST;／／邻接表的数据类型定义方法一：广度优先遍历(使用队列)intrbfs(ADJLISTg,intvi,intvj){inti,count,yes；yes=0；／／yes用来判断是否遍历到所有顶点count=1；／／用来对已遍历顶点计数QueueQ；for(i=0；iadjdata;if(viSited[W]==0){viSited[W]=1;cOUnt++；EnQueue(W,Q);}elSeP=P->next；}}if(count==V)／／V为有向图结点总数yeS=1；returnyeS；}／／rbfS方法二：深度优先遍历(使用栈)intrdfs(ADJLISTg,intvi,intvj){inti,count,yeS；yes=0；Count=1;StackS；for(i=0；iadjdata)){P=P->next：if(p==NULL)Pop(S);e1Se{w=p一>adjdata;viSited[W]=1；COUnt++;PuSh(W,S)；}}}if(count==v;／／v为有向图结点总数yeS=1；returnyes；}／／rbfs