java - 无向图的邻接表在 Java 中给出了错误的输出

Question

我正在尝试创建一个无向图，给定机场的文本文件及其连接的每个其他机场的成本。该文件的格式例如: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

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

Answer 1

邻接矩阵的每个节点都位于头位置，然后所有节点都连接到 secondaryList 中的每个头节点，边与头节点相关。

 Vertex ver = findVertex(s);

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

            ver.edgeLength = scan.nextInt();

            from.connected.add(ver);

好像有问题。

1. Ideally every node in "vertices" (lets call it headList), should have 0 edgeLength (distance from itself).
2. You cannot pull a vertex from headList and push it in the "connected"(secondaryList). The edgeLengths are realtive to the headVertex for each secondaryList.