Java：递归搜索函数

Question

我通过HashMap创建一个无向和无权重的图

然后，我想找到节点之间的所有最短路径。我的想法是检查源节点的所有邻居是否是目标节点的邻居。如果没有，它将检查源节点的邻居的邻居。

我想检查所有黄色节点，然后检查绿色节点，直到找到目的地的邻居。但是，当我尝试使用同时循环和递归函数来查找最短路径时，它将检查第一个黄色节点，然后检查第一个绿色节点。

我如何解决它？

还是我的想法其实是错的？

这是我的密码。inputData用于从txt文件获取数据。

static Map<Integer, HashSet<Integer>> graph = new HashMap<Integer, HashSet<Integer>>();


public static void inputData(Integer k, Integer v) {
        if (graph.containsKey(k)) {
            HashSet<Integer> s = new HashSet<Integer>(graph.get(k));
            s.add(v);
            graph.put(k, s);
        }
        else {
            HashSet<Integer> s = new HashSet<Integer>();
            s.add(v);
            graph.put(k, s);
        }
        if (graph.containsKey(v)) {
            HashSet<Integer> s = new HashSet<Integer>(graph.get(v));
            s.add(k);
            graph.put(v, s);
        }
        else {
            HashSet<Integer> s = new HashSet<Integer>();
            s.add(k);
            graph.put(v, s);
        }
    }


public static void findAllShortestPaths() {`

        for (Integer key : graph.keySet()) {
            Iterator it = graph.entrySet().iterator();
            while (it.hasNext()) {
                Integer k = (Integer) it.next();
                if (k == key) {
                    break;
                }
            }

            while (it.hasNext()) {
                Integer k = (Integer) it.next();
                if (!(isNeighbour(key, k))) {
                    findShortestPaths(key, k);
                }
            }
        }
    }

public static void findShortestPaths(Integer source, Integer dest) {

        HashSet<Integer> sp = new HashSet<Integer>(graph.get(source));
        if (!(isNeighbor(source, dest))) {
            Iterator it = sp.iterator();
            boolean isfound = false;

            while (!isfound) {

                while (it.hasNext()) {
                    if (isNeighbor((Integer) it.next(), dest)) {
                        isfound = true;
                    }
                }
            }


        }
    }




Answer 1

首先，HashMap是无序的。因此，不可能按特定顺序解析节点。

您可以使用类来创建图形结构。就像你在做BFS一样。

class Node {
    List<Node> adjacentNodes;
}

您可以迭代相邻节点的列表。因为名单将维持秩序。