实施Java Graph类的间接连接测试

Question

我正在Java上写一堂课以表示图形数据结构。这是特定于未方向的，未加权的图，其目的主要用于边缘测试（是直接或间接连接到节点B的节点A）。

我需要实现间接方法的帮助。在下面的代码中，我只评论了此方法，并且我要返回false，因此代码将编译为IS。

我已经花了一些时间来提出算法，但是我似乎找不到比这简单的东西，而且我担心我使它比需要的更复杂了：

• 首先测试直接连接
• 如果没有从节点A到节点B的直接连接：
  • 对于每个边缘，我连接到节点a：
    • 创建一个不包含边缘A-> i的新图
    • 测试新的图表，用于节点I和B之间的间接连接

在您的答案中，欢迎伪代码或实际Java代码。这是我拥有的代码：

class Graph {

    // This is for an undirected, unweighted graph
    // This implementation uses an adjacency matrix for speed in edge testing 

    private boolean[][] edge;
    private int numberOfNodes;

    public Graph(int numNodes) {

        // The indices of the matrix will not be zero-based, for clarity,
        // so the size of the array will be increased by 1.

           edge = new boolean[numNodes + 1][numNodes + 1];
           numberOfNodes = numNodes;
    }

    public void addEdge(int a, int b) {
        if (a <= numberOfNodes && a >= 1) {
            if (b <= numberOfNodes && b >= 1) {
                edge[a][b] = true;
                edge[b][a] = true;
            }
        }
    }

    public void removeEdge(int a, int b) {
        if (a <= numberOfNodes && a >= 1) {
            if (b <= numberOfNodes && b >= 1) {
                edge[a][b] = false;
                edge[b][a] = false;
            }
        }
    }

    public boolean directEdgeTest(int a, int b) {

        // if node a and node b are directly connected, return true 

        boolean result = false;
        if (a <= numberOfNodes && a >= 1) {
            if (b <= numberOfNodes && b >= 1) {
                if (edge[a][b] == true) {
                    result = true;
                }
            }
        }
        return result;
    }

    public boolean indirectEdgeTest(int a, int b) {

        // if there exists a path from node a to node b, return true 

            // implement indirectEdgeTest algorithm here.

            return false;
    }
}

Answer 1

我认为Meriton的答案是他或她的答案，但是我已经将这个想法编码为工作Java课程和单位测试，因此我在这里提供单独的答案，以防任何人正在寻找可重复使用的代码。

谢谢梅里顿。我同意在直接边缘测试和路径测试之间进行区分很重要，并且有不同的图形实现，这些图形更适合特定类型的测试。在路径测试的情况下，邻接列表似乎比邻接矩阵表示更有效。

我下面的代码可能没有可能的效率，但是目前它正在解决我的问题。如果有人有改进的建议，请自由。

编译：Javac Graph.java

执行：Java GraphTest

class Graph {

    private java.util.ArrayList<Node> nodeList;
    private int numberOfNodes;

    public Graph(int size) {
        nodeList = new java.util.ArrayList<Node>(size + 1);
        numberOfNodes = size;

        for (int i = 0; i <= numberOfNodes; i++) {
            nodeList.add(new Node());
        }
    }

    public void addEdge(int a, int b) {
        if (a >= 1 && a <= numberOfNodes) {
            if (b >= 1 && b <= numberOfNodes) {
                nodeList.get(a).addNeighbour(nodeList.get(b));
                nodeList.get(b).addNeighbour(nodeList.get(a));
            }
         }
    }

    public void walk(Node origin, java.util.Set<Node> visited) {
        for (Node n : origin.getNeighbours()) {
            if (!visited.contains(n)) {
                visited.add(n);
                walk(n, visited);
            }
        }
    }

    public boolean hasPath(Node origin, Node target) {
        java.util.Set<Node> reachables = new java.util.HashSet<Node>();
        walk(origin, reachables);
        return reachables.contains(target);
    }

    public boolean hasPath(int a, int b) {

        java.util.Set<Node> reachables = new java.util.HashSet<Node>();
        Node origin = nodeList.get(a);
        Node target = nodeList.get(b);
        walk(origin, reachables);
        return reachables.contains(target);       
    }
}

class Node {

    private java.util.Set<Node> neighbours;

    public Node() {
        neighbours = new java.util.HashSet<Node>();
    }

    public void addNeighbour(Node n) {
        neighbours.add(n);
    }

    public java.util.Set<Node> getNeighbours() {
        return neighbours;
    }
}

class GraphTest {

    private static Graph g;

    public static void main(String[] args) {

        g = new Graph(6);

        g.addEdge(1,5);
        g.addEdge(4,1);
        g.addEdge(4,3);
        g.addEdge(3,6);

        printTest(1, 2);
        printTest(1, 4); 
        printTest(6, 1);   
    }

    public static void printTest(int a, int b) {

        System.out.print("Are nodes " + a + " and " + b + " connected?");
        if (g.hasPath(a, b)) {
            System.out.println(" YES.");
        } else {
            System.out.println(" NO.");
        }
    }
}

Answer 2

ERM，这种方法听起来效率非常低。这个如何：

void walk(Node orgin, Set<Node> visited) {
    for (Node n : origin.neighbours) {
        if (!visited.contains(n)) {
            visited.add(n);
            walk(n, visited);
        }
    }
}


boolean hasPath(Node origin, Node target) {
    Set<Node> reachables = new HashSet<Node>();
    walk(origin, reachables);
    return reachables.contains(target);
}

同样，使用邻接矩阵对于图形遍历的可疑用途是可疑的，因为您无法在稀疏图中有效地迭代节点的邻居。

如果经常使用该方法，并且图形很少更改，则可以通过将分解为 连接区域 前面，并为每个节点存储它所属的区域。然后，如果两个节点属于同一区域，则连接两个节点。

编辑：要澄清如何最好地表示图形。对于直接边缘测试，首选邻接矩阵。对于路径测试，分解为区域。后者并不是要随着图形的变化而保持电流并不是很重要的，但是文献中可能存在算法。或者，邻接列表可用于图形遍历并因此可以进行路径测试，但与将分解记录到连接区域相比，它们的效率较小。您还可以使用邻接集在稀疏图中结合更有效的邻居迭代和恒定的边缘测试。

请记住，您还可以冗余地存储信息，以保存每种查询，量身定制的单独数据结构。

Answer 3

您的解决方案将起作用，但更好的解决方案是从根“ A”节点构造一个生成树。这样，您最终只需要考虑一棵树，而不是仅缺少特定边缘的多个子图。

一旦您 明白, ，您如何实施它取决于您。假设您可以以合理的方式实现该算法，则您只应该有一棵树要搜索连接性，这将大大加快速度。