邻接表通过顶点数组与邻接链表组合存储社交网络：每个用户为顶点，关系为边，仅存真实连接，空间复杂度o(n+e)，远优于邻接矩阵的o(n²)；支持无向、有向、带权关系建模，并可扩展逆邻接表优化入度查询。
用邻接表存储社交关系网络图，核心是把每个用户当作一个顶点，把“关注”或“互为好友”这种关系当作边，再为每个用户单独维护一份精简的连接列表——只存真实存在的关系，不浪费空间。
邻接表怎么组织社交数据
它由两部分组成：一个顶点数组（存所有用户），和一组链表（每个用户对应一条链表，里面是ta直接关联的人）。比如用户“Alice”在数组第0位，她的链表里只存“Bob”“Charlie”的编号或引用，而不是把全网几千万人都列出来。
- 无向关系（如微信好友）：A关注B，B也自动关注A → 边双向添加，即把B加进A的链表，同时把A加进B的链表
- 有向关系（如微博关注）：A关注B，但B不一定关注A → 只把B加进A的链表，不反向操作
- 带权关系（如QQ亲密度）：链表节点额外存一个weight字段，比如亲密度数值或互动频次
实际编码时的关键结构
以Python为例，最简洁实用的方式是用字典套列表：
graph = {
"Alice": ["Bob", "Charlie"],
"Bob": ["Alice", "David"],
"Charlie": ["Alice", "David"],
"David": ["Bob", "Charlie"]
}
这本质上就是邻接表的高层表达。若用C语言，则需定义顶点结构体和边节点链表，用指针串联；用Java可用HashMap
为什么社交网络特别适合邻接表
现实中的社交图极度稀疏：一个普通用户可能有几百好友，但平台总用户数达上亿。邻接表空间复杂度是O(n + e)，其中n是用户数、e是关系数；而邻接矩阵要O(n²)，光存一个1亿用户的矩阵就需要10¹⁶字节，完全不可行。
- 查某人所有好友：直接读取对应链表，时间复杂度O(k)，k是好友数
- 判断A是否关注B：需遍历A的链表，最坏O(k)，但实际平均很快
- 增删好友：只需在对应链表头或尾插入/删除节点，操作轻量
扩展考虑：入度与出度分离
对微博这类单向关注场景，如果既要查“谁关注了我”（入度），又要查“我关注了谁”（出度），单纯一张邻接表不够高效。这时可维护两张表：
- out_list：标准邻接表，记录“我关注谁”
- in_list：逆邻接表，记录“谁关注我”，构建时每加一条A→B边，就在B的in_list中加入A
虽然多占一倍空间，但换来O(1)级粉丝查询能力，在高并发主页访问场景下非常值得。
