java - java中使用hashmap的有向图

Question

我使用Map数据结构在java中实现了有向图。

目前，我有两个 Map 数据结构:

1. 保存每个节点以及所有入度顶点。
2. 保存每个节点以及所有出度顶点。

我的问题如下: 我想实现一个最短路径算法，给定一个特定节点和一个辅助节点，找到第一个节点到第二个节点之间的最短路径。

我不知道如何使用Map数据结构来实现它。

public class NetworkInfluence {
private int numEdges; //number of edges
private int numVert;  //number of vertices
private int numIter;  //number of page rank iterations
private Map<String, List<String>> AtoB; //out degree of vertices
private Map<String, List<String>> BtoA; //in degree of vertices
private Map<String, Double> influenceMap;  //page ranks of vertices
private Set<String> nodeCounter;        //list of vertices

/**
 * Creates a new PageRank object.  This is used to find the pagerank
 * of a graph represented as an edgelist in a text file.
 * @param fileName Name of text file containing graph edge list.
 * @param eps Convergence parameter for pagerank.
 * @throws FileNotFoundException If text file containing graph cannot be found.
 * @throws IOException If error reading a text file.
 */
public NetworkInfluence(String fileName) throws FileNotFoundException, IOException {
    numIter = 0;
    numEdges = 0;
    AtoB = new HashMap<String, List<String>>();
    BtoA = new HashMap<String, List<String>>();
    Set<String> nodeCounter = new HashSet<String>();

    FileReader fr = new FileReader(fileName);
    BufferedReader b = new BufferedReader(fr);

    String line = b.readLine();
    String nodes[];
    List<String> toList;
    List<String> fromList;
    while((line = b.readLine()) != null) { 
        numEdges++;
        nodes = line.toLowerCase().split(" ");

        //A->B
        if(!AtoB.containsKey(nodes[0])) {
            toList = new ArrayList<String>();
            toList.add(nodes[1]);

            AtoB.put(nodes[0], toList);
        } else {
            toList = AtoB.get(nodes[0]);
            toList.add(nodes[1]);

            AtoB.put(nodes[0], toList);
        }
        //B->A
        if(!BtoA.containsKey(nodes[1])) {
            fromList = new ArrayList<String>();
            fromList.add(nodes[0]);

            BtoA.put(nodes[1], fromList);
        } else {
            fromList = BtoA.get(nodes[1]);
            fromList.add(nodes[0]);

            BtoA.put(nodes[1], fromList);
        }
        nodeCounter.add(nodes[0]);
        nodeCounter.add(nodes[1]);
    }
    this.nodeCounter = nodeCounter;
    numVert = nodeCounter.size();
    b.close();

如有任何帮助，我们将不胜感激。谢谢。

Answer 1

如上所述，即使您使用 HashMap ，您也可以使用 dijkstra 解决它。除了结构之外，您还必须以某种方式计算边缘的成本，如下所示:

Map<String, Map<String, Integer>> costs = new HashMap<>();
...
// where the cost of edge ("node0", "node1") is:
int cost = costs.get("node0").get("node1");

od dijkstra 部分可能是这样的(我不关心优化 map 访问):

public List<String> path(String node0, String node1) {
        // array to keep trace of visited nodes
        Map<String, Boolean> visited = new HashMap<>();
        // array to keep trace of predecessors of nodes in the path
        Map<String, String> pred = new HashMap<>();
        // initialize maps
        for (String n : nodeCounter) {
            visited.put(n, false);
            pred.put(n, node0);
        }

        // min costs from node0 to any other node, initialized to INFINITE if
        // the nodes are not adjacent
        Map<String, Integer> mincosts = new HashMap<>();
        for (String n : nodeCounter)
            mincosts.put(n, costs.get(node0).get(n));

        // initialize flags of start node
        visited.put(node0, true);
        mincosts.put(node0, 0);

        // iterate until all vertexes or node1 are reached
        for (int i = 0; (i < numVert) && (!visited.get(node1)); ++i) {
            int min = inf;
            String candidate = null;
            for (String n : nodeCounter)
                if (!visited.get(n) && mincosts.get(n) < min) {
                    min = mincosts.get(n);
                    candidate = n;
                }
            if (candidate == null)
                break;
            visited.put(candidate, true);

            for (String n : nodeCounter)
                if (!visited.get(n) && ((mincosts.get(candidate) + costs.get(candidate).get(n)) < mincosts.get(n))) {
                    mincosts.put(n, mincosts.get(candidate) + costs.get(candidate).get(n));
                    pred.put(n, candidate);
                }
        }

        if (!visited.get(node1))
            return null;

        // store the path from node1 to node0, using predecessors
        // map
        String current = node1;
        List<String> path = new ArrayList<>();
        path.add(current);
        while (!current.equals(node0))
            path.add(current = pred.get(current));

        // store the path from node0 to node1
        Collections.reverse(path);

        return path;
    }

实际上，如果您还可以使用第三个库，我建议您寻找像JGraphT这样的图形java库，并使用给定的函数求最小路径。例如here是 Dijkstra JGraphT API 的引用。