java - 如何在java中表示无向加权图

Question

我正在对图进行一些研究，因为这不完全是我的研究领域，我真的很难表示一个无向加权图，但我认为我遵循了错误的想法，请遵循一些代码:

public class Vertex { // Nothing really new here...
    private String label;

    public Vertex(String pageObject) {
        this.label = pageObject;
    }
    // blabla.
}

我认为这是我开始做错事的地方:

public class Edge {
    private String source; //Source? if it's bidirectional It's not supposed to have a source, or am I wrong? Like it's source looking from the starting point?
    private int weight;
    private String destination; //Same thing here.

    public Edge(String source, int weight, String destination) {
        this.source = source;
        this.weight = weight;
        this.destination = destination;
    }
}

在这里，我真的迷路了:

public class Graph { // Really struggling to represent it here.
    private Map<Vertex, List<Edge>> adjVertices;
}
// I think the wrong idea about the graph above may lead to results like this below, and it seems wrong, like Earth being the key, and also the source...
// Just an example:
{  
   "Earth":{  
      "source":"Earth",
      "weight":150,
      "destination":"Jupiter"
   }
}

几乎每个示例都与有向图相关，因此我需要一些关于如何纠正或从零开始的说明。

Answer 1

有许多不同的方式来表示顶点、边和图。这是一个过于简化的:

定义方向边:

class Edge {

    private Vertex to; 
    private int weight;

    public Edge(Vertex to, int weight) {
        super();
        this.to = to;
        this.weight = weight;
    }

    Vertex getTo() {
        return to;
    }

    int getWeight() {
        return weight;
    }   

    //todo override hashCode()
}

定义一个顶点，以便每个顶点都有其邻居的边集合:

class Vertex { 

    private String label;
    private Set<Edge> edges; //collection of edges to neighbors 

    public Vertex(String pageObject) {
        this.label = pageObject;
        edges = new HashSet<>();
    }

    String getLabel() {
        return label;
    }

    boolean addEdge(Edge edge){
        return edges.add(edge);
    }

    List<Edge> getEdges() {
        return new ArrayList<>(edges);
    }

    //todo override hashCode()
}

定义一个具有 Vertex 对象集合的 Graph:

class Graph{

    private Set<Vertex> vertices; //collection of all verices 

    public Graph() {
        vertices = new HashSet<>();
    } 

    List<Vertex> getVertices() {
        return new ArrayList<>(vertices);
    }   

    boolean addVertex(Vertex vertex){
        return vertices.add(vertex);
    }
}

构建图表:

public static void main(String[] args) {

    Graph graph = new Graph();

    //construct vertices 
    Vertex v1 = new Vertex("1"); 
    Vertex v2 = new Vertex("2"); 
    Vertex v3 = new Vertex("3");
    Vertex v4 = new Vertex("4");
    Vertex v5 = new Vertex("5");

    //to make the graph un directed use the same weight 
    //both ways 
    v1.addEdge(new Edge(v2, 1)); //connect v1 v2 
    v2.addEdge(new Edge(v1, 1));   

    v2.addEdge(new Edge(v3, 2)); //connect v2 v3
    v3.addEdge(new Edge(v2, 2));

    v2.addEdge(new Edge(v4, 3)); //connect v2 v4
    v4.addEdge(new Edge(v2, 3));

    v4.addEdge(new Edge(v5, 1)); //connect v4 v5
    v5.addEdge(new Edge(v4, 1));

     graph.addVertex(v1); graph.addVertex(v2); graph.addVertex(v3);
     graph.addVertex(v4); graph.addVertex(v5);  
}