时间戳

首页 > 解决方案 > 使用深度优先搜索的社交用户

java - 使用深度优先搜索的社交用户

问题描述

我需要这样做：实施深度优先搜索算法来确定给定的一对个体是否具有社会联系。该算法应该从第一个个体开始，然后搜索图形，直到到达第二个个体或直到该连接子图中的所有单元都已被访问。该程序应显示“未连接”（当用户没有社交联系时）或“已连接”（当个人有社交联系时，应显示一系列用户，指示个人如何连接）。

社会联系的概念被定义为由一系列朋友联系在一起的个人。例如，如果 user1 是 user2 的朋友，user2 是 user6 的朋友，user6 是 user11 的朋友，user11 是 user5 的朋友，那么我们说 user1 和 user5 通过序列 user1, user2, user6, user11, user5 是社交联系的。

该实现从 users.txt 中读取所有文本，并将唯一的用户整数对存储在名为 UserIndex 的 HashMap 中。这用于轻松地从名称到邻接矩阵中的索引。用户也存储在一个 ArrayList 中，以便可以轻松获取与索引关联的名称。读取文件 ConnectedUsers.txt 并将所有连接的用户作为边添加到邻接矩阵中，在这种情况下，它只是一个二维布尔数组，如果两个索引之间存在边，则将值设置为 true。

ConnectedUsers.txt 的内容：

Users.txt 的内容：

到目前为止，我已经完成了以下操作，但我不知道如何检查与社会相关的个人。

public class GraphNode {
  public String name;
  public int index;
  public boolean isVisited = false;

  public GraphNode(String name, int index) {
    this.name = name;
    this.index = index;
  }
}

public class Graph {
    
    private HashMap<String, Integer> UserIndex = new HashMap<String, Integer>();
    private ArrayList<String> Users = new ArrayList<String>();
    ArrayList<GraphNode> nodeList = new ArrayList<GraphNode>();
    boolean[][] adjacencyMatrix;
    
    
    public Graph()
    {
        loadUsers();
        matrix = new boolean[UserIndex.size()][UserIndex.size()];        
        loadConnectedUsers();
        Set<HashMap.Entry<String,Integer>> key = UserIndex.entrySet();
        for(HashMap.Entry<String,Integer> tempKey: key) {
            nodeList.add(new GraphNode(tempKey.getKey(), tempKey.getValue()));
        }
        dfs();
    }

    public static void main(String[] args) {
        new Graph();
    }

    public ArrayList<GraphNode> getNeighbors(GraphNode node) {
        ArrayList<GraphNode> neighbors = new ArrayList<GraphNode>();
        int nodeIndex = node.index;
        for (int i=0; i<adjacencyMatrix.length; i++) {
            if(matrix[nodeIndex][i]) {
                neighbors.add(nodeList.get(i));
            }
        }
        return neighbours;

    }

    void dfsVisit(GraphNode node) {
        Stack<GraphNode> stack = new Stack<>();
        stack.push(node);
        while(!stack.isEmpty()) {
            GraphNode currentNode = stack.pop();
            currentNode.isVisited = true;
            System.out.print(currentNode.name + " ");
            ArrayList<GraphNode> neighbors = getNeighbors(currentNode);
            for (GraphNode neighbor : neighbors) {
                if (!neighbor.isVisited) {
                    stack.push(neighbor);
                    neighbor.isVisited = true;
                }
            }

        }
    }

    void dfs() {
        for (GraphNode node : nodeList) {
            if(!node.isVisited) {
                dfsVisit(node);
            }
        }
    }
    
    public void loadConnectedUsers()
    {
        try
        {
            BufferedReader in = new BufferedReader(new FileReader(new File("ConnectedUsers.txt")));
            while(in.ready())
            {
                String text = in.readLine();
                StringTokenizer stringLine = new StringTokenizer(text,","); 
                
                String user1 = stringLine.nextToken();
                String user2 = stringLine.nextToken();
             
                addUndirectedEdge(UserIndex.get(user1), UserIndex.get(user2))
            }

        } catch (Exception e)
        {
            e.printStackTrace();
            System.exit(1);
        }        
        
    }
    
    public void loadUsers()
    {
        try
        {
            BufferedReader in = new BufferedReader(new FileReader(new File("Users.txt")));
            int count = 0;
            while(in.ready())
            {
                String text = in.readLine();
                UserIndex.put(text, count);  
                Users.add(text);
                count++;
            }

        } catch (Exception e)
        {
            e.printStackTrace();
            System.exit(1);
        }        
        
    }  

  private void addUndirectedEdge(int k, int m) {
    adjacencyMatrix[k][m] = true;
    adjacencyMatrix[m][k] = true;
  }
    
}

标签： javadata-structureshashmapgraph-algorithmdepth-first-search

解决方案

推荐阅读