我正在做一些关于图的研究,因为这不完全是我的研究领域,我确实在努力代表无向加权图,但是我认为我遵循错误的思路,请遵循以下代码:
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"
}
}
几乎每个示例都与有向图有关,因此我需要对如何更正或从零开始进行修正有所了解。
最佳答案
表示顶点,边和图的方式有很多。这是一个过于简化的例子:
定义方向性Edge:
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
的集合: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()
}
定义一个具有顶点对象集合的图:
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);
}