java - 使用嵌套 for 循环搜索 LinkedHashMap

Question

我有一个像这样的LinkedHashMap

LinkedHashMap <Integer, ArrayList<Integer>> indexToIndecies = new LinkedHashMap <Integer ,ArrayList<Integer>>();

我有一个方法public int searchGraph(int baseIndex, int searchIndex, int count)

这种搜索方法的要点是；当有人输入 baseIndex 时，这是一个键，它必须找出需要多少次“点击”才能到达 searchIndex。键的值是它们相关的索引。所以“点击”将从一个键转到另一个键。所以如果我的 hashmap 看起来像:

0[2]
1[0, 3]
2[0, 5]
3[0, 2, 4, 5]
4[5]
5[2]
6[3, 4, 5]
7[1, 4]

从 0 到 5 需要点击两次。

所以这是我的方法代码:

public int searchGraph(int baseIndex, int searchIndex, int count)
{
    if (baseIndex == searchIndex)
    {

        return count;
    }
    if (searchIndex > indexToIndecies.size()-1){

        return -3;
    }
    else{

        for (int i = 0; i < indexToIndecies.get(baseIndex).size(); i++)
        {
            for (int x = 0; x< indexToIndecies.get(baseIndex).size(); x++){

                if (indexToIndecies.get(baseIndex).get(x) == searchIndex){

                    return count;
                }
                else{
                    count++;
                }

            }

            baseIndex = (indexToIndecies.get(baseIndex)).get(i);            

        }

        return count;
    }

}

工作正常如果 baseIndex 和 seachIndex 我给它有一个关联，但是如果没有，我不知道如何捕获它......任何帮助将不胜感激。

Answer 1

现在您没有考虑从 baseIndex 到 searchIndex 可能存在多条路径的可能性 - 如果是这种情况，您可能需要最短路径。纠正此问题的一种方法是将嵌套的 for 循环替换为围绕递归调用的单个 for 循环。如果未找到路径，则返回 Integer.MAX_VALUE，然后如果您的最短路径的计数为 Integer.MAX_VALUE，那么您将知道您无法找到找到一条路。 (如果您确实找到了一条计数为 Integer.MAX_VALUE 的路径，那么您的路径查找算法可能出了问题 - 您不应该有那么长的路径。)如果您想使用嵌套循环而不是递归，那么您可以使用自己的堆栈变量将递归调用转换为循环。

public int searchGraph(int baseIndex, int searchIndex, int count) {
    if(baseIndex == searchIndex) {
        return count;
    } else if(count > indexToIndecies.size()) {
        return Integer.MAX_VALUE; // cycle in graph
    } else {
        int returnVal = Integer.MAX_VALUE;
        for(int i = 0; i < indexToIndecies.get(baseIndex).size(); i++) {
            int temp = searchGraph(indexToIndecies.get(baseIndex).get(i), searchIndex, count + 1);
            returnVal = temp < returnVal ? temp : returnVal;
        }
        return returnVal;
    }
}

这应该返回最短路径，如果它返回 Integer.MAX_VALUE，则表示找不到路径。

另一种选择是返回 Integer 而不是 int，在这种情况下，您可以在找不到路径的情况下返回 null。

编辑:SimonC 在评论中指出图中的循环可能导致堆栈溢出。如果 count 超过 indexToIndecies.size()，我已经通过返回 Integer.MAX_VALUE 来纠正这个问题，因为 count不应超过映射中键的数量。