小编con*_*ish的帖子

请注意,图表表示为邻接列表.

我听说有两种方法可以在图表中找到一个循环:

1. 保留一个布尔值数组,以跟踪您之前是否访问过某个节点.如果你的新节点用完了(没有点击你已经存在的节点),那么只需回溯并尝试不同的分支.

2. 来自Cormen的CLRS或Skiena的那个:对于无向图中的深度优先搜索,有两种类型的边,树和背.当且仅当存在后沿时,该图具有循环.

有人可以解释一下图的后边缘是什么,以及上述两种方法之间的差异是什么.

谢谢.

更新: 这是在两种情况下检测周期的代码.Graph是一个简单的类,为了简单起见,将所有图形节点表示为唯一编号,每个节点都有其相邻的相邻节点(g.getAdjacentNodes(int)):

public class Graph {

  private int[][] nodes; // all nodes; e.g. int[][] nodes = {{1,2,3}, {3,2,1,5,6}...};

  public int[] getAdjacentNodes(int v) {
    return nodes[v];
  }

  // number of vertices in a graph
  public int vSize() {
    return nodes.length;
  }

}

用于检测无向图中的循环的Java代码:

    public class DFSCycle {

    private boolean marked[];
    private int s;
    private Graph g;
    private boolean hasCycle;

    // s - starting node
    public DFSCycle(Graph g, int s) {
        this.g = g;
        this.s = …

如何在 testNG 中使用 IAnnotationTransformer？当我调试时，代码从未进入转换函数。它执行了所有 3 个测试。我使用 Maven 来触发我的测试，这就是我所拥有的——

public class SomeTest {

    @BeforeClass
    public void before(){

        TestNG testNG = new TestNG();
        testNG.setAnnotationTransformer(new Transformer());
    }

    @Test(priority = 1)
    public void test1(){}

    @Test(priority = 2)
    public void test2(){}

    @Test(priority = 3)
    public void test3(){}
}

public class Transformer implements IAnnotationTransformer {

    public void transform(ITestAnnotation annotation, Class testClass, Constructor testConstructor, Method testMethod){

        if (true){
            annotation.setEnabled(false);
        }
    }
}