我已经使用哈希图链表实现了一个Graph，我想添加包含边的权重来确定从一个国家到另一个国家的旅行总成本EX：-英国-迪拜60000等
public class Edge {
Vertex from;
Vertex to;
String al;
double weight;
public Edge(Vertex from , Vertex to , String al,double weight)
{
this.from = from;
this.to = to;
this.al = al;
this.weight = weight;
}
public void printEdge()
{
System.out.println(" FROM : " + from.name + " TO : " + to.name + " AirLine name : |"+al+"| " + "PRICE :- " + weight+"LKR");
}
}
public class Vertex {
String name;
public Vertex(String name)
{
this.name = name;
}
}
package GraphTEST;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;
public class Graph {
private Map<Vertex , LinkedHashSet<Vertex>> map = new HashMap<>();
//Arraylist to store the edges
public ArrayList<Edge> edges = new ArrayList<Edge>();
public void addEdge(Vertex n1 , Vertex n2)
{
LinkedHashSet<Vertex> adjacentz = map.get(n1);
if(adjacentz==null)
{
adjacentz = new LinkedHashSet<>();
map.put(n1, adjacentz);
}
adjacentz.add(n2);
}
public void addEDGE(Vertex n1, Vertex n2 , String al, double weight)
{
Edge e = new Edge(n1, n2, al, weight);
edges.add(e);
LinkedHashSet<Vertex> adjacentz = map.get(n1);
if(adjacentz==null)
{
adjacentz = new LinkedHashSet<>();
map.put(n1, adjacentz);
}
adjacentz.add(n2);
}
public void printAll()
{
for(int i =0;i < edges.size() ;i++)
{
edges.get(i).printEdge();
}
}
//------
// public void twoWayVertex(String n1 , String n2)
// {
// addEdge(n1, n2);
// addEdge(n2, n1);
// }
//----------------
public boolean isConnected(Vertex n1 , Vertex n2)
{
Set adjacentt = map.get(n1);
if(adjacentt==null)
{
return false;
}
return adjacentt.contains(n2);
}
public LinkedList<Vertex> adjacentNodesList(Vertex last)
{
LinkedHashSet<Vertex> adjacentyy = map.get(last);
if(adjacentyy==null)
{
return new LinkedList<>();
}
return new LinkedList<Vertex>(adjacentyy);
}
}
package GraphTEST;
import java.util.LinkedList;
public class TestGraph {
static Vertex EN;
static Vertex ST;
//starting and ending FROM --> TO
public static void main(String[] args) {
Graph graph = new Graph();
Vertex v0 = new Vertex("UK");
Vertex v1 = new Vertex("USA");
Vertex v2 = new Vertex("Dubai");
Vertex v3 = new Vertex("Sri Lanka");
Vertex v4 = new Vertex("Australia");
Vertex v5 = new Vertex("Singapore");
Vertex v6 = new Vertex("Malaysia");
Vertex v7 = new Vertex("New Zeland");
// graph.addEdge("UK", "USA");
// graph.addEdge("USA", "UK");
// graph.addEdge("UK", "Dubai");
// graph.addEdge("Dubai", "UK");
// graph.addEdge("Sri Lanka", "UK");
// graph.addEdge("Sri Lanka", "USA");
// graph.addEdge("Dubai", "Sri Lanka");
// graph.addEdge("Sri Lanka", "Dubai");
//
// graph.addEdge("Australia", "Dubai");
// graph.addEdge("Sri Lanka", "Singapore");
// graph.addEdge("Singapore ", "Sri Lanka");
// graph.addEdge("Sri Lanka", "Malaysia");
// graph.addEdge("Singapore", "Malaysia");
// graph.addEdge("Singapore", "Australia");
// graph.addEdge("New Zeland", "Singapore");
// graph.addEdge("Malaysia", "New Zeland");
// graph.addEdge("Australia", "New Zeland");
// graph.addEdge("New Zeland", "Australia");
ST = v3;
EN = v0;
//-----------------------------------------------
graph.addEDGE(v0, v1, "NG", 35000);
graph.addEDGE(v1, v0, "NG", 35000);
graph.addEDGE(v2, v0, "EK", 26000);
graph.addEDGE(v0, v2, "WK", 26000);
graph.addEDGE(v3, v0, "UL", 46000);
graph.addEDGE(v3, v1, "CX", 65000);
graph.addEDGE(v2, v3, "FD", 20000);
graph.addEDGE(v3, v2, "FD", 20000);
graph.addEDGE(v4, v2, "QF", 150000);
graph.addEDGE(v3, v5, "UL", 20000);
graph.addEDGE(v5, v3, "UL", 20000);
graph.addEDGE(v3, v6, "UL", 80000);
graph.addEDGE(v5, v4, "QF", 110000);
graph.addEDGE(v5, v6, "MH", 35000);
graph.addEDGE(v4, v7, "NZ", 43000);
graph.addEDGE(v7, v4, "NZ", 43000);
graph.addEDGE(v7, v5, "NZ", 113000);
graph.addEDGE(v6, v7, "MH", 73000);
System.out.println("========================================================================");
graph.printAll();
System.out.println("========================================================================");
LinkedList<Vertex> visited = new LinkedList<>();
visited.add(ST);
new TestGraph().breadthFirst(graph , visited);
}
public void breadthFirst(Graph graph, LinkedList<Vertex> visited )
{
LinkedList<Vertex> links = graph.adjacentNodesList(visited.getLast());
//CHECK
for(Vertex Link : links)
{
if(visited.contains(Link))
{
//System.out.println(" I_N ");
continue;
}
if(Link.equals(EN))
{
System.out.println("****************");
//System.out.println("IN THE IF");
visited.add(Link);
System.out.println("--");
printPath(visited);
System.out.println("888888888888888888888888");
visited.removeLast();
break;
}
}
//in breadth-first recusrsion needs to come after visiting adjacent nodes
//;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
for (Vertex Link : links) {
if (visited.contains(Link) || Link.equals(EN)) {
continue;
}
visited.addLast(Link);
breadthFirst(graph, visited );
visited.removeLast();
}
//;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
}
public void printPath(LinkedList<Vertex> visited)
{
for(Vertex Link : visited)
{
System.out.print(Link.name);
System.out.print(" ");
}
System.out.println();
}
}
这是我的代码，它有四个类1） Edge2） 顶点3） Graph4） 测试图
在testGraph类中，有一个"广度优先搜索"的方法，它将列出从一个地方到另一个的所有可能的方法
我的任务是使这个程序出每个路径的成本以及
如果有人能帮我做这件事，我将不胜感激
应该这样做：
public void traverseBreadthFirst( Graph graph, Vertex startVertex,
LinkedList<Vertex> visitedVertices )
{
LinkedList<Vertex> adjacentVertices = graph.getAdjacentVertices( startVertex );
for( Vertex visitedVertex : visitedVertices )
{
if( adjacentVertices.contains( visitedVertex ) )
adjacentVertices.remove( visitedVertex );
}
for( Vertex adjacentVertex : adjacentVertices )
visitedVertices.addLast( adjacentVertex );
for( Vertex adjacentVertex : adjacentVertices )
breadthFirst( graph, adjacentVertex, visitedVertices );
}