如何在java中表示无向加权图
有许多不同的方法来表示顶点,边和图。这是一个过于简化的:
定义方向边:
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()
} 定义一个顶点,以便每个顶点都有一个Edges 的集合到它的:
class Vertex {
private String label;
private Set 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 getEdges() {
return new ArrayList<>(edges);
}
//todo override hashCode()
} 定义一个包含Vertex对象集合的Graph:
class Graph{
private Set vertices; //collection of all verices
public Graph() {
vertices = new HashSet<>();
}
List 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');
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);
}
赞0
踩0