-1

我这里有一段代码。这是我的 Dijkstra 实现的一个片段。在这里，我们实例化了 4 个顶点，每个顶点都有指定的边及其与顶点（节点）的距离。如果将数据直接输入到主类中，则此代码简单且有益。

Vertex v0 = new Vertex("Redvile");
Vertex v1 = new Vertex("Blueville");
Vertex v2 = new Vertex("Greenville");
Vertex v3 = new Vertex("Orangeville");
Vertex v4 = new Vertex("Purpleville");

v0.adjacencies = new Edge[]{ new Edge(v1, 5),
                             new Edge(v2, 10),
                                 new Edge(v3, 8) };
v1.adjacencies = new Edge[]{ new Edge(v0, 5),
                             new Edge(v2, 3),
                             new Edge(v4, 7) };
v2.adjacencies = new Edge[]{ new Edge(v0, 10),
                                 new Edge(v1, 3) };
v3.adjacencies = new Edge[]{ new Edge(v0, 8),
                             new Edge(v4, 2) };
v4.adjacencies = new Edge[]{ new Edge(v1, 7),
                                 new Edge(v3, 2) };

但是，我的数据来自文件。我必须读取文件并创建顶点的实例以及每个顶点上的边（邻接）。我在实现此功能时遇到问题。也就是说，我需要一个代码，将上面的这段代码转换为数据来自文件的东西。

这是我的示例数据：

a0 -    a1,1.6
a1 -    a0,1.6      * a2,0.85   * a3,0.5
a2 -    a1,0.85     * a34,1.2   * a39,0.65
a3 -    a1,0.5      * a4,0.2    * a5,0.1
a4 -    a3,0.2      * a5,0.2
a5 -    a4,0.1      * a6,1      * a36,0.65
a6 -    a5,1        * a7,1.5    * a14,0.45
a7 -    a6,1.5      * a8,0.18   * a11,1.2
a8 -    a7,0.18     * a9,1
a9 -    a8,1
a10 -   a13,1.9

a0-a10 是顶点，a1,1.6是其他的表示以 (vertex,distance) 格式连接到顶点的邻接或边。

到目前为止，我能够读取这个文件并将每一行放在一个 ArrayList 上。我现在的问题基本上是如何实例化每个顶点并添加邻接关系。

这就是我读取文件的方式：

private void readFile(String fileName) {

    try{
        FileReader file = new FileReader(fileName);
        Scanner sc = new Scanner(file);

        int i = 0;
        while (sc.hasNextLine()) {
          input.add(sc.nextLine());
          i++;
        }

        setNodes();
        System.out.println();
        file.close();
    } catch(Exception e){
        System.out.println(e);
    }
}

输入是每行包含文件所有内容的arrayList。另一方面，节点将拥有所有顶点的列表。

public void setNodes() {

    System.out.println();

    for(int i=0; i<input.size(); i++) {
        line = this.input.get(i);
        nodes.add(line.substring(0,line.indexOf("-")).trim());
    }
}

还，

PS我也是数据类型的问题。我的 arrayList 是字符串，顶点是 Vertex 类型，这是我的代码中定义的类。

如果此描述不充分，请随时发表评论。谢谢你和欢呼！

4

2 回答 2

2

这应该是直截了当的

a0 -    a1,1.6
a1 -    a0,1.6      * a2,0.85   * a3,0.5

我将向您展示过程而不是代码

Create vertex_list list 
For each line read
  split on '-' left side is your current_vertex, right side is your 'adjacency list'
   check if your vertex is present in vertex_list if not create it and add it
   adj list =  a0,1.6      * a2,0.85   * a3,0.5
   split your adj list   on '*' 
   for each entry ex 'a0,1.6'
      split on ','  now you know the edge_vertex=split[0] = a0 and weight = split[1] = 1.6
      check if you already have edge_vertex in your vertex list if not add it
      create and add edge(edge_vertex, weight)  to current vertex
    end
 end

在您的过程结束时，您应该能够显示 vertex_list 中的所有顶点

至于为顶点命名，您可以通过几种不同的方式来执行此操作，简单的方法是在配置文件中为顶点命名。这将需要您对列表进行两次遍历，第一次生成每个具有名称的顶点，第二次就像上面的伪代码一样，除了不需要创建新顶点，因为它们是在第一次遍历中创建的，您只需添加边顶点到 adj。列表。

a0,Name A -    a1,1.6
a1,Name B -    a0,1.6      * a2,0.85   * a3,0.5
a2,Name C -    a1,0.85     * a34,1.2   * a39,0.65
a3,Name D -    a1,0.5      * a4,0.2    * a5,0.1
于 2013-03-14T17:39:17.433 回答
1

我现在根据我的实现和@greg 提供的信息发布这个问题的答案。非常感谢他！

private void setVertices() {

    String[] listEdges;

    for(int i=0; i<nodes.size(); i++) {

        //if vertex does not exist, create it
        if(vertexList.containsKey(nodes.get(i))) {
            vertexList.put(nodes.get(i), new Vertex(nodes.get(i)));
        }

        line = adjLine.get(i);

        //separate adj edges to *
        if(line.contains("*")) {
            listEdges = line.split("[*]");
        } else {
            listEdges = new String[1];
            listEdges[0] = line;
        }

        //add edges to specified vertex
        for(int j=0; j < listEdges.length; j++ ) {
            String[] word = listEdges[j].split(",");
            edges.add(new Edge(vertexList.get(word[0]),Double.parseDouble(word[1])));
        }

        map.put(nodes.get(i), edges);
        edges.clear();
    }
}

基本上，我使用 ArrayList、Map 和 HashMap 来做到这一点。是的！

于 2013-03-19T05:11:22.853 回答