避免邻接链表图中的重复项

问题描述

这是我第一次发帖

我环顾四周，找不到一个问题特别严重的问题，我无法理解并实施自己的解决方案。 我发现大约3个链接与一个类似的项目有关，但距离同一实现或问题不太近。

我正在使用一个Hashmap，该哈希表将键存储为字符串，将值存储为顶点，并且顶点自身会保留其邻接表，以避免必须重复在hashmap中进行查找。

是的，这是家庭作业，我已经尝试了几天，只是只是简单地从文件创建图形，而似乎做得还不错。 我的图形的两个方向都可以正常工作，因此它是无向的，但是我似乎无法避免重复

请原谅凌乱的代码，这些对象会抛出很多异常，而我是抓住其中每个对象的人。

public AirportGraph(File file)
    {
        this.airports = new HashMap(DEFAULT_SIZE, DEFAULT_LOAD);
        processFile(file);
    }

    private void processFile(File file)
    {   
        Scanner sc;

        /* First we must try to create a scanner from the file */
        try 
        {
            sc = new Scanner(file);

            /* Initializing the hashmap with empty lists in this loop */
            while (sc.hasNext())
            {
                String from = new String();

                /* Here we are skipping over integers for now */
                try
                {
                    from = sc.next();
                    Integer.parseInt(from);
                }
                /* If parsing the int failed, it must be an airport id */
                catch(NumberFormatException e)
                {
                    /* Make sure it does not already contain the key in the hashmap */
                    if (this.airports.containsKey(from))
                        continue;

                    /* Add the key and value to the hashmap */
                    AirportVertex source = new AirportVertex(from);
                    airports.put(from, source);
                    this.numNodes++;
                }
                catch(NoSuchElementException e)
                {
                    System.err.println("There are no more tokens available");
                    e.printStackTrace();
                }
                catch(IllegalStateException e)
                {
                    System.err.println("The scanner is closed");
                    e.printStackTrace();
                }
            }

            /* Reinitialize the scanner */
            sc = new Scanner(file);

            /* Adding adjacent airports */
            while(sc.hasNextLine())
            {
                String line = new String();

                /* Try to create Scanner for the line read from the file */
                try
                {
                    line = sc.nextLine();
                    Scanner tokens = new Scanner(line);

                    /* Try to read tokens */
                    try
                    {
                        String from = tokens.next();


                        /* The first token is the source airport */
                        AirportVertex source = this.airports.get(from);

                        /* The file has a pattern of alternating strings and ints after the first string read on each line */
                        AirportVertex dest = this.airports.get(tokens.next());
                        source.adj_lst.add(dest);

                        /* Read the rest of the line */
                        while (tokens.hasNext())
                        {
                            int cost = tokens.nextInt();

                            AirportVertex nextDest = this.airports.get(tokens.next());

                            if (!dest.adj_lst.contains(nextDest))
                                dest.adj_lst.add(nextDest);

                            if(!nextDest.adj_lst.contains(dest))
                                nextDest.adj_lst.add(dest);

                            dest = nextDest;
                        }
                    }
                    catch(NoSuchElementException e)
                    {
                        System.err.println("There are no more tokens available to scan for the ");
                    }
                    catch(IllegalStateException e)
                    {
                        System.err.println("The scanner is closed");
                        e.printStackTrace();
                    }
                }
                catch(NoSuchElementException e)
                {
                    System.err.println("No line could be found");
                }
                catch(IllegalStateException e)
                {
                    System.err.println("The scanner is closed");
                    e.printStackTrace();
                }
            }
        } 
        catch (FileNotFoundException e) 
        {
            System.err.println("File could not be found");
            e.printStackTrace();
        }

        print();
    }

此代码的输出是

SHV|  OKC SFO DFW
MOB|  DFW ATL
LAX|  HOU LIT DFW
OKC|  MSY SHV DFW
BOS|  DFW ATL AUS HOU
SAT|  HOU DFW AUS
HOU|  DFW SAT BOS LAX AUS
MSY|  LIT OKC DFW
DFW|  BOS MOB HOU ATL ATL AUS SAT SFO LAX
LIT|  LAX MSY DFW
ATL|  BOS DFW AUS
SFO|  SHV DFW DFW
AUS|  DFW ATL BOS HOU

您在此处看到的第一个城市是“源”，列表中的其他城市将是源城市能够去的“目的地”。

例如，这两行在我的文件中

BOS  ATL 250  DFW 250 
DFW  ATL 250  AUS 59  BOS 250  HOU 128  LAX 1000  LIT 59  MSY 128  OKC 59  SHV 59  SFO 1200

如您所见，输出如下：

 DFW|  BOS MOB HOU ATL ATL AUS SAT SFO LAX

在列表中两次显示ATL，检查我提供的2行时，您会看到这是因为ATL转到了DFW，而DFW也转到了ATL，但是我也将其指向了目标指向源头的位置发生两次。 我的if语句并未阻止这种情况的发生。 还有其他问题吗？？？ 我可以简单地使用Set吗？