Java:如何表示图形？

Question

我正在实现一些算法来自学图表以及如何使用它们。你会推荐什么是在 Java 中做到这一点的最佳方法？我在想这样的事情:

public class Vertex {

    private ArrayList<Vertex> outnodes; //Adjacency list. if I wanted to support edge weight, this would be a hash map.

    //methods to manipulate outnodes
}

public class Graph {
    private ArrayList<Vertex> nodes;
    //algorithms on graphs
}

但我基本上只是编造了这个。有没有更好的办法？

另外，我希望它能够支持普通图的变体，例如有向图、加权边、多重图等。

Answer 1

每个节点都是唯一命名的，并且知道它连接到谁。连接列表允许一个节点连接到任意数量的其他节点。

public class Node {
    public String name;
    public List<Edge> connections;
}

每个连接都是有向的，有起点和终点，并且是加权的。

public class Edge {
    public Node start;
    public Node end;
    public double weight;
}

图表只是您的节点集合。而不是 List<Node>考虑Map<String, Node>按名称快速查找。

public class Graph {
    List<Node> nodes;
}