如何高效访问无向无权图中的信息？

Question

我正在做作业，但遇到了一些问题。我实现了一个 class 图，它可以使用邻接列表表示未加权和无向图。我的方法现在是 addEdges 和 addVertex。社交网络图在附件中给出（每行代表由一条边连接的两个节点）。我已经可以访问图表并查看谁和谁是朋友（请查看输出）。我想知道谁的朋友最多，平均有多少朋友。我如何访问这些信息？

public class UndirectedGraphs {
HashMap<String, LinkedList<String>> socialNetworkAdj;

public UndirectedGraphs() {
    socialNetworkAdj = new HashMap<String, LinkedList<String>>();


}
public void addVertex(String label){
    socialNetworkAdj.put(label, new LinkedList<String>());
}

public LinkedList<String> getEdges(String label) {
    return socialNetworkAdj.get(label);
}

public void addEdges(String ver1, String ver2) {
    if (!socialNetworkAdj.containsKey(ver1)) {
        addVertex(ver1);
    }

    if (!socialNetworkAdj.containsKey(ver2)) {
        addVertex(ver2);
    }
    socialNetworkAdj.get(ver1).add(ver2);
    socialNetworkAdj.get(ver2).add(ver1);
    //System.out.println(socialNetworkAdj);

}


public static void main(String[] args) throws Exception {

    File filePath = new File("C:\Users\F\Desktop\A9\social_network.txt");
    FileReader fr = new FileReader(filePath);
    BufferedReader br = new BufferedReader(fr);

    String[] tokens = new String[2];
    //ArrayList<String> nodes = new ArrayList<>();
    UndirectedGraphs graph = new UndirectedGraphs();
    String line;
    String var1 = tokens[0];
    String var2 = tokens[1];

    while ((line = br.readLine()) != null) {
        String[] nodes = line.split("\s+");
        if (nodes.length == 2){
            graph.addEdges(nodes[0], nodes[1] );
        }

    }

    System.out.println("\nAnna: --> " + graph.getEdges("Anna"));
    System.out.println("\nMarie: --> " + graph.getEdges("Marie"));
    System.out.println("\nJakob: --> " + graph.getEdges("Jakob"));
    System.out.println("\nHanna: --> " + graph.getEdges("Hanna"));
    System.out.println("\nFelix: --> " + graph.getEdges("Felix"));
    System.out.println("\nEmma: --> " + graph.getEdges("Emma"));
    System.out.println("\nBen: --> " + graph.getEdges("Ben"));
    System.out.println("\nUlrike: --> " + graph.getEdges("Ulrike"));
    System.out.println("\nLutz: --> " + graph.getEdges("Lutz"));
    System.out.println("\nSofia: --> " + graph.getEdges("Sofia"));
    System.out.println("\nEmilia: --> " + graph.getEdges("Emilia"));
    System.out.println("\nMia: --> " + graph.getEdges("Mia"));
    br.close();

}

}

输出

Anna: --> [Noah, Marie]

Marie: --> [Anna, Noah, Jakob, Hanna]

Jakob: --> [Marie, Felix]

Hanna: --> [Marie, Felix, Jonas]

Felix: --> [Jakob, Hanna, Jonas, Emma, Finn, Ben]

Emma: --> [Felix, Finn]

Ben: --> [Felix, Finn, Lina]

Ulrike: --> [Wolfgang]

Lutz: --> [Stephan, Wolfgang]

Sofia: --> [Emilia]

Emilia: --> [Sofia, Luis, Mia]

Mia: --> [Emilia, Lukas]

Answer 1

那么你可以尝试找到每个节点的 LinkedList 的长度，像这样 -

int total = 0; //variable to store total of friends in the graph
for (String person : graph.socialNetworkAdj.keySet()) 
{           
      int counter = socialNetworkAdj.get(person).size(); //find the length
      System.out.println(person+" has "+counter+ " friends.\n");
      total+= counter; 
}
System.out.println("Average friends : "+(float)total / graph.socialNetworkAdj.size()); //considering that the socialNetworkAdj is not empty

如何高效访问无向无权图中的信息？

How to efficiently access the information in an undirected unweighted graph?

java

graph