-2

Java で 2D 整数配列 (ArrayList ではない) の内容をソートする際に問題があります。私の問題配列path_info[ ][ ]は次のようになります。

Node_x Node_y Path_ID Port_x Port_y
  4      6      500     3       2
  6      8      500     3       2      
  4      9      501     2       3
  9      3      501     2       2      
  2      3      502     3       2      
  1      5      503     2       3 
  5      2      503     2       2

各行は、Port_x から Port_y までの Path_ID 上の node_x から node_y を意味します。各パスは、テーブル内の 1 つ以上の行になる場合があることに注意してください。

この配列は、無向重み付けなしグラフのノード 8 からノード 1 に到達するためのルーティング アルゴリズムの結果の配列です。

送信元ノードから宛先ノードに到達すること。たとえば、テーブルのノード 8 からノード 1 の場合、path_ID は 500、501、502、および 503 です (PATH_ID は列 で既にソートされていますPath_ID)。問題は、ソース ノードが列 "Node_x" の最初のノードであり、宛先ノードが列 "Node_y" の最後のノードになるように、この配列を並べ替えたいことです。そして、すべての中間の行と列が適切にソートされました。

結果の配列は次のようになります (ソース ノードが 8 で宛先ノードが 1 の場合)。

Node_x Node_y Path_ID Port_x Port_y
  8      6      500     2      3
  6      4      500     2      3     
  4      9      501     2      3
  9      3      501     2      2
  3      2      502     2      3
  2      5      503     2      2
  5      1      503     3      2

まだコードを書き始めていないので、貼り付けるスニペットがありません。私はまだこれを達成する方法を理解しようとしています。誰か助けてくれませんか？

4

2 に答える 2

1

Arrays.sort()1 次元配列 (2D 配列の要素) で動作するカスタム コンパレータと共に使用します。

于 2012-12-13T19:10:15.480 に答える
0

アルゴリズムが正しく機能したと仮定すると、同じノードに複数回アクセスすることはありません。したがって、貪欲に適切なノードを探すことができますが、絶え間なくループしないように適切なデータ構造が必要です。このコードは、 、および であると想定しpath_info[index][0]てnode_xいpath_info[index][1]ますnode_y。O(n)各ループに間に合うように実行される、次のようなものを試してください。

import java.util.*;

public class GraphSorter {
  public static void main(String[] args) {
    int[][] graph = new int[][]{{9, 3}, {6, 4}, {3, 2}, {8, 6}, {5, 1}, {4, 9}, {2, 5} }; 
    LinkedList<int[]> myList = path(graph, 8);
    for (int[] edge : myList) {
      System.out.println(Arrays.toString(edge));
    }
  }

  public static LinkedList<int[]> path(int[][] path_info, int source) {
    HashMap<Integer, int[]> nodeXmap = new HashMap<Integer, int[]>();
    HashMap<Integer, int[]> nodeYmap = new HashMap<Integer, int[]>();
    LinkedList<int[]> foundPath = new LinkedList<int[]>();

    for(int i = 0; i < path_info.length; i++) {
      // We already found an edge with this node_x edge, turn it around
      if(nodeXmap.containsKey(path_info[i][0])) {
        int tmp = path_info[i][0];
        path_info[i][0] = path_info[i][1];
        path_info[i][1] = tmp;
      }
      nodeXmap.put(path_info[i][0], path_info[i]);
      nodeYmap.put(path_info[i][1], path_info[i]);
    }

    int current = source;
    // Use our maps to lookup where the next edge exists in our path,
    // since our input is guaranteed to be unique
    for(int i = 0; i < path_info.length; i++) {
      int[] currentEdge = nodeXmap.get(current);
      if (currentEdge == null) {
        currentEdge = nodeYmap.get(current);
        current = currentEdge[0];
      } else {
        current = currentEdge[1];
      }
      foundPath.add(currentEdge);
      nodeXmap.remove(currentEdge[0]);
      nodeYmap.remove(currentEdge[1]);
    }

    return foundPath;
  }
}
于 2012-12-13T19:56:48.757 に答える