1

我正在尝试创建一个无向图，给定机场的文本文件以及与其连接的每个其他机场的成本。该文件采用以下格式，例如：LAX DFW 1000 MSY 250... 其中 lax 是一个顶点（出发机场），dfw 是与 lax 相邻的另一个顶点（到达机场），其边长为 1000。我试图创建一个邻接列表，其中所有出发机场都是存储在数组列表中的 Vertex 对象，并且该数组中的每个元素都有另一个与之连接的数组列表，其中连接数组中的元素也是 Vertex 对象。每个 Vertex 对象都有一个名称字段和边长字段。这是我到目前为止的示例：

import java.io.*;
import java.util.*;

public class ShortestPath
{   
    public ArrayList<Vertex> vertices;

    //new Vertex
    private static class Vertex
    {
        public int edgeLength;
        public ArrayList<Vertex> connected;  //list of connected vertices
        public String name;

        public Vertex(String s)
        {       
            name = s;
        }
    } 

    public ShortestPath() throws FileNotFoundException
    {
        readFile();
    }

    private void readFile() throws FileNotFoundException
    {
        File f = new File("airports.txt");
        Scanner input = new Scanner(f);
        this.vertices = new ArrayList<Vertex>();

        while(input.hasNextLine())
        {
            String line = input.nextLine();
            Scanner scan = new Scanner(line);  //scanner for the current line

            String str = scan.next();

            Vertex from = findVertex(str); 

            if (from == null)
            {
                from = new Vertex(str);
                vertices.add(from);
            }

            from.connected = new ArrayList<Vertex>();

            while(scan.hasNext())
            {
                String s = scan.next();
                Vertex ver = findVertex(s);

                if (ver == null)
                {
                    ver = new Vertex(s);
                    this.vertices.add(ver);
                }

                ver.edgeLength = scan.nextInt();

                from.connected.add(ver);

               //if I use this line, it prints out exactly how the graph should be
               // System.out.println(from.name + " to " + ver.name + " is " + ver.edgeLength);
            }
        }
    } //end readFile()

    public static void main(String[] args)
    {
        try 
        {
            ShortestPath sp = new ShortestPath();

            for(Vertex v: sp.vertices)
            {
                System.out.println(v.name);

                for (Vertex e: v.connected)
                {
                    System.out.print("    to " + e.name + " is " + e.edgeLength);
                }

                System.out.println();
            }

        } catch (FileNotFoundException e) 
        {
            e.printStackTrace();
        }
    }


}

这是我运行它时得到的结果（这是不正确的）：

ATL
    to BOS is 250  to DFW is 59  to MOB is 59
BOS
    to ATL is 59  to DFW is 59
DFW
    to ATL is 59  to AUS is 59  to BOS is 250  to HOU is 59  to LAX is 100  to LIT is 59  to MSY is 128    to OKC is 59  to SHV is 59  to SFO is 100
MOB
    to ATL is 59
AUS
    to DFW is 59  to HOU is 59  to SAT is 59
HOU
    to AUS is 59  to DFW is 59  to SAT is 59
SAT
    to AUS is 59  to HOU is 59
LAX
    to DFW is 59  to SFO is 100
LIT
    to DFW is 59
MSY
    to DFW is 59
OKC
    to DFW is 59
SHV
    to DFW is 59
SFO
    to DFW is 59  to LAX is 100

如果我取消注释 readFile() 中的 System.out.println 行，它会给出这个，如果你要手动绘制图形应该是这样的：

ATL to BOS is 250
ATL to DFW is 250
ATL to MOB is 59
AUS to DFW is 59
AUS to HOU is 59
AUS to SAT is 59
BOS to ATL is 250
BOS to DFW is 250
DFW to ATL is 250
DFW to AUS is 59
DFW to BOS is 250
DFW to HOU is 128
DFW to LAX is 1000
DFW to LIT is 59
DFW to MSY is 128
DFW to OKC is 59
DFW to SHV is 59
DFW to SFO is 1200
HOU to AUS is 59
HOU to DFW is 128
HOU to SAT is 59
LAX to DFW is 1000
LAX to SFO is 100
LIT to DFW is 59
MOB to ATL is 59
MSY to DFW is 128
OKC to DFW is 59
SAT to AUS is 59
SAT to HOU is 59
SFO to DFW is 1200
SFO to LAX is 100
SHV to DFW is 59

我似乎无法弄清楚为什么我得到错误的输出。任何帮助表示赞赏！

4

1 回答 1

0

邻接矩阵的每个节点都位于头位置，然后所有节点都连接到辅助列表中的每个头节点，并具有相对于头节点的边。

 Vertex ver = findVertex(s);

            if (ver == null)
            {
                ver = new Vertex(s);
                this.vertices.add(ver);
            }

            ver.edgeLength = scan.nextInt();

            from.connected.add(ver);

好像有问题。

  1. 理想情况下，“顶点”中的每个节点（我们称之为 headList）都应该具有 0 edgeLength（与自身的距离）。
  2. 您不能从 headList 中拉出一个顶点并将其推送到“已连接”（secondaryList）中。edgeLengths 对每个 secondaryList 的 headVertex 都是真实的。
于 2013-08-01T06:08:02.820 回答