java - 如何在 Java 中高效地创建 Web 数据结构？

Question

我正在尝试为社交网络建模。像这样

A和B,C,D是 friend
B和A,D是 friend
C和A是 friend
D和A,B是 friend

我该如何在 Java 中实现它。我需要编写接受 2 个输入的函数，其工作方式如下:

AreFriends(A,D) = 1
有 friend (C,D) = 0

Answer 1

使用像邻接表这样的数据结构来存储所有的关系。但是对于它，你需要将所有的字符串转换为一些等价的整数，这些整数可以唯一标识String。我们可以在那里使用 map 并将整数相应地分配给 Strings。为了存储连接，我们可以使用 HashSet 的 ArrayList。

import java.util.*;

class Main
{
    static HashMap<String,Integer> map;
    static ArrayList<HashSet<Integer>> list;

    static boolean check(String id1,String id2)  //To check if a connection exists or not
    {
        int index1=map.get(id1);
        int index2=map.get(id2);

        return list.get(index1).contains(index2);
    }

    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);

        ArrayList<String> ids=new ArrayList<String>();
        ids.add("A");ids.add("B");ids.add("C");ids.add("D");  //Taking all possible IDs

        map=new HashMap<String,Integer>();

        int given_id=0;

        for(String id:ids)
        {
            if(!map.containsKey(id))
            {
                map.put(id,given_id);          //Assigning each String a unique ID
                given_id++;
            }
        }

        list=new ArrayList<HashSet<Integer>>(); //ArrayList of HashSet is used to store the connections

        for(int i=0;i<given_id;i++)
        {
            list.add(new HashSet<Integer>());
        }

        //Now for example, we store the connections in HashSet

        String connections="A B A C A D B A B D C A D A D B"; //You can change the following loop as per your need
        String arr[]=connections.split(" ");

        for(int i=0;i<arr.length;i+=2)
        {
            int index1=map.get(arr[i]);
            int index2=map.get(arr[i+1]);

            list.get(index1).add(index2);       //Adding connection in both IDs
            list.get(index2).add(index1);
        }

        if(check("A","D"))
            System.out.println("A and D are friends!");
        else
            System.out.println("No, A and D are not friends!");

        if(check("C","D"))
            System.out.println("C and D are friends");
        else
            System.out.println("No, C and D are not friends!");
    }
}

输出:

A and D are friends!
No, C and D are not friends!