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 にするには 2 回のクリックが必要です。

だから、これは私が私の方法のために持っているコードです:

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です。

4

1 に答える 1

2

現時点では、baseIndex から searchIndex への複数のパスが存在する可能性を考慮していません。おそらく、この場合は最短パスが必要です。これを修正する 1 つの方法は、ネストされた 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 はコメントで、グラフ内のサイクルがスタック オーバーフローを引き起こす可能性があることを指摘しました。マップ内のキーの数を超えてはならないため、Integer.MAX_VALUEif extends を返すことでこれを修正しました。countindexToIndecies.size()count

于 2013-08-07T03:20:52.623 に答える