1

私は次の問題を理解することができません。ポイント1では、ポイント2またはポイント5に移動できます。ポイントから3または4に移動できます。ポイント5から6または7に移動できます。7から9へのパスは1つだけです。すべてのフルパスを計算します。私は最速のルートか何かを探していません。簡単にたどることができる方法で、そこにあるすべてのパスが必要です。

2つの質問があります：

  1. オプションを「保存」する正しい方法を使用しているかどうかわかりません（a [1] = [2,5]）。これは大丈夫ですか、それとももっと良い方法がありますか？

  2. これを解決する方法がわかりません。誰かが私に手がかりを与えることができますか？私は正しい方向を見ていることを望んでいます:-)

パス：

  1 ->2 ->3
        ->4
    ->5 ->6
        ->7 ->8 ->9

そして望ましい結果：

 1,2,3
 1,2,4
 1,5,6
 1,5,7,8,9

javascriptでこれを解決する私の試み

// this doesn't do what I need 
var a = [];
a[1]=[2,5];    
a[2]=[3,4];
a[5]=[6,7];
a[7]=[8];
a[8]=[9];

trytoloop(a,1);

function trytoloop(a,key){
    if(a[key]){
         for (var y in a[key]){
                document.write(key);

                trytoloop(a,a[key][y]);
         }
    } else {
        document.write(key);
    }
}
4

4 に答える 4

2

以下に解決策を示しますが、ネタバレが欲しくない場合は見ないでください！グラフにサイクルがない場合のみを扱います。

答えを出さずにいくつかのヒント：再帰関数では、現在の場所だけでなく、2番目の引数でこれまでのパス全体を追跡することをお勧めします。そうしないと、訪問した場所のリストが表示されますが、それぞれにたどり着くまでの道のりをどうやって知るのですか？次に、Javascriptでは、for ... in構造体を使用して配列を反復処理することは適切な方法とは見なされないため、0から配列の長さまでの通常のforループを使用できます。第3に、構築されたパスをある時点で印刷する必要がありますが、すべてのステップで印刷する必要はありません。代わりに、完了時にパスを印刷する必要があります。つまり、現在の場所から移動する場所がなくなったときです。最後に、私は信じているので、に置き換えdocument.writeましたconsole.logdocument.write何かを印刷するたびにドキュメントの内容が上書きされます。

var a = [];
a[1]=[2,5];
a[2]=[3,4];
a[5]=[6,7];
a[7]=[8,9];

trytoloop(a,[1]);

function trytoloop(a,path){
  var last = path[path.length - 1];
  var next_hops = a[last];
  // if there could be cycles, you might want to check that next_hops doesn't
  // contain any already visited locations
  if (next_hops) {
    for (var i = 0; i < next_hops.length; i++) {
      var new_path = path.concat([next_hops[i]]);
      trytoloop(a, new_path);
    }
  } else {
    console.log(path);
  }
}
于 2012-12-09T19:51:48.933 に答える
2

これまでに構築した部分的なパスを追跡しません。ただし、配列のアイデアは問題ないようです。これは、いくつかのより意味のある名前を持つ作業バージョンです：http: //jsfiddle.net/YkH5b/。

// A cleaner way of defining the next keys
var nextKeysMap = {
    1: [2, 5],    
    2: [3, 4],
    5: [6, 7],
    7: [8],
    8: [9]
};

var fullPaths = [];
generateFullPaths([1], 1);  // start off with partial path [1] and thus at key 1

function generateFullPaths(partialPath, currentKey) {
    if(currentKey in nextKeysMap) {  // can we go further?
        var nextKeys = nextKeysMap[currentKey];  // all possible next keys
        for (var i = 0; i < nextKeys.length; i++) {  // loop over them
            var nextKey = nextKeys[i];
            // append the current key, and build the path further
            generateFullPaths(partialPath.concat(nextKey), nextKey);
         }
    } else {  // we cannot go further, so this is a full path
        fullPaths.push(partialPath);
    }
}

for(var i = 0; i < fullPaths.length; i++) {
    console.log(fullPaths[i].join(","));
}
于 2012-12-09T19:51:55.277 に答える
1

私はこれを試していませんが、頭のてっぺんから、これらの線に沿って何かを試すことができます：

// use an object, and set the numbers as keys and the values as the child options
var a = {};
a[1] = {2:{3:{},4:{}},5:{6:{},7:{8:{9:{}}}}};

(function trytoloop(obj,num,str){
    if(str.length>0) str += ',';
    str += num
    if(Object.keys(obj).length==0) document.writeln(str+'<br />');
    else for(var key in obj) trytoloop(obj[key],key,str);
})(a[1],1,'');
于 2012-12-09T20:00:55.707 に答える
1

これが私の解決策です：フィドル

最終出力はにconsole送られ、ここで初期ノードを変更できますconsole.log(getPaths(1));（要件に応じてノード1から開始します）。

于 2012-12-09T20:09:31.450 に答える