图中的顶点四度连接 - Java 哈希图

Question

我的Java代码是做以下事情： (1)构建相互连接的朋友的图表(地图)。 (2)检查是否有任何两个人在4度连接(少于3条边)内连接，例如A-> B(A&B 1

度连接)，A->B->C(A&C，2度连接)，A->B->C->D(A&D，3度连接)，A->B->C-D->E(A&E，4度连接)。现在我的Java代码使用Hashmap来构建一个朋友连接地图。然后搜索哈希图，如果两个人(例如，X和Y)在4度连接内连接。 它非常适合少数人的地图。当涉及到 330 万人的朋友地图时，它非常适合第 1、第 2 和第 3 连接。第三次连接搜索在我的 PC 上测试了大约 20 分钟。但是对于 4 度连接，它无法在 50 小时后完成。

问题：我想知道当涉及到像300万人这样的大尺寸图形(地图)时，Hashmap是否不是正确的方法。如果没有，可能的数据结构是什么？

#构建好友连接图： public HashMap> buildFriendMap(String inputFile){ 字符串支付记录 = 输入文件;

try{
FileInputStream prStream = new FileInputStream(paymentRecord);
Scanner prScanner = new Scanner(prStream);
while(prScanner.hasNextLine()){
String line = prScanner.nextLine();
System.out.println(line);
String[] columns = line.split(",");
if(columns.length<3){
continue;
}
String sender = columns[1];
String receiver = columns[2];
if(!(sender.equals(" id1")) && !(receiver.equals(" id2"))){
if(friendMap.containsKey(sender)==false){
friendMap.put(sender,new HashSet<String>());
}
friendMap.get(sender).add(receiver);
if(friendMap.containsKey(receiver) ==false){
friendMap.put(receiver,new HashSet<String>());
}
friendMap.get(receiver).add(sender);
}
}
prScanner.close();
}catch (FileNotFoundException e) {
e.printStackTrace();
}
return friendMap;

检查两个人是否在 4 度连接内： public String is4thDegreeFriend (String id1， String id2) {

String sender = id1;
String receiver = id2;
String fraudFlag = "Unverified";
if(!(sender.equals(" id1")) && !(receiver.equals(" id2"))){
if(friendMap.containsKey(sender)==true){
if(friendMap.get(sender).contains(receiver)==true){
fraudFlag = "Trusted";
}else if(friendMap.get(sender).contains(receiver)==false){
Iterator index2nd = friendMap.get(sender).iterator();
while (index2nd.hasNext()){
Object idx2nd = index2nd.next();
if(friendMap.get(idx2nd).contains(receiver)==true){
fraudFlag = "Trusted";
}else if(friendMap.get(idx2nd).contains(receiver)==false){
Iterator index3rd = friendMap.get(idx2nd).iterator();
while (index3rd.hasNext()){
Object idx3rd = index3rd.next();
if(friendMap.get(idx3rd).contains(receiver)==true){
fraudFlag = "Trusted";
}else if(friendMap.get(idx3rd).contains(receiver)==false){
Iterator index4th = friendMap.get(idx3rd).iterator();
while (index4th.hasNext()){
Object idx4th = index4th.next();
if(friendMap.get(idx4th).contains(receiver)==true){
fraudFlag = "Trusted";
}
}
}
}
}
}
}
}
}
return fraudFlag;
}   

#谢谢

Answer 1

查看Dijkstra的算法。 https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

您可以将每个好友连接视为权重为 1 的图形边。