在邻接链表列表中避免重复 [英] Avoiding Duplicates in Adjacency Linked List Graph
问题描述
这是我在这里的第一篇文章
我环顾四周，无法找到一个具体问题，理解并实施我自己的解决方案。我发现大约3个链接是关于一个类似的项目，但不是相对接近相同的实现或问题。
我使用一个Hashmap来存储键作为字符串和值作为顶点，顶点持有它们的邻接列表本身，以避免在hashmap中重复查找。
是的，这是作业，我试过只需简单地从一个文件创建一个图表，并且看起来似乎完全正确。我的图表正常工作，所以它是无向的，但我似乎无法避免重复
公共AirportGraph（文件文件）
{
this.airports = new HashMap（DEFAULT_SIZE，DEFAULT_LOAD）;
processFile（file）;
}
private void processFile（文件文件）
{
Scanner sc;
$ b $ *首先，我们必须尝试从文件中创建一个扫描器* /
try
{
sc = new Scanner（file）;
$ b $ *在这个循环中用空列表初始化hashmap * /
while（sc.hasNext（））
{
String from = new String（）;
/ *现在我们跳过整数* /
尝试
{
from = sc.next（）;
Integer.parseInt（from）;
}
/ *如果解析int失败，它必须是机场id * /
catch（NumberFormatException e）
{
/ *确保它不已经在hashmap * /
中包含密钥if（this.airports.containsKey（from））
continue;
/ *将密钥和值添加到散列表* /
AirportVertex source = new AirportVertex（from）;
airports.put（from，source）;
this.numNodes ++;
catch（NoSuchElementException e）
{
System.err.println（没有更多的标记可用）;
e.printStackTrace（）;
catch（IllegalStateException e）
{
System.err.println（扫描器已关闭）;
e.printStackTrace（）;
重新初始化扫描器* /
sc = new Scanner（file）;
$ b $ / *添加相邻机场* /
while（sc.hasNextLine（））
{
String line = new String（）;
*尝试为从文件读取的行创建扫描器* /
尝试
{
line = sc.nextLine（）;
扫描仪令牌=新扫描仪（线）;
$ b $ *尝试读取令牌* /
尝试
{
String from = tokens.next（）;
/ *第一个标记是源机场* /
AirportVertex source = this.airports.get（from）;
/ *在每行读取第一个字符串后，该文件具有交替字符串和整数的模式* /
AirportVertex dest = this.airports.get（tokens.next（））;
source.adj_lst.add（dest）;
$ b $ *读取其余行* /
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;
$ b $ catch（NoSuchElementException e）
{
System.err.println（没有更多的标记可用于扫描）;
catch（IllegalStateException e）
{
System.err.println（扫描器已关闭）;
e.printStackTrace（）;
catch（NoSuchElementException e）
{
System.err.println（No line could be found）;
catch（IllegalStateException e）
{
System.err.println（扫描器已关闭）;
e.printStackTrace（）;
$ b 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
您在这里看到的第一个城市是SOURCE和其他城市在这个列表中是源城市可以访问的DESTINATIONS。
例如，这两行代码位于我的文件中
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？
傻傻的我...我只需要一个if语句
在这里，我应该说这个而不是
/ *第一个标记是源机场* /
AirportVertex source = this.airports.get（from）;
/ *在每行读取第一个字符串后，该文件具有交替字符串和整数的模式* /
AirportVertex dest = this.airports.get（tokens.next（））;
if（！source.adj_lst.contains（dest））
source.adj_lst.add（dest）;
this is my first post here
I have looked around and could not find a particular question that is having a problem close enough to mine for me to be able to understand and implement a solution of my own. I found about 3 links that were about a similar project, but not relatively close to the same implementation or problem.
I am using a Hashmap that stores keys as strings and values as vertices, with the vertices holding their adjacency lists themselves in order to avoid having to repeatedly do a lookup in the hashmap.
Yes, this is homework and I have tried for days to just simply create a graph from a file and just cant seem to quite get it right. I have both directions of my graph working correctly, so it is undirected, but I cannot seem to avoid duplicates
please excuse the messy code, these objects throw lots of exceptions and I am the type of person to catch every one of them lol.
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();
}
The output of this code is
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
The first city you see here is the "SOURCE" and the rest of the cities in the list are to be the "DESTINATIONS" that the source city is able to go to.
These 2 lines, for example, are in my file
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
As you can see, the output Here:
DFW| BOS MOB HOU ATL ATL AUS SAT SFO LAX
is showing ATL twice in the list, which when examining the the 2 lines i provided, you can see it is because ATL goes TO DFW and DFW also goes TO ATL, but I have also made it to where the destination points back at the source which happens twice. My if statements are not stopping this from happening. Is there something else going wrong??? Could I simply just use a Set?
Silly me... I only needed one other if statement
Here I should have said this instead
/* 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());
if (!source.adj_lst.contains(dest))
source.adj_lst.add(dest);
这篇关于在邻接链表列表中避免重复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
