java - 使用空间 O(边数)的图形表示的邻接列表

Question

为了使用 BFS 查找一些信息。我从名为 graph.txt 的 txt 中获取有关图形的信息。我不确定我是否使用空间 O(m) 来保存图形，而且我不确定这是否是保存它以便使用 BFS 的好方法。

public class Vertex  {
    boolean visited = false;
    int number;
    ArrayList<Integer> adjList;
    public Vertex(int i) {
        this.number= i;
        adjList = new ArrayList<Integer>(); 
    }
    public void addNeighbor(int i) {
        this.adjList.add(i);
    }
}

Answer 1

是的，您的表示确实使用了 O(m) 空间。根据您的陈述，我有两个不同的建议。

1.如果你真的想将顶点表示为一个类，那么它的相邻顶点列表是List 而不是 List

或

2。由于您的 Vertex 类似乎除了顶点的 Integer 值之外没有任何其他信息，为什么不直接使用 Integer 本身呢？该图可以表示为

ArrayList<ArrayList<Integer>> graph;

其中graph[i]是连接到顶点i的顶点列表这样一来，您就不必从整数 ID 到 Vertex 实例中找到匹配项。