时间戳

首页 > 解决方案 > Java：递归搜索函数

java - Java：递归搜索函数

问题描述

我创建了一个无向且未加权的图HashMap<Integer,HashSet<Integer>>。HashMap的key是节点的编号，map的值是节点的邻居。

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

例如 在此处输入图像描述

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

我该如何解决？

还是我的想法实际上是错误的？

这是我的代码。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;
                    }
                }
            }


        }
    }

标签： java

解决方案

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

您可以使用类来创建图形结构。当你在做 BFS 之类的事情时。

class Node {
    List<Node> adjacentNodes;
}

您可以迭代相邻节点的列表。由于列表将保持顺序。

推荐阅读