2

我有一个LinkedHashMap这样 的

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

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

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

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

}

工作正常如果 ThebaseIndex和seachIndex我给它有关联，但是如果没有，我不确定如何抓住它......任何帮助将不胜感激。

4

1 回答 1

2

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

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则找不到路径。

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

编辑：SimonC 在评论中指出，图中的循环可能会导致堆栈溢出。我已经通过返回Integer.MAX_VALUEif beyond 来纠正这个问题，因为不应该超过地图中的键数count。indexToIndecies.size()count

于 2013-08-07T03:20:52.623 回答