java - Java中用于存储图形的数组

Question

我正在用 java 创建一个程序来对图执行深度优先搜索。

问题是输入文件有 500 万行。文件的每一行都包含两个数字，表示一条无向边。

存储这些数据的最佳方式是什么？

Answer 1

假设现代计算机具有合理数量的 RAM，创建 500 万个对象来存储链接应该没有问题。您使用的数据结构很可能取决于您打算如何使用它。在您的情况下，您想执行深度优先搜索，这意味着从它们接触的两个节点引用链接会很方便。

假设未加权链接，一个非常简单的数据结构示例可能是:

class Node {
    private final int id;
    private final List<Node> linkedNodes = new ArrayList<>();

    public Node(int id) {
        this.id = id;
    }

    public void addLink(Node linkNode) {
        linkedNodes.add(linkNode);
    }
}

class Graph {
    private final Map<Integer, Node> nodes = new HashMap<>();
    public addLink(int id1, int id2) {
        getNode(id1).addLink(getNode(id2));
        getNode(id2).addLink(getNode(id1));
    }

    private getNode(int id) {
        if (!nodes.containsKey(id)) {
            nodes.add(new Node(id));
        }
        return nodes.get(id);
    }
}

使用这种数据结构，您的搜索变得相对简单:

public Node {
    public void search(List<Node> visitedList, Consumer<Node> action) {
        visitedList.add(this);
        linkedNodes.stream()
            .filter(n -> !visitedList.contains(n))
            .collect(Collectors.toList())
            .forEach(n -> n.search(visitedList, action);
        action.accept(this);
    }
}

我在这里使用了 Java 8 流，但转换为传统迭代应该不会太难。请注意，我在搜索链接节点之前将它们收集到一个列表中，以避免在中途更改列表。

如果您在轻量级硬件上运行或要处理数十亿行，那么您可能需要考虑更轻量级的数据结构。