📚 课程目录第3章图谱数据结构基础

3. 图谱数据结构基础：图的基本术语、邻接表与邻接矩阵、JSON Schema 定义

好，咱们开始聊图的数据结构。

说实话，很多人一听到「图」这俩字就有点发怵。觉得什么拓扑、最短路径、深度优先……听起来头大。但我跟你讲，图的底层原理其实特别简单——它本质上就是在描述「谁跟谁认识」这件事情。

你在做实时编辑重生成反馈图谱时，每次用户点了个节点、拖了一条线，后台处理的数据结构就是图。这块搞不清楚，后面优化就是空中楼阁。我个人习惯是，先把最基础的东西敲瓷实了，再谈什么性能优化。

3.1 图的核心术语

先说几个逃不开的词。你别光背定义，得真能用在项目里。

顶点（Vertex）：就是图里的一个「点」。在我做图谱编辑器时，每个可拖拽的知识卡片就是一个顶点。
边（Edge）：连接两个顶点的线。有向边带箭头，无向边不带。
有向图 vs. 无向图：有向图的边有方向，比如 A→B；无向图的边是双向的，A—B 就表示两条路都能走。
权重（Weight）：边上的数值。比如「关联强度」、「置信度」这种。
度（Degree）：一个顶点有多少条边连着它。有向图里还分入度和出度。
路径（Path）：从一个顶点走到另一个顶点经过的边序列。

举个例子。我之前做过一个知识图谱的编辑器，用户画了一条线表示「A 依赖 B」。那这条线就是有向边，入度是 B 的依赖数，出度是 A 被谁依赖。你看，这些术语是不是一下子就活了？

避坑指南：我曾经在定义图数据时，把有向无向搞混了，结果前端画出来的箭头方向全是反的。调试了两小时才发现是数据结构里 direction 枚举写反了。所以，建图之前，先确定你是「有向」还是「无向」，这个会直接影响邻接矩阵的形状。

3.2 两种存储方式：邻接表 vs. 邻接矩阵

图在内存里怎么存？主流就两种——邻接表和邻接矩阵。各有各的适用场景，我简单对比一下。

3.2.1 邻接矩阵

说白了，就是一个二维数组。拿一个 N×N 的矩阵，matrix[i][j] 表示顶点 i 到顶点 j 有没有边。

// 有向图示例：3个顶点
// 0 → 1, 1 → 2, 0 → 2
matrix = [
  [0, 1, 1],  // 顶点0
  [0, 0, 1],  // 顶点1
  [0, 0, 0]   // 顶点2
]

优点很明显：判断两个顶点是否相邻，直接 O(1) 查数组下标，快得很。缺点呢？你要是图里有 10 万个顶点，矩阵就是 10万×10万，内存直接爆炸。说白了，邻接矩阵适合稠密图——顶点少、边多的情况。

3.2.2 邻接表

这才是工程里的常客。每个顶点维护一个列表，存着它能到达的邻居。

// 还是刚才那个图
adjList = [
  [1, 2],   // 顶点0 → 1, 2
  [2],      // 顶点1 → 2
  []        // 顶点2 没有出边
]

我个人的习惯是，但凡可能涉及动态增删节点，首选邻接表。为什么呢？加一个顶点，邻接表只需要在数组末尾 push 一个新列表。邻接矩阵呢？得整个矩阵重建一次，成本极高。

但这玩意也不是万能。你要查「顶点 i 和 j 有没有边」，邻接表得遍历 i 的邻居列表，最坏 O(N)。所以它适合稀疏图——顶点多、但每个顶点连的边并不多。

特性	邻接矩阵	邻接表
空间复杂度	O(V²)	O(V + E)
查边是否存在	O(1)	O(degree)
遍历一个顶点的边	O(V)	O(degree)
适合场景	稠密图、图大小固定	稀疏图、动态增删

注意：在实时编辑场景下，用户频繁拖拽节点、新增连线。这时候如果底层用邻接矩阵，每次增删顶点就得重构整个矩阵——性能就别指望了。我建议你在做图谱编辑器时，默认走邻接表方案，只在边特别多、查询特别频繁时才考虑矩阵。

3.3 JSON Schema 定义

好了，理论说完了，咱们来点实践的。你写了一个图的结构，怎么让别人也能读懂？怎么保证前端和后端解析一致？答案就是——JSON Schema。

我之前在团队里推过这个。当时前后端对图数据的字段定义完全各写各的，联调时 debug 花了大把时间。后来我把图的结构写成一个 JSON Schema，让前端和后端都按照这个来生成和校验数据。效果立竿见影。

下面是我在实时编辑重生成反馈图谱项目里常用的一个 Schema 骨架——

{
  "$schema": "http://json-schema.org/draft-07/schema#",
  "title": "FeedbackGraph",
  "type": "object",
  "properties": {
    "vertices": {
      "type": "array",
      "items": {
        "type": "object",
        "properties": {
          "id": { "type": "string" },
          "label": { "type": "string" },
          "group": { "type": "string" }
        },
        "required": ["id"]
      }
    },
    "edges": {
      "type": "array",
      "items": {
        "type": "object",
        "properties": {
          "source": { "type": "string" },
          "target": { "type": "string" },
          "weight": { "type": "number", "minimum": 0 },
          "directed": { "type": "boolean", "default": true }
        },
        "required": ["source", "target"]
      }
    },
    "directed": {
      "type": "boolean",
      "default": true
    }
  },
  "required": ["vertices", "edges"]
}

你看，这个 Schema 定义得很清晰：vertices 是顶点数组，每个顶点至少个 id；edges 是边数组，source 和 target 指向顶点 id。这样一来，不管是前端渲染还是后端做图算法，大家的数据结构都是同一套。

  关键点：edges 里的 source 和 target 引用的是 vertices 里的 id。这是一种「隐式引用」——不需要额外的指针，字符串就够了。在实时编辑场景下，这样的好处是：你 copy 一段 JSON 到浏览器，直接就能画图。

3.4 一张图串起所有概念

说了这么多，不如直接看一张结构图。这是我画的「图数据结构全景」，包含了顶点、边、两种存储方式和 JSON Schema 的映射关系。

看到了吗？这张图把咱们这一章的内容全串起来了：图由顶点和边组成，方向与权重决定边的行为；存储上你可以选邻接表或邻接矩阵；最后用 JSON Schema 把这些约定写成文档，让前后端都遵守。

个人经验：我建议你在项目起步阶段，就先把 JSON Schema 写好。哪怕就写了 20 行，也比口头沟通强一万倍。因为 schema 是你的「事实标准」——它会拦住大部分低级的字段拼写错误和类型不匹配问题。我团队后来把这个 schema 直接集成到了 CI 里，每次 PR 都自动校验 payload。效果很不错。

3.5 小结

这一章我们把图的底牌全摊开了：术语、存储方式、数据契约。你下次再碰到类似「图数据结构怎么设计」的问题，脑子里应该有个清晰的决策框架——顶点少边多走矩阵，顶点多边少走邻接表，两者之间用 JSON Schema 做桥接。

嗯，这块儿很关键。你一定要在自己的编辑器项目里亲手写一写邻接表的增删改查，哪怕是 10 个顶点的 demo 也行。纸上谈兵永远比不上手敲一遍来得扎实。