Java：如何表示图形？

java graph

2022-09-01 00:34:21

我正在实现一些算法来自学图形以及如何使用它们。你会建议在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
}

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

另外，我希望它能够支持普通图的变化，如双连字符，加权边，多图等。

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

答案 2

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

我还建议使用泛型来指定当前使用的顶点和 Edge 的哪个子类。例如：

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

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

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