广度优先搜索加权有向图

Question

我需要帮助为我的 BFS 算法添加边成本。我不知道如何为添加到路径中的每个顶点添加边成本。我将post代码供大家参考。给我一些建议。

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);
        }
    }

我的问题是如何将 edgecost 添加到 bfs 部分的代码中，并在执行时提供从源到目的地的路径成本。

Answer 1

到 return 路径和成本，您需要创建一个 class 来保存这两个值：

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;
    }
}

您的搜索应该 return 来自 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 拆分得更多，您的代码将更具可读性。

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;
}

完成后，您会发现在何处添加与特定 class 相关的逻辑变得更加明显，并且您需要的数据将在您需要时可用。例如，现在可以轻松地将 Path 转换为总成本：

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

与必须四处传递原始图形以查找边的成本相比，这是更简洁的代码。

广度优先搜索加权有向图

Breadth first search for weighted directed graph

java

algorithm

breadth-first-search