写点什么

30 | 图的表示:如何存储微博、微信等社交网络中的好友关系

作者:鲁米
  • 2023-12-12
    北京
  • 本文字数:1657 字

    阅读完需:约 5 分钟

关于开篇思考题,我们只讲了微博这种有向图的解决思路,那像微信这种无向图,应该怎么存储呢?你可以照着我的思路,自己做一下练习。

临接表

package com.controller.bootweb.demo.dsa;
import java.util.ArrayList;import java.util.List;import java.util.Map;import java.util.concurrent.ConcurrentHashMap;
public class WechatGraph { private final Map<Integer, List<Integer>> adjacencyList;
public WechatGraph() { this.adjacencyList = new ConcurrentHashMap<>(); }
public void addEdge(int v1, int v2) { // Add edge v1 -> v2 adjacencyList.computeIfAbsent(v1, k -> new ArrayList<>()).add(v2); // Add edge v2 -> v1 (for undirected graph) adjacencyList.computeIfAbsent(v2, k -> new ArrayList<>()).add(v1); }
public List<Integer> getNeighbors(int vertex) { return adjacencyList.getOrDefault(vertex, new ArrayList<>()); }
public static void main(String[] args) { WechatGraph graph = new WechatGraph(); graph.addEdge(1, 2); graph.addEdge(2, 3); graph.addEdge(3, 1);
// Example: Get neighbors of vertex 1 List<Integer> neighbors = graph.getNeighbors(1); System.out.println("Neighbors of vertex 1: " + neighbors); }}
复制代码

邻接矩阵

package com.controller.bootweb.demo.dsa;
import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.Map;import java.util.concurrent.ConcurrentHashMap;
public class WechatGraph2 { private final int[][] adjacencyMatrix; private final int vertices;
public WechatGraph2(int vertices) { this.vertices = vertices; this.adjacencyMatrix = new int[vertices][vertices]; }
public void addEdge(int v1, int v2) { // Add edge v1 -> v2 adjacencyMatrix[v1][v2] = 1; // Add edge v2 -> v1 (for undirected graph) adjacencyMatrix[v2][v1] = 1; }
public int[][] getAdjacencyMatrix() { return adjacencyMatrix; }
public static void main(String[] args) { int numberOfVertices = 4; WechatGraph2 graph = new WechatGraph2(numberOfVertices); graph.addEdge(0, 1); graph.addEdge(1, 2); graph.addEdge(2, 0);
// Example: Get adjacency matrix int[][] matrix = graph.getAdjacencyMatrix(); System.out.println("Adjacency Matrix:"); for (int[] row : matrix) { System.out.println(Arrays.toString(row)); } }}
复制代码


除了我今天举的社交网络可以用图来表示之外,符合图这种结构特点的例子还有很多,比如知识图谱(Knowledge Graph)。关于图这种数据结构,你还能想到其他生活或者工作中的例子吗?


当涉及到图这种数据结构时,有很多现实生活和工作中的例子。以下是一些例子:


  1. 交通网络图: 道路和交叉口可以被表示为图,交通规划和路径规划就是基于这样的图来进行的。

  2. 电力网络图: 发电站、输电线路、变电站可以被建模为图,用于电力系统的管理和优化。

  3. 组织结构图: 公司或组织的员工关系、部门之间的联系可以用图表示,用于组织管理和沟通。

  4. 任务调度图: 任务之间的依赖关系可以用有向图表示,用于任务调度和优化。

  5. 电子电路图: 电子元件和连接线可以形成图,用于电路设计和分析。

  6. 推荐系统中的用户-物品关系图: 在推荐系统中,用户和物品之间的交互可以用图来建模,用于推荐算法。

  7. 生物学中的基因调控网络: 生物体内基因之间的相互作用可以用图表示,用于研究基因调控。

  8. 网页链接图: 互联网上的网页和链接可以形成图,用于搜索引擎的网页排名算法。

用户头像

鲁米

关注

生活黑客35 2019-06-11 加入

起点不重要,迭代很重要,就需要保持充分的开放和积累;而信息越充分,结果越可靠,又要求随时调整、不断逼近真相。

评论

发布
暂无评论
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系_鲁米_InfoQ写作社区