3

我恳请您的帮助，因为我被卡住了。我输入了这种格式：

6 <-- 顶点数

0 1 2 <-- 通过边直接链接到顶点 0 的顶点

1 0 3 4

我需要在我的程序中是这样的：

int[][] edges = {
   {0,1}, {0,2}, 
   {1,2}, {1,3}, 
   {2,5},
   {3,2}, {3,4},
   {5,4}
};

我被卡住了，我想我可能不得不处理一个列表？这是我到目前为止所拥有的：

public class Part1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int k = scanner.nextInt(); // number of vertices
        String[] input = new String[k];
        int[][] edges;
        String[] tokens = new String[k];
        int[] vertices = new int[k];
        int[] integers = new int[k];
        int p = 0;

        for (int i = 0; i < k; i++) {
            vertices[i] = i;
            input[i] = scanner.nextLine();
            tokens = input[i].split("[\\s+]");
            integers[i] = Integer.parseInt(tokens[i].trim());
            for (int j = 0; j < integers.length - 1; j++) {
                edges[p][i] = integers[0];
                edges[p][2] = integers[j];
                p++;

            }
        }
    }
}

我希望有一个人可以帮助我。

4

2 回答 2

2

我会要求您考虑以不同的方式表示您的图表。表示图的传统方式（也是许多基本图算法的便捷方式）是 Vector[]，它是这样声明的列表数组。

Vector<Integer> graph = new Vector<Integer>[number_of_vertices];

访问 graph[i] 将返回包含顶点 i 的邻居的向量。因此，这种数据结构让您可以有效地动态添加边并快速遍历邻居。构建图表的一些示例代码：

for (int i = 0; i < k; i++) {
  String line = scanner.nextLine();
  tokens = line.split(" ");
  int from = Integer.parseInt(line[0]);
  for (int j = 1; j < tokens.length; j++) {
    graph[from].add(Integer.parseInt(tokens[j]));
  }
}

编辑：请参阅康德对无法使用通用数组的解决方法的回应。

于 2012-04-13T07:03:06.643 回答
1

据我所知，java 不允许使用泛型类型的数组。如何以这种方式修改上面的示例：

Map<Integer,Vector<Integer>> graph = new HashMap<Integer, Vector<Integer>>();

for (int i = 0; i < k; i++) {
  String line = scanner.nextLine();
  tokens = line.split(" ");
  int from = Integer.parseInt(line[0]);
  Vector<Integer> = v new Vector<Integer>();
  for (int j = 1; j < tokens.length; j++) {
    v.add(Integer.parseInt(tokens[j]));
  }
  graph.put(from, v);

}

当你想检索你写的价值时：

  Vector<Integer> v = graph.get(0);
于 2012-04-13T10:41:05.127 回答