0

我正在用 Java 编写一个类来表示 Graph 数据结构。这特定于无向、未加权的图，其目的主要用于边缘测试（节点 A 直接或间接连接到节点 B）。

我需要帮助来实现indirectEdgeTest 方法。在下面的代码中，我只注释了这个方法并且我返回 false，所以代码将按原样编译。

我花了一些时间想出一个算法，但我似乎找不到比这更简单的东西了，我担心我让它变得比它需要的更复杂：

  • 首先测试直接连接
  • 如果从节点 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;
    }
}
4

3 回答 3

2

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

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);
}

此外，使用邻接矩阵对于图遍历的用途是有问题的，因为您无法有效地迭代稀疏图中节点的邻居。

如果该方法经常使用，并且图形很少更改，则可以通过预先分解为连接区域并为每个节点存储它所属的区域来加快查询速度。然后，如果它们属于同一区域，则连接两个节点。

编辑：澄清如何最好地表示图表。对于直接边缘测试，邻接矩阵是首选。对于路径测试，分解为区域。后者随着图形的变化而保持最新并不是微不足道的，但文献中可能有用于此的算法。或者，邻接表可用于图遍历和路径测试，但它们的效率仍然低于直接将分解记录到连接区域中。您还可以使用邻接集将稀疏图中更有效的邻居迭代与恒定时间边缘测试相结合。

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

于 2010-08-23T19:57:59.927 回答
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.");
        }
    }
}
于 2010-08-24T17:28:49.147 回答
1

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

一旦你有了这个想法，你如何实现它就取决于你了。假设您可以以合理的方式实现该算法，您应该只有一棵树来搜索连通性，这将大大加快速度。

于 2010-08-23T19:53:41.330 回答