kyrenesjtv.github.io

https://kyrenesjtv.github.io/

---

Project maintained by kyrenesjtv Hosted on GitHub Pages — Theme by mattgraham

示例：六度好友

创建human

package me.kyrene.demo.test;

import java.util.HashSet;

/**
 * @ProjectName: demo4Java
 * @Author: AlbertW
 * @CreateDate: 2019/1/15 16:44
 */
public class Node {

    //节点的名称，存放的是用户的ID
    public int user_id;

    //无重复的好友的数量
    public HashSet<Integer> friends = null;

    //好给定的用户节点是几度好友
    public int degree;

    //初始化
    public Node(int id) {
        this.user_id = id;
        this.friends = new HashSet<Integer>();
        this.degree = 0;
    }

    public Node() {

    }

    public int getUser_id() {
        return user_id;
    }

    public void setUser_id(int user_id) {
        this.user_id = user_id;
    }

    public HashSet<Integer> getFriends() {
        return friends;
    }

    public void setFriends(HashSet<Integer> friends) {
        this.friends = friends;
    }

    public int getDegree() {
        return degree;
    }

    public void setDegree(int degree) {
        this.degree = degree;
    }
}

创建好友关系

    /**
     * 创建人际网
     * @param huamnLength 总共有多少人
     * @return 人际网
     */
    public static Node[] createHuman (int huamnLength , int relation_num ){

        //用来生成随机用户
        Random random = new Random(huamnLength);
        //人的node数组
        Node[] user_nodes = new Node[huamnLength];

        //生成所有表示用户的节点
        for(int i = 0 ; i <huamnLength ; i++){
            user_nodes[i] = new Node(i);
        }

        //创建好友关系
        for(int i = 0 ; i<relation_num ; i++){
            int humanA_id = random.nextInt(huamnLength);
            int humanB_id = random.nextInt(huamnLength);

            //自己跟自己不能是好友
            if(humanA_id == humanB_id){
                continue;
            }

            //创建关系
            Node humanA = user_nodes[humanA_id];
            Node humanB = user_nodes[humanB_id];

            humanA.friends.add(humanB_id);
            humanB.friends.add(humanA_id);
        }

        return user_nodes;
    }

查找某一个人的关系网

    /**
     * 查找某一个人的关系网
     * @param nodes 好友关系
     * @param user_id 对应的人
     */
    public static void  bfs(Node[] nodes , int user_id){

        //防止数组越界
        if(user_id > nodes.length){
            return;
        }

        //用于广度搜索的队列
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(user_id);
        //用于存放已经被访问过的点
        HashSet<Integer> visited = new HashSet<>();
        visited.add(user_id);

        while(!queue.isEmpty()){
            int current_user_id = queue.poll();
            //判断这个人是否存在node中
            if(nodes[current_user_id] == null){
                continue;
            }
            for(int friend_id :nodes[current_user_id].friends){
                //排除不存在的
                if (nodes[friend_id] == null) {
                    continue;
                }
                //排除已经访问过的
                if(visited.contains(friend_id)){
                    continue;
                }
                //加入
                queue.offer(friend_id);
                visited.add(friend_id);

                //判断是几度好友
                nodes[friend_id].degree =  nodes[current_user_id].degree +1;
                System.out.println(String.format("\t%d 度好友：%d",nodes[friend_id].degree,friend_id));
            }

        }

    }