1

グラフ内の 2 つのノード間のすべてのパスを見つけるアルゴリズムに取り組んでいます。それだけです。次のように、文字列の配列内のすべてのパスをエンコードできました。

String []paths = new String[50];

注: パスを格納するために文字列の配列を使用していますが、必要に応じて他のデータ構造に格納できます。

私の配列のデータのサンプルは、以下の表のようなものになります。文字は私のデータであり、ハイフンは視覚化のみに使用されることに注意してください。

 -----------
| A | B | C |
 -----------
| D | E |   |
 -----------

上記の配列を処理し、すべての組み合わせを次のように出力するだけです。

ABC

AEC

DBC

DEC

反復アプローチ「ループ」を使用してこの問題を解決しようとしましたが、失敗しました。再帰でこれを行うかもしれないと思いますが、それを行う方法がわかりません。また、この問題を処理するデータ構造があるかどうかもわかりません。文字列の配列ではなく、パスを保存する方が良いでしょうか?

とにかく、ここに私がループで取り組んでいるものがあります：

String []temp = new String[100];
for( r=0; r<paths.length ;r++ )
   for( c=0; c<paths[r].length() ;c++ )
      for( j=c+1; j<paths[r].length() ;j+1 )
         temp[r] += paths[j];
4

1 に答える 1

1

したがって、正規表現[AD][BE][C].

それもより良いデータ構造になります: 配列を 90 度回転させます。これにより、長さ (ABC と DE) のチェックが不要になります。

それにもかかわらず、あなたのデータ構造では:

int maxPathLength = 3; // TODO calculate
Set<String> results = new TreeSet<String>();
process(paths, "", 0);

public void process(String[] paths, String prefix, int i, Set<String> results) {
    if (i >= maxPathLength) {
        System.out.println(prefix);
        results.add(prefix);
        return;
    }
    for (String s : paths) {
         if (i < s.length()) {
             process(paths, prefix + s.charAt(i), i + 1, results);
         }
    }
}
于 2012-12-15T04:10:29.773 に答える