如何实现无权重图及关系建模？算法分析项目技术求助

核心需求回顾 #

为未开启隐私设置的用户，推荐同一社区、学校或雇主的密切联系人；开启隐私的用户不参与推荐（既不接收推荐，也不被推荐）。目前已完成文件读取并映射到Person和Activities类，需实现无权重图结构来关联用户关系。

1. 先优化数据存储（解决原代码对象未持久化问题） #

原代码中创建的Person和Activities对象未保存，需先将数据存入集合以便后续构建图结构。我们用HashMap以**姓名组合（firstname+lastname）**作为唯一键，快速查找用户：

public class InfoReader {
    // 存储所有用户：键为用户唯一标识（姓名组合），值为Person对象
    private Map<String, Person> personMap = new HashMap<>();
    // 存储用户活动：键为用户唯一标识，值为该用户的活动列表
    private Map<String, List<Activities>> activityMap = new HashMap<>();
    private ContactGraph contactGraph;

    public void ReadInfo(){
        // 读取人员文件
        try {
            String fileLocation = File.separator + "Users" + File.separator + "user" + File.separator + "Downloads" + File.separator + "SamplefilePersons2022Oct31text.csv";
            File personList = new File(fileLocation);
            Scanner personScanner = new Scanner(personList);

            while (personScanner.hasNextLine()) {
                String nextline = personScanner.nextLine();
                String[] personComponents = nextline.split(",");
                
                // 清洗数据（去除字段前后空格）
                String firstname = personComponents[0].trim();
                String lastname = personComponents[1].trim();
                String phone = personComponents[2].trim();
                String email = personComponents[3].trim();
                String community = personComponents[4].trim();
                String school = personComponents[5].trim();
                String employer = personComponents[6].trim();
                String privacy = personComponents[7].trim();

                // 生成用户唯一标识
                String userId = firstname + "_" + lastname;
                Person newPerson = new Person();
                newPerson.setFirstname(firstname);
                newPerson.setLastname(lastname);
                newPerson.setPhone(phone);
                newPerson.setEmail(email);
                newPerson.setCommunity(community);
                newPerson.setSchool(school);
                newPerson.setEmployer(employer);
                newPerson.setPrivacy(privacy);
                
                // 存入map
                personMap.put(userId, newPerson);
            }
            personScanner.close();
        } catch (FileNotFoundException e) {
            throw new RuntimeException(e);
        }

        // 读取活动文件
        try {
            String fileLocation = File.separator + "Users" + File.separator + "user" + File.separator + "Downloads" + File.separator + "SamplefileActivities2022Oct31text.csv";
            File activityList = new File(fileLocation);
            Scanner activityScanner = new Scanner(activityList);

            while (activityScanner.hasNextLine()) {
                String nextLine = activityScanner.nextLine();
                String[] activityComponents = nextLine.split(",");
                
                String firstname = activityComponents[0].trim();
                String lastname = activityComponents[1].trim();
                String activity = activityComponents[2].trim();
                String userId = firstname + "_" + lastname;

                Activities newActivity = new Activities();
                newActivity.setFirstname(firstname);
                newActivity.setLastname(lastname);
                newActivity.setActivity(activity);
                
                // 存入map
                activityMap.computeIfAbsent(userId, k -> new ArrayList<>()).add(newActivity);
            }
            activityScanner.close();
        }catch (FileNotFoundException e) {
            throw new RuntimeException(e);
        }

        // 读取完成后构建联系人图
        buildContactGraph();
    }
}

2. 实现无权重图结构 #

采用邻接表实现无向无权重图：顶点为用户，边代表两人是密切联系人（同一社区/学校/雇主）。用HashSet存储邻接列表，避免重复添加边：

public class ContactGraph {
    // 邻接表：键为用户唯一标识，值为该用户的密切联系人集合
    private Map<String, Set<String>> adjacencyList = new HashMap<>();

    // 添加用户顶点
    public void addVertex(String userId) {
        adjacencyList.putIfAbsent(userId, new HashSet<>());
    }

    // 添加双向边（无向图）
    public void addEdge(String userId1, String userId2) {
        adjacencyList.get(userId1).add(userId2);
        adjacencyList.get(userId2).add(userId1);
    }

    // 获取目标用户的推荐列表（过滤隐私开启的用户）
    public List<Person> getRecommendations(String targetUserId, Map<String, Person> personMap) {
        List<Person> recommendations = new ArrayList<>();
        if (!adjacencyList.containsKey(targetUserId)) {
            return recommendations;
        }

        for (String contactId : adjacencyList.get(targetUserId)) {
            Person contact = personMap.get(contactId);
            // 只推荐未开启隐私的用户
            if ("N".equals(contact.getPrivacy())) {
                recommendations.add(contact);
            }
        }
        return recommendations;
    }
}

3. 构建图的关联关系 #

通过分组批量添加边提升效率：按社区、学校、雇主分别分组，同一组内的用户互相添加边。在InfoReader中添加如下方法：

private void buildContactGraph() {
    contactGraph = new ContactGraph();
    // 按社区分组构建边
    groupAndAddEdges(personMap, Person::getCommunity);
    // 按学校分组构建边
    groupAndAddEdges(personMap, Person::getSchool);
    // 按雇主分组构建边
    groupAndAddEdges(personMap, Person::getEmployer);
}

// 通用分组添加边方法，避免重复代码
private void groupAndAddEdges(Map<String, Person> personMap, Function<Person, String> groupKeyExtractor) {
    Map<String, List<String>> groups = new HashMap<>();
    // 按指定维度（社区/学校/雇主）分组
    for (Map.Entry<String, Person> entry : personMap.entrySet()) {
        String userId = entry.getKey();
        Person person = entry.getValue();
        String groupKey = groupKeyExtractor.apply(person);
        groups.computeIfAbsent(groupKey, k -> new ArrayList<>()).add(userId);
    }

    // 给同一组内的用户添加边
    for (List<String> group : groups.values()) {
        // 先添加所有顶点
        group.forEach(contactGraph::addVertex);
        // 两两用户之间添加双向边
        for (int i = 0; i < group.size(); i++) {
            for (int j = i + 1; j < group.size(); j++) {
                contactGraph.addEdge(group.get(i), group.get(j));
            }
        }
    }
}

// 对外提供获取推荐列表的方法
public List<Person> getRecommendationsForUser(String userId) {
    if (contactGraph == null || !personMap.containsKey(userId)) {
        return Collections.emptyList();
    }
    Person user = personMap.get(userId);
    // 开启隐私的用户不接收推荐
    if ("Y".equals(user.getPrivacy())) {
        return Collections.emptyList();
    }
    return contactGraph.getRecommendations(userId, personMap);
}

4. 关键注意事项 #

• 用户唯一标识：如果数据中有手机号、邮箱等唯一字段，优先用这些字段作为用户ID，避免重名问题
• 数据清洗：CSV字段可能带有空格，必须用trim()处理，否则会导致分组匹配失败
• 隐私规则：严格过滤开启隐私的用户，既不让他们出现在推荐列表，也不给他们推送推荐
• 性能优化：如果用户量极大，两两添加边的O(n²)复杂度会有性能问题，可考虑用更高效的分组关联方式（比如批量插入）

内容的提问来源于stack exchange，提问作者Demali Gregg