代码中的数学-使用邻接矩阵

邻接矩阵

1 图

在计算机科学中，一个图就是一些’顶点(vertex)’的集合，这些顶点通过一系列’边(edge)’结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。
一般的图如下图所示

1.1 无向图

无向图就是指的是点与点之间的关联边没有方向限制。两点间可以来回往返的图

如v3这种与其他顶点并不相连的点我们称之为孤立顶点

1.2 有向图

有向图的点与点之间的关系有方向， 只能从一个顶点到允许的顶点

如图， 我们只能从v0到达v1，再从v1到达v2，而不能从v2到达v1。
实际上， 无向图可以看作是边都是双向的有向图。 而要存储和表示图， 我们可以使用数学工具邻接矩阵。

2 邻接矩阵

2.1 理论基础

邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。
我们思考一下图的表示方法， 就会发现， 我们需要一个一维数组来存储顶点，一个二维数组来存储点之间的关系， 而这个二维数组就被称之为邻接矩阵。
我们设一个图有四个顶点（从v0到v3）。那么我们可以用一个 4 * 4 的二维数组（list）来表示。
第一行（row）我们可以视作v0与其他顶点的关系， 那么list[0][0]表示v0与v0的关系 list[0][1]表示v1的关系，如果他们有连接， 那么我们记作true， 即list[0][1] = true 。
理论已经讲解的差不多了， 我们可以上手写个邻接矩阵了。

2.2 实际代码

我们用一个一维数组来存储顶点。

 const vertices: string[] = []

用一个二维数组来存储邻接矩阵

const matrix: boolean[][] = []

然后就是初始化了， 初始我们需要创建一个全是false的矩阵。

Array.from(new Array(length),()=>new Array(length).fill(false))

然后我们需要实现设置两点之间关系的方法， 很简单， 就是找到矩阵中相应的点，然后把它设置为true。具体实现看下面的代码中的setEdge方法。
然后还有得到相邻点的方法， 这个我们则是找到相应行， 然后对照顶点数组， 返回相应的点。（getEdge）
邻接矩阵中常用的操作就是得到多个顶点的相邻点的交集并集的方法，还是通过一个数组来进行运算。
我们创建一个都是0的数组， 长度为顶点个数。 分别求出每一个顶点的相邻点， 如v0的相邻点为v1, v2 那么数组的第二项第三项就相应加1， 记为一次引用。
最后得到的数组，就是各顶点在求相邻点时被引用的次数， 那么交集就是每个顶点都与它相邻， 也就是引用次数等于这多个顶点的个数。
并集就是被引用过的顶点， 返回引用次数大于0的顶点即可。
具体代码如下

class AdjacencyMatrix {
  vertices: string[] = []
  matrix: boolean[][] = []
  constructor(v: string[]) {
    this.vertices = v
    this.init()
  }
  private init() {
    const length = this.vertices.length
    this.matrix = Array.from(new Array(length),()=>new Array(length).fill(false))
  }
  setEdge(id:string, edges:string[]) {  // 设置点之间的关系
    const idIndex = this.vertices.indexOf(id)
    edges.forEach(i => {
      const index = this.vertices.indexOf(i)
      this.matrix[idIndex][index] = true
    })
  }
  getEdge(id: string) {  // 获得相邻点
    return this.matrix[this.vertices.indexOf(id)].map((i, index) => i ? this.vertices[index] : '').filter(Boolean)
  }
  private getRowSum(ids: string[]) {
    const list = new Array(this.vertices.length).fill(0)
    ids.forEach(id => this.matrix[this.vertices.indexOf(id)].forEach((item, index) => list[index] += ~~item))
    return list
  }
  getUnions(ids: string[]) {  // 求交集
    const row = this.getRowSum(ids)
    return row.map((i, index) => i === ids.length && this.vertices[index]).filter(Boolean)
  }
  getCollection(ids: string[]) { // 求并集
    const row = this.getRowSum(ids)
    return row.map((i, index) => i && this.vertices[index]).filter(Boolean)
  }
}

const obj = new AdjacencyMatrix(['v0', 'v1'，'v2']) // 这样我们就创建了一个邻接矩阵

2.3 邻接矩阵可视化

我们完成了邻接矩阵的代码， 但是还是不能直观地认识邻接矩阵， 因此， 可视化就变的很有必要了。 说到底， 邻接矩阵就是顶点和边，顶点的话，随便一个div加点样式就能当顶点。而边， 我想到了流程图中使用的jsPlumb， 我们就用这个来完成邻接矩阵的可视化。
安装jsPlumb我就不多说了， 跟其他包一样。

import {jsPlumb} from 'jsplumb'

class Demo extends AdjacencyMatrix {
  private plumbIns = jsPlumb.getInstance()
  private connections = new Map()
  constructor(v: string[]) {
    super(v);
    const node = document.querySelectorAll(".node")
    this.plumbIns.draggable(node, {containment: 'parent'})
  }

  setLine (id: string, edges: string[], option?: any) {
    this.setEdge(id, edges)
    edges.forEach(edge => {
      if (this.connections.get(id) === edge) return
      const connParam = {source: id, target: edge}
      this.plumbIns.connect(connParam, option || jsplumbConnectOptions)
      this.connections.set(id, edge)
    })
  }
}

如代码所示， 我们通过继承邻接矩阵方法， 实现了我们需要的可视化功能， 我还使用jsPlumb中的拖动功能，使我们生成的顶点可以拖曳。

const vertices = ['v0', 'v1', 'v2', 'v3', 'v4']
function getNode () {
  const list = []
  for (let i = 0; i < vertices.length; i++) {
    list.push(<div key={vertices[i]} style={{left: 200*i+'px'}} id={vertices[i]} className='node' >{vertices[i]}</div>)
  }
  return list
}
function drawLine() {
  const demo = new Demo(vertices)
  demo.setLine('v0', ['v2', 'v3'])
  demo.setLine('v1', ['v3', 'v4'])
  demo.setLine('v2', ['v0', 'v3', 'v4'])
  demo.setLine('v3', ['v0', 'v1', 'v2'])
  demo.setLine('v4', ['v1', 'v2'])
}
function Matrix() {
  useEffect(()=> {
    drawLine()
  })
  return <> {getNode()} </>
}

如图

当然， 还有很多功能我们没有实现， 如删除关系， 创建关系， 这只是个初步的demo。

2.4 邻接矩阵的实际运用 SKU

sku一般是指库存的商品规格， 当然我们在前端上说的sku， 指的是像下边这种页面结构

如图， 我们可以选择不同的属性来购买商品， 当某些对应的属性不存在时， 我们便无法选择， 前端写这个的话，我们就可以通过邻接矩阵实现。

const data = [
  { id: '1', specs: [ '紫色', '套餐一', '64G' ] },
  { id: '2', specs: [ '紫色', '套餐一', '128G' ] },
  { id: '3', specs: [ '紫色', '套餐二', '128G' ] },
  { id: '4', specs: [ '黑色', '套餐三', '256G' ] },
]
const commoditySpecs = [
  { title: '颜色', list: [ '红色', '紫色', '白色', '黑色' ] },
  { title: '套餐', list: [ '套餐一', '套餐二', '套餐三', '套餐四' ]},
  { title: '内存', list: [ '64G', '128G', '256G' ] }
]

先确定数据结构， 如上所示， 我们要展示的就是commoditySpecs， 而我们库存， 也就是相应的sku， 是data。
同样， 先继承下我们的邻接矩阵， 实现一下需要的方法。我们先看需要实现的图。

我们需要根据data进行关系的连接，同时， 同一种属性， 如黑色紫色， 也需要进行链接， 因此，我们就需要一个方法来进行链接， 然后需要一个根据已选顶点返回能够选择顶点的方法。 这样， class的写法就很清晰了

class ShopAdjoin extends AdjacencyMatrix {
  commoditySpecs: commodityType[]
  data: dataType[]
  constructor(commoditySpecs: commodityType[], data: dataType[]) {
    super(commoditySpecs.reduce((total:string[], current) => [
      ...total,
      ...current.list,
    ], []));
    this.commoditySpecs = commoditySpecs;
    this.data = data;
    this.initShopAdjoin();
  }
  private applyCommodity(params: string[]) {
    params.forEach((param) => {
      this.setEdge(param, params);
    });
  }
  private initShopAdjoin() {
    this.data.forEach((item) => {  // sku进行链接
      this.applyCommodity(item.specs);
    });
    // 获得所有可选项
    const specsOption = this.getCollection(this.vertices);
    this.commoditySpecs.forEach((item) => {
      const params: string[] = [];
      item.list.forEach((value) => {
        if (specsOption.indexOf(value) > -1) params.push(value);
      });
      // 同级点位创建
      this.applyCommodity(params);
    });
  }
  
  querySpecsOptions(params: any) {
    if (params.some(Boolean)) { // 判断是否存在选项
      params = this.getUnions(params.filter(Boolean)); // 过滤一下选项
    } else {
      
      params = this.getCollection(this.vertices); // 兜底选一个
    }
    return params;
  }
}

写出了方法， 我们就能写出我们需要的sku了。

const shopAdjoin = new ShopAdjoin(commoditySpecs, data)
function SKU () {
  const [specsS, setSpecsS] = useState(Array.from({ length: commoditySpecs.length }));
  const optionSpecs = shopAdjoin.querySpecsOptions(specsS);
  function handleClick (flag: boolean, i: string, index: number) {
    if (specsS[index] !== i && !flag) return;
    specsS[index] = specsS[index] === i ? '' : i;
    setSpecsS([...specsS]);
  }
  return <div className='container'> { commoditySpecs.map((item, index) => <div className='container-item' key={'item'+index}> <p>{item.title}</p> <div className='options'> {item.list.map(i=> <div onClick={()=>handleClick(optionSpecs.indexOf(i) > -1, i, index)} className={classNames({ option: true, active: specsS.indexOf(i) > -1, disable: !(optionSpecs.indexOf(i) > -1) })} key={i+'option'}>{i}</div>)} </div> </div> ) } </div>
}

线上实例在这里

至于有向图， 加权有向图， 都能在我们已经写好的邻接矩阵class基础上实现。 这些我会在之后的文章中进行讲解。