Java 数据结构中怎么用图的邻接表和邻接矩阵存储社交网络关系

云婷吖_4207

云婷吖_4207

2026-08-03

823人浏览

原创

社交网络应优先选用邻接表存储,因其空间复杂度为O(V+E)、增删边O(1)、遍历邻居高效,天然适配稀疏图特性;邻接矩阵仅适用于顶点数少(≤1000)、需高频O(1)连通性查询的小规模封闭系统。

java 数据结构中怎么用图的邻接表和邻接矩阵存储社交网络关系

社交网络关系本质上是图结构:用户是顶点,好友/关注关系是边。Java中用邻接表或邻接矩阵存储,核心区别在于空间占用、查询目标和图的稀疏程度。

邻接表更适合大多数社交网络场景
微信好友关系、微博关注关系通常非常稀疏——一个用户可能有几千粉丝,但整个平台有上亿用户,任意两人直接相连的概率极低。邻接表只存真实存在的边,空间开销小,增删边快,遍历邻居高效。

邻接矩阵只在特定小规模场景下适用
比如一个内部通讯系统,仅几百名员工,且需要高频判断“张三和李四是否互为好友”(即O(1)查连通性),这时邻接矩阵的快速判定优势才压倒其空间浪费问题。


邻接表:用HashMap + ArrayList 实现(推荐)

适合无向图(如微信好友)或有向图(如微博关注),代码简洁、扩展性强。

  • 每个用户(顶点)映射到一个邻居列表
  • 无向图:添加 A-B 关系时,同时往 A 的列表加 B,往 B 的列表加 A
  • 有向图(如关注):只往 A 的列表加 B(表示 A 关注 B)
import java.util.*;

public class SocialGraph {
    // key: 用户ID,value: 好友ID列表(无向)或关注对象ID列表(有向)
    private Map<string list>> adjList;

    public SocialGraph() {
        this.adjList = new HashMap();
    }

    public void addVertex(String user) {
        adjList.putIfAbsent(user, new ArrayList());
    }

    // 无向图:互为好友
    public void addFriend(String u, String v) {
        addVertex(u); addVertex(v);
        adjList.get(u).add(v);
        adjList.get(v).add(u);
    }

    // 有向图:u 关注 v
    public void addFollow(String u, String v) {
        addVertex(u); addVertex(v);
        adjList.get(u).add(v);
    }

    // 快速获取某用户所有好友/关注列表
    public List<string> getNeighbors(String user) {
        return adjList.getOrDefault(user, Collections.emptyList());
    }

    // 判断 u 是否关注 v(有向)→ 遍历 u 的邻居列表,O(degree(u))
    public boolean isFollowing(String u, String v) {
        return getNeighbors(u).contains(v);
    }
}</string></string>

✅ 优点:内存随边数线性增长(O(V+E)),添加/删除边 O(1),遍历邻居高效
⚠️ 注意:isFollowing 是 O(d) 操作,不是 O(1);若需高频判断连通性,可额外用 HashSet 存邻居提升查找速度


邻接矩阵:用二维布尔数组或整型数组实现

适用于顶点数固定且较少(如 ≤ 1000)、查询极其频繁的封闭系统。

  • 先为每个用户分配唯一整型索引(如用 Map 映射 ID → index)
  • matrix[i][j] == true 表示 i 与 j 有边(无向图需对称设置;有向图单向)
public class SmallSocialMatrix {
    private final int n; // 顶点总数
    private boolean[][] matrix;
    private Map<string integer> idToIndex;

    public SmallSocialMatrix(int maxUsers) {
        this.n = maxUsers;
        this.matrix = new boolean[n][n];
        this.idToIndex = new HashMap();
    }

    public void addUser(String userId) {
        if (idToIndex.size() >= n) throw new IllegalStateException("Too many users");
        idToIndex.put(userId, idToIndex.size());
    }

    // 无向图添加好友
    public void addFriend(String u, String v) {
        int i = idToIndex.get(u), j = idToIndex.get(v);
        matrix[i][j] = matrix[j][i] = true;
    }

    // O(1) 判断是否互为好友
    public boolean areFriends(String u, String v) {
        Integer i = idToIndex.get(u), j = idToIndex.get(v);
        return i != null && j != null && matrix[i][j];
    }
}</string>

✅ 优点:areFriends() 真正 O(1),适合强一致性校验场景
❌ 缺点:内存固定为 O(n²),10⁴ 用户就要 10⁸ 个布尔值(约100MB),实际不可行;动态增删顶点困难


选哪种?看三个关键事实

  • 社交网络边数远小于顶点数的平方 → 属于稀疏图 → 邻接表天然适配
  • 大多数操作是“查某人的所有好友”或“发消息给所有关注者” → 邻接表遍历邻居更直接
  • 需要支持千万级用户扩容 → 邻接表可用 HashMap> 动态伸缩,矩阵做不到

不复杂但容易忽略:真正上线的社交系统不会只用基础邻接表。它会在其上叠加缓存(如 Redis 存热门用户邻居)、分片(按用户ID哈希分库)、反向索引(谁关注了你)等机制——但底层逻辑,仍是邻接表承载关系主干。

Java开发手册免费版
Java开发手册免费版

Java 开发规约速查手册,覆盖命名、异常、并发、数据库等 7 大维度核心规范。

下载

Java免费学习笔记:立即使用
解锁 Java 大师之旅:从入门到精通的终极指南

相关专题

更多
java
java

Java是一个通用术语,用于表示Java软件及其组件,包括“Java运行时环境 (JRE)”、“Java虚拟机 (JVM)”以及“插件”。php中文网还为大家带了Java相关下载资源、相关课程以及相关文章等内容,供大家免费下载使用。

2023.06.15

13217

6

java正则表达式语法
java正则表达式语法

java正则表达式语法是一种模式匹配工具,它非常有用,可以在处理文本和字符串时快速地查找、替换、验证和提取特定的模式和数据。本专题提供java正则表达式语法的相关文章、下载和专题,供大家免费下载体验。

2023.07.05

10262

9

java自学难吗
java自学难吗

Java自学并不难。Java语言相对于其他一些编程语言而言,有着较为简洁和易读的语法,本专题为大家提供java自学难吗相关的文章,大家可以免费体验。

2023.07.31

8672

8

java配置jdk环境变量
java配置jdk环境变量

Java是一种广泛使用的高级编程语言,用于开发各种类型的应用程序。为了能够在计算机上正确运行和编译Java代码,需要正确配置Java Development Kit(JDK)环境变量。php中文网给大家带来了相关的教程以及文章,欢迎大家前来阅读学习。

2023.08.01

1384

3

java保留两位小数
java保留两位小数

Java是一种广泛应用于编程领域的高级编程语言。在Java中,保留两位小数是指在进行数值计算或输出时,限制小数部分只有两位有效数字,并将多余的位数进行四舍五入或截取。php中文网给大家带来了相关的教程以及文章,欢迎大家前来阅读学习。

2023.08.02

1088

3

java基本数据类型
java基本数据类型

java基本数据类型有:1、byte;2、short;3、int;4、long;5、float;6、double;7、char;8、boolean。本专题为大家提供java基本数据类型的相关的文章、下载、课程内容,供大家免费下载体验。

2023.08.02

1656

5

java有什么用
java有什么用

java可以开发应用程序、移动应用、Web应用、企业级应用、嵌入式系统等方面。本专题为大家提供java有什么用的相关的文章、下载、课程内容,供大家免费下载体验。

2023.08.02

3469

5

java在线网站
java在线网站

Java在线网站是指提供Java编程学习、实践和交流平台的网络服务。近年来,随着Java语言在软件开发领域的广泛应用,越来越多的人对Java编程感兴趣,并希望能够通过在线网站来学习和提高自己的Java编程技能。php中文网给大家带来了相关的视频、教程以及文章,欢迎大家前来学习阅读和下载。

2023.08.03

20651

3

配置java环境变量
配置java环境变量

配置Java环境变量是为了让操作系统能够识别和使用Java的相关命令和功能。本专题为大家提供配置java环境变量相关文章,帮助大家解决问题。

2023.08.03

1495

8

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
dev.java 官方:Learn Java
dev.java 官方:Learn Java

共0课时 | 0人学习

Java JDBC数据库连接官方教程
Java JDBC数据库连接官方教程

共0课时 | 0人学习