-2

我在 Java 中对二维整数数组（不是 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

每行表示：Path_ID 上的 node_x 到 node_y，通过 Port_x 到 Port_y。请注意，每条路径可以是表格中的一行或多行。

该数组是路由算法从无向无权图上的节点 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()与适用于一维数组（二维数组的元素）的自定义比较器一起使用

于 2012-12-13T19:10:15.480 回答
0

假设您的算法正常工作，您不应该多次访问同一个节点。所以你可以贪婪地寻找正确的节点，但你需要一个好的数据结构，这样你就不会不停地循环。此代码假定path_info[index][0]isnode_x和path_info[index][1]is 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 回答