如何在Java中表示无向加权图 [英] How to represent an undirected weighted graph in java

问题描述

我正在做一些关于图的研究，因为这不完全是我的研究领域，我真的很努力地表示无向加权图，但是我认为我遵循错误的思路，请遵循一些代码:

I'm doing some study about graphs, as it's not exactly my field of study, I'm really struggling to represent an undirected weighted graph, but I think I'm following the wrong idea, follow some code:

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

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

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

Here I think is where I start doing things wrong:

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

在这里，我真的迷路了:

And here, I'm really lost:

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"
   }
}

几乎每个示例都与有向图有关，因此我需要对如何纠正或从零开始进行一些了解.

Almost every example is related to directed graphs, so I need some light on how to correct or do it from zero.

推荐答案

有很多不同的方式来表示顶点，边和图形.这是一个过于简化的例子:

There are many different way to represent vertices, edges and a graph. Here is an over-simplified one:

定义方向性边线:

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()
}

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

Define a Vertex so that each vertex has a collection of Edges to its neighbors:

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()
}

定义一个具有顶点对象集合的图:

Define a Graph which has a collection of Vertex objects:

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

这篇关于如何在Java中表示无向加权图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！