0

给定一个图 G 和 3 个顶点 a、b 和 c，在线性时间内验证从 a 开始并通过 b 的所有无限路径在到达 b 之前必然也从顶点 c 经过 如果只有顶点 c 在之前出现，则算法返回 True B 沿着从 a 开始到 b 的无限路径

我试图实现一个解决方案，但我不确定我以 3 种方式为图的节点着色黑色（n），白色（b），灰色（g）

ALGO(G,a,b,c)
  init(G);
  color[c]=n;
  DFS_Visit(G,a);
  ret=true;
  if(color[b]=n)then
    init(G);
    ret=DFS_VisitMod(G,b);
  return ret;

  init(G)
    for each v in V do
      color[v]=b;

  DFS_VisitMod(G,a)
    color[a]=g;
    for each v in adj(a) do
      if(color[v]=b)then
        ret=DFS_VisitMod(G,v);
        if(ret=false)then
          return false;
      else if(color[v]=g)then
        return false;
    color[a]=n;
    return true;
4

0 回答 0