Java中的图形实现

Question

我正在尝试创建一个图形类，使用另一个类Vertex来表示图的所有顶点。我不确定是否需要一个Edge类来表示两个顶点之间可能的连接，因为每个顶点可以跟踪其连接到的其他节点。但我不确定这是否正确。你觉得呢？

谢谢。

- FranXh

---

问：这是“作业”吗？如果是，请标记它。无论如何，请看一下这个链接：http://en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29 - paulsm4

这不是作业。我知道如何使用和不使用Edge类来实现该类。我只是想知道在没有Edge类的情况下是否正确。谢谢提供链接。 - FranXh

Answer 1

您不必使用一个 Edge 类。您可以使用邻接表，仍然可以正确地表示一个 无权重 图。对于有权重的图，需要一种表示边权值的方式，因此使用 Edge 类是合适的。

class Graph<E> {
    private List<Vertex<E>> vertices;

    private static class Vertex<E> {
        E elem;
        List<Vertex<E>> neighbors;
    }
}

- blackcompe

---

是的，这正是我所想的。在完全不使用边缘类的情况下跟踪其他顶点。谢谢！！！ - FranXh

一切都很好，直到你需要一个带权重的有向图。那么你将需要元数据或者更好的边缘类(Edge class)。 - Andrew T Finnell

Answer 2

通常，选择一种数据结构的 表示 取决于其适用性。在这个简单的例子中，GraphPanel 仅使用一个 List<Edge> 作为其模型。

- trashgod