廣度優先搜索加權有向圖

Question

我需要幫助爲我的BFS算法添加邊緣成本。我不知道如何爲要添加到路徑的每個頂點添加邊緣成本。我會發布代碼供您參考。提供一些建議。

Graph.java

package algo; 
import java.util.*; 


public class Graph 
{ 
    private static Map<String, LinkedHashSet<HashMap<String, Double>>> map; 
    private ArrayList<String> nodes = new ArrayList<String>(); 
    private static ArrayList<String> shortestPath = new ArrayList<String>(); 
    public Graph() 
    { 

    } 

    public Graph(String[] nodes) 
    { 
     map = new HashMap<String,LinkedHashSet<HashMap<String, Double>>>(); 
     for(int i=0;i<nodes.length;++i) 
      map.put(nodes[i], new LinkedHashSet<HashMap<String, Double>>()); 
    } 

    public void addNeighbor(String node1,String node2, Double edgeCost) 
    { 
     LinkedHashSet<HashMap<String, Double>> adjacent = map.get(node1); 
     HashMap<String, Double> innerMap = new HashMap<String, Double>(); 
     if(map.get(node1)==null) 
     { 
      adjacent = new LinkedHashSet<HashMap<String, Double>>();      
      map.put(node1, adjacent); 
     } 
     innerMap.put(node2, edgeCost); 
     adjacent.add(innerMap); 
    } 

    public boolean memberOf(String node) { 
     return nodes.contains(node); 
    } 

    public LinkedList<HashMap<String, Double>> getNeighbours(String node) { 
     LinkedHashSet<HashMap<String, Double>> adjacent = map.get(node); 
     if(adjacent==null) { 
      return new LinkedList<HashMap<String, Double>>(); 
     } 
     return new LinkedList<HashMap<String, Double>>(adjacent); 
    } 

    protected void storeNodes(String source, String destination) 
    { 
     if (!source.equals(destination)) 
     { 
      if (!nodes.contains(destination)) 
      { 
       nodes.add(destination); 
      } 
     } 
     if (!nodes.contains(source)) { 
      nodes.add(source); 
     } 
    } 

    public void getKeyValuePairs() 
    { 
     Iterator<String> iterator = map.keySet().iterator(); 

     while (iterator.hasNext()) 
     { 
      String key = iterator.next().toString(); 
      LinkedHashSet<HashMap<String, Double>> value = map.get(key); 
      System.out.println(key + " " + value); 
     } 
    } 
} 

Main.java

package algo; 
import java.io.*; 

public class Main { 

    public static void main(String[] args) throws IOException 
    { 
     File file = new File("city.txt"); 
     FileReader fr = new FileReader(file); 
     BufferedReader br = new BufferedReader(fr); 
     String line = br.readLine(); 
     String [] tokens = line.split("\\s+"); 
     String [] nodes = new String[tokens.length]; 

     for (int i = 0; i < nodes.length; ++i) { 
      nodes[i] = tokens[i]; 
     } 
     Graph g = new Graph(nodes); 
     String var_1 = tokens[0]; 
     String var_2 = tokens[1]; 
     Double var_3 = Double.parseDouble(tokens[2]); 
     g.addNeighbor(var_1, var_2,var_3); 
     while((line = br.readLine())!=null) 
     { 
      tokens = line.split("\\s+"); 
      nodes = new String[tokens.length]; 
      for (int i = 0; i < nodes.length; ++i) { 
       nodes[i] = tokens[i]; 
      } 

      //Graph g = new Graph(nodes); 
      var_1 = tokens[0]; 
      var_2 = tokens[1]; 
      var_3 = Double.parseDouble(tokens[2]); 
      g.addNeighbor(var_1, var_2,var_3); 
      g.storeNodes(var_1, var_2); 
     } 
     g.getKeyValuePairs(); 
     br.close(); 
    } 

} 

city.txt

city1 city2 5.5 
city1 city3 6 
city2 city1 16 
city2 city3 26 
city2 city4 15.5 
city2 city5 7 
city3 city4 9 
city3 city5 5 
city4 city1 3.6 
city4 city2 4 
city5 city2 7.9 
city5 city3 5 

這是我的BFS的我的代碼部分，我有不添加任何edgecost測試

public static ArrayList<String> breadthFirstSearch(Graph graph, 
      String source, 
      String destination) 
    { 
     shortestPath.clear(); 

     // A list that stores the path. 
     ArrayList<String> path = new ArrayList<String>(); 

     // If the source is the same as destination, I'm done. 
     if (source.equals(destination) && graph.memberOf(source)) 
     { 
      path.add(source); 
      return path; 
     } 
     // A queue to store the visited nodes. 
     ArrayDeque<String> queue = new ArrayDeque<String>(); 

     // A queue to store the visited nodes. 
     ArrayDeque<String> visited = new ArrayDeque<String>(); 

     queue.offer(source); 
     while (!queue.isEmpty()) { 
      String vertex = queue.poll(); 
      visited.offer(vertex); 

      ArrayList<String> neighboursList = (ArrayList<String>) graph.getNeighbours(vertex); 
      int index = 0; 
      int neighboursSize = neighboursList.size(); 
      while (index != neighboursSize) { 
       String neighbour = neighboursList.get(index); 

       path.add(neighbour); 
       path.add(vertex); 

       if (neighbour.equals(destination)) { 
        return processPath(source, destination, path); 
       } else { 
        if (!visited.contains(neighbour)) { 
         queue.offer(neighbour); 
        } 
       } 
       index++; 
      } 
     } 
     return null; 
    } 

    public static ArrayList<String> processPath(String src, 
               String destination, 
               ArrayList<String> path) 
    { 

     // Finds out where the destination node directly comes from. 
     int index = path.indexOf(destination); 
     String source = path.get(index + 1); 

     // Adds the destination node to the shortestPath. 
     shortestPath.add(0, destination); 

     if (source.equals(src)) { 
     // The original source node is found. 
     shortestPath.add(0, src); 
     return shortestPath; 
     } else { 
     // We find where the source node of the destination node 
     // comes from. 
     // We then set the source node to be the destination node. 
     return processPath(src, source, path); 
     } 
    } 

我的問題是如何將邊緣代碼添加到bfs部分的代碼中，並在執行時提供從源到目標的路徑開銷。

Answer 1

要返回的路徑，你需要創建一個類的費用，以保持這兩個值：然後

class CostedPath { 
    private final List<String> path = new ArrayList<>(); 
    private double cost = 0.0; 

    public CostedPath(String start) { 
     path.add(start); 
    } 

    public CostedPath addNode(String node, Graph graph) { 
     this.cost += graph.getCost(path.get(0), node); 
     path.add(0, node); 
     return this; 
    } 
} 

你的搜索應該從processPath返回CostedPath。

private CostedPath processPath(String start, String end, List<String> path, Graph graph) { 
{ 
    String previous = path.get(path.indexOf(end) + 1); 
    if (previous.equals(start)) 
     return new CostedPath(start); 
    else 
     return processPath(start, previous, path, graph).addNode(end, graph); 
} 

如果您將課程分爲更多類型，您的代碼將更具可讀性。

class Vertex { 
    private final String name; 
    private final Set<Edge> edges; 
} 

class Edge { 
    private final Vertex end; 
    private final double cost; 
} 

class Graph { 
    private final Set<Vertex> vertices; 
} 

class Path { 
    private final Vertex start; 
    private final List<Edge> edges; 
} 

一旦你這樣做，你會發現這是一個很大較爲明顯，其中以添加的有關特定類的，你需要的時候你需要它會提供的數據邏輯。例如，它現在微不足道的一個Path轉換爲總成本：

public double getCost() { 
    return edges.stream().mapToDouble(Edge::getCost).sum(); 
} 

這比通過圍繞原始圖找到一個邊的成本更清潔的代碼。