用邻接表java实现图形

Question

对于许多点，我有2D的协定子，例如点a=x，y

我想做一个图的实现使用邻接列表列表和连接某些点的无方向图在最有效的方式（不使用地图或哈希表）

Answer 1

您可以尝试这种无向图的嵌入

public class Graph {

    private static final String NEW_LINE = System.lineSeparator();

    private final int vertices;
    private int edges;
    private List<Integer>[] adj;

    public Graph(int v) {
        if (v < 0)
            throw new IllegalArgumentException("Number of vertices must be non-negative");
        this.vertices = v;
        this.edges = 0;
        adj = (List<Integer>[]) new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[v] = new LinkedList<Integer>();
        }
    }

    public int getVertices() {
        return vertices;
    }

    public int getEdges() {
        return edges;
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
        edges++;
    }

    public int degree(int v) {
        return adj[v].size();
    }

    public Iterable<Integer> adj(int v) {
        return adj[v];
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (int v = 0; v < vertices; v++) {
            builder.append(v + ": ");
            for (int w : adj[v]) {
                builder.append(w + " ");
            }
            builder.append(NEW_LINE);
        }
        return builder.toString();
    }
}