帮助Java图形实现 [英] Help with Java Graph Implementation

问题描述

我必须编写一个程序，将verticies存储到一个图中并将它们连接起来。该程序的输入为：

 绘图3 5至5 8 
绘图6 1至3 5 
等
  

从这个输入中，我将存储一个的vertix 3,5），它们是 x 和 y 坐标。然后我必须将此坐标连接到（5,8）。

我的问题是，我将如何去实现这个图表？我想我需要将顶点存储在一个数组列表或地图中，并将边缘保存在一个列表中，但由于我没有给出图的实际最大尺寸，所以我有点迷路了在整体实施中。基本上，如果你们可以给我一个想法如何开始，这将是甜美的。

解决方案

简单的方法思考图是将它们分解成它们的节点和边缘组件。 （注意：你称之为一个顶点，我调用一个节点，足够接近。）

让我们考虑以下选项：

  //选项1 
 class节点< V> {
 V数据; 
 Set< Node< V>>边缘; 
 //如果它是有向图，则需要：
 // Set< Node< V>> edgesAway; 
} 
 
 //选项2 
 class节点< V> {
 V数据; 
 Set< Edge< V>>边缘; 
 //如果它是有向图，则需要：
 // Set< Edge< V>> edgesAway; 
} 
 
 class Edge< V> {
节点< V>资源; 
节点< V>目的地; 
} 
  

现在图形只不过是：

  //选项1 
类图< V> {
 Set< Node< V>>节点; 
} 
 
 //选项2 
类图< V> {
 Set< Node< V>>节点; 
 Set< Edge< V>>边缘; 
} 
  

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

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

  class SomeObject {
字符串数据; 
 int x; 
 int y; 
 
 public boolean equals（Object o）{
 if（o instanceof SomeObject）{
 SomeObject so =（SomeObject）o; 
返回so.x == x&& so.y == y; 
} 
返回false; 
 
 
 public int hashCode（）{
 return x * 100 + y; //它的工作原理......足够接近:) 
} 
} 
 
 //某处稍后：
 Graph< SomeObject> graph = ... 
  

现在至于你想要什么功能，你需要一个更完整的名单。但是，这应该能够帮助您理解如何实现图表。

I have to write up a program that stores verticies into a graph and connect them. The input for the program is given as:

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

From this input, I would store a vertix of (3,5) which are the x and y coordinates. I would then have to connect this coordinate to (5,8).

My question is, how would I go in implementing this graph? I was thinking I would need to store the vertixes in an arraylist or a map, and keep the edges in a list too...but since I'm not given an actual max size of the graph, I'm a little bit lost in the overall implementation. Basically, if you guys could give me an idea how to start this, it'd be sweet as.

解决方案

An easy way to think about graphs is to break them down into their Node and Edge components. (Note: what you call a vertex I call a node. Close enough.)

Let us consider the following options:

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

Now a graph is nothing more than:

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

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

Option 1 is the simplest and easiest to implement. Option 2 gives you some more flexibility, such as adding weights to the edge values.

Now, you have some data at these nodes, correct? For now, let's just have the data be the string representation of the coordinates.

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 = ...

Now as for what functionality you'll want you'd need a more complete list. But this should get you well on your way to understanding how to implement a graph.

这篇关于帮助Java图形实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！