java - 帮助实现 Java 图形

Question

我必须编写一个程序，将顶点存储到图中并将它们连接起来。程序的输入如下:

Plot 3 5 to 5 8
Plot 6 1 to 3 5
etc

根据这个输入，我将存储 (3,5) 的顶点，它是 x 和 y 坐标。然后我必须将此坐标连接到 (5,8)。

我的问题是，我将如何实现这个图表？我在想我需要将顶点存储在数组列表或 map 中，并将边缘也保存在列表中......但是因为我没有给出图形的实际最大大小，所以我有点迷路在整体实现上。基本上，如果你们能给我一个如何开始的想法，那就太好了。

Answer 1

考虑图形的一种简单方法是将它们分解为节点和边组件。 (注意:你称之为顶点的东西我称之为节点。足够接近了。)

让我们考虑以下选项:

// Option 1
class Node<V> {
    V data;
    Set<Node<V>> edges;
    // if it were a directed graph, you'd need:
    // Set<Node<V>> edgesAway;
}

// Option 2
class Node<V> {
    V data;
    Set<Edge<V>> edges;
    // if it were a directed graph, you'd need:
    // Set<Edge<V>> edgesAway;
}

class Edge<V> {
    Node<V> source;
    Node<V> destination;
}

现在一个图无非就是:

// option 1
class Graph<V> {
    Set<Node<V>> nodes;
}

// option 2
class Graph<V> {
    Set<Node<V>> nodes;
    Set<Edge<V>> edges;
}

选项 1 是最简单和最容易实现的。选项 2 为您提供更多灵 active ，例如为边缘值添加权重。

现在，您在这些节点上有一些数据，对吗？现在，让我们将数据作为坐标的字符串表示。

class SomeObject {
    String data;
    int x;
    int y;

    public boolean equals(Object o) {
        if(o instanceof SomeObject) {
            SomeObject so = (SomeObject)o;
            return so.x == x && so.y == y;
        }
        return false;
    }

    public int hashCode() {
        return x * 100 + y; // it works... close enough :)
    }
}

// somewhere later:
Graph<SomeObject> graph = ...

现在至于您需要什么功能，您需要一个更完整的列表。但这应该能让您顺利理解如何实现图表。