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

Answer 2

如果需要加权边和多图,则可能需要添加另一个类Edge.

我还建议使用泛型来指定当前使用的Vertex和Edge的哪个子类.例如:

public class Graph<V extends Vertex> {
List<V> vertices;
...
}

在实现图算法时,您还可以为算法可以操作的图类定义接口,以便您可以使用实际图表示的不同实现.例如,连接良好的简单图形可能更好地通过邻接矩阵实现,较稀疏的图形可能由邻接列表表示- 这一切都取决于......

BTW高效地构建这样的结构可能非常具有挑战性,所以也许你可以给我们一些关于你想用它们做什么工作的更多细节？对于更复杂的任务,我建议您查看各种Java图形库,以获得一些灵感.

Answer 3

看一下http://jung.sourceforge.net/doc/index.html图库.您仍然可以练习实现自己的算法(可能是广度优先或深度优先搜索开始),但您不必担心创建图形结构.

Answer 4

为什么不保持简单并使用邻接矩阵或邻接表？