我已经使用哈希图链接列表实现了一个图，并且我想添加包含权重的边，以确定从一个国家到另一个国家旅行的总费用
例如：-英国-迪拜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）边缘
2）顶点
3）图
4）测试图
在testGraph类中，存在用于“ BreadthfirstSearch”的方法，该方法将提出从一个地方到另一个地方的所有可能方法
我的任务是使该程序也花费每条路径的成本
如果有人可以帮助我做到这一点，我将不胜感激
比
最佳答案
这样的事情应该做到：
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 );
}
关于java - 如何进行广度优先搜索，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28577301/