社交网络应优先选用邻接表存储，因其空间复杂度为O(V+E)、增删边O(1)、遍历邻居高效，天然适配稀疏图特性；邻接矩阵仅适用于顶点数少（≤1000）、需高频O(1)连通性查询的小规模封闭系统。
社交网络关系本质上是图结构：用户是顶点，好友/关注关系是边。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<String>> 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);
}
}✅ 优点：内存随边数线性增长（O(V+E)），添加/删除边 O(1)，遍历邻居高效
⚠️ 注意：isFollowing 是 O(d) 操作，不是 O(1)；若需高频判断连通性，可额外用 HashSet 存邻居提升查找速度
邻接矩阵：用二维布尔数组或整型数组实现
适用于顶点数固定且较少（如 ≤ 1000）、查询极其频繁的封闭系统。- 先为每个用户分配唯一整型索引（如用
Map<String, Integer>映射 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];
}
}✅ 优点：areFriends() 真正 O(1)，适合强一致性校验场景
❌ 缺点：内存固定为 O(n²)，10⁴ 用户就要 10⁸ 个布尔值（约100MB），实际不可行；动态增删顶点困难
选哪种？看三个关键事实
- 社交网络边数远小于顶点数的平方 → 属于稀疏图 → 邻接表天然适配
- 大多数操作是“查某人的所有好友”或“发消息给所有关注者” → 邻接表遍历邻居更直接
- 需要支持千万级用户扩容 → 邻接表可用
HashMap<String, Set<String>>动态伸缩，矩阵做不到
不复杂但容易忽略：真正上线的社交系统不会只用基础邻接表。它会在其上叠加缓存（如 Redis 存热门用户邻居）、分片（按用户ID哈希分库）、反向索引（谁关注了你）等机制——但底层逻辑，仍是邻接表承载关系主干。
