Vertex 4-Grad-Verbindung in Grafik-Java Hashmap

Question

mein Java-Code war, um die folgenden Dinge zu tun: (1) Erstellen Sie eine Grafik (Karte) von Freunden miteinander verbunden. (2) prüfen, ob zwei Personen innerhalb der 4. Grad-Verbindung angeschlossen sind (weniger als 3 Kanten), z. B. A-> B (A & B 1. Grad-Anschluss), A-> B-> C (A & C, 2 Gradanschluss), A-> B-> C-> D (A & D, Anschluss 3. Grades), A-> B-> CD-> E (A & E, 4. Grad Anschluss).

Jetzt verwendet mein Java-Code Hashmap, um eine Friend-Connecting-Map zu erstellen. Suchen Sie dann die Hashmap, wenn zwei Personen (z. B. X und Y) innerhalb der Grad-Verbindung verbunden sind. Es funktioniert sehr gut für eine Karte von einer kleinen Anzahl von Menschen. Wenn es um eine Freundeskarte von 3,3 Millionen Menschen geht, funktioniert es sehr gut für die 1., 2. und 3. Verbindung. Die 3. Verbindungssuche dauerte ca. 20 Minuten auf meinem PC. Aber für den Anschluss 4. Grades konnte es nach 50 Stunden nicht beenden.

Fragen: Ich frage mich, ob Hashmap nicht der richtige Weg ist, wenn es um eine große Größe von Graphen (Karte) wie 3 Millionen Menschen geht. Wenn nicht, wie sieht die mögliche Datenstruktur aus?

#

bauen die Freund Anschlusskarte: öffentlichen HashMap> buildFriendMap (String inputfile) { String paymentRecord = Eingabedatei;

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; 

Überprüfen Sie, ob zwei Personen sind im 4. Grad-Verbindung: 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; 
} 

#

Danke,

Answer 1

Check out Dijkstra-Algorithmus . https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Sie können mit einem Gewicht von 1