文章目录

一、实现效果

以一个简单的示例说明：容量有1L、4L两种，颜色有红色、黑色两种，其中1L可选红色/黑色，而4L只有红色规格，不可选黑色，同时，选择了黑色，也不能选择4L。实现效果如下所示（仅做示例，样式粗糙不管啦）：
在这里插入图片描述

二、实现过程详解

0.前置知识了解

对sku、图、邻接矩阵等熟悉的可以略过本部分。

（1）什么是sku

sku
本文解决的是前端商品多规格选择问题。接口返回的数据以sku组合列表的形式，每一个sku组合有唯一标识的id。sku是会计学中的一个名词，被称作库存单元，即每一个单规格选项，例如“黑色”、“1L”都是一个规格(sku)。商品和sku属于一对多的关系，可以通过选择多个sku来确定到某个具体的商品。

业务场景
需要实现的业务场景是，要根据用户每一次选择的规格，确定剩下可选和不可选的规格，表现在前端页面上，即将不可选的规格置灰。这是一个十分常见的业务场景，在淘宝、京东、拼多多等电商平台上均需要用户选择规格属性。

暴力破解法
暴力破解法可以O(n²)复杂度实现。实现方法：
当用户选择某一个规格时，对每一个规格进行遍历，判断当前规格是否需要置灰，需要找到除当前规格所在的property之外（称“颜色”为property，称“黑色”、“红色”为attribute，下同），其他已选attribute筛选出来的sku列表，若当前的attribute所支持的sku中的任意一个包含在筛选出来的sku列表中，则当前规格可选，不需要置灰；否则置灰，表示当前规格不可选。这样的时间复杂度较高，在商品的规格非常多且用户的设备性能不佳的情况下，将导致运行时间过长，表现在前端页面上就是当用户点击了一个规格，会有明显的卡顿，十分影响用户体验。

更优的解法是本文基于图这种数据结构的实现，时间复杂度O(n)。
参考文章：规格选择_分分钟学会前端sku算法（商品多规格选择）

（2）什么是图

图的结构很简单，就是由顶点 V 集和边 E 集构成，因此图可以表示成 G=（V, E）。

无向图/有向图
图1-1：无向图1
上图是一个无向图，由点集 V = { 1 , 2 , 3 , 4 , 5 , 6 } ，边集E = { ( 1 , 2 ) , ( 1 , 5 ) , ( 2 , 3 ) , ( 2 , 5 ) , ( 3 , 4 ) , ( 4 , 5 ) , ( 4 , 6 ) }构成 。在无向图中，边( u , v )和边( v , u ) 是一样的。

图1-2：有向图 2
上图是一个有向图，有向图就是加上了方向性，顶点( u , v ) 之间的关系和顶点( v , u )之间的关系不同，二者不一定同时存在。

有权图/无权图
有权图：与有权图对应的就是无权图。如果一张图不含权重信息，我们就认为边与边之间没有差别。
还有很多细化的概念，有兴趣可以自行了解。

参考文章：数据结构：图结构的实现

我们选用的是无向图且是无权图。因为用户在选择规格的时候，并没有先后顺序之分，并且只关注两个顶点是否连通，边与边没有区别。将每种规格看作是无向图的一个顶点，就可以根据 attribute 相互之间的关系画出一个无向图。

（3）什么是邻接矩阵

数组（邻接矩阵）表示法
建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。
设图A=（V，E）有n个顶点，则
在这里插入图片描述
图的邻接矩阵是一个二位数组A.arcs[n][n]，定义为：
在这里插入图片描述

无向图的邻接矩阵表示法
在这里插入图片描述
特点：

  • 无向图的邻接矩阵是对称的；
  • 顶点 i 的度=第 i 行（列）中1的个数；
  • 完全图的邻接矩阵中，对角元素为0，其余1。

参考文章：邻接矩阵

1.初始化顶点集和空邻接矩阵

数据源如下所示：
其中 isActive 表示当前 attribute 是否被选中，若为 true 时表示选中，样式变化，高亮突出显示，isDisabled 表示当前 attribute 是否被置灰，若为 true 时表示置灰，样式变化，点击无响应。

    this.properties = [
      {
        id: "1",
        name: "容量",
        attributes: [
          { value: "1L", isActive: false, isDisabled: false },
          { value: "4L", isActive: false, isDisabled: false },
        ],
      },
      {
        id: "2",
        name: "颜色",
        attributes: [
          { value: "红色", isActive: false, isDisabled: false },
          { value: "黑色", isActive: false, isDisabled: false },
        ],
      },
    ];
    this.skuList = [
      { id: "10", attributes: ["1L", "红色"] },
      { id: "20", attributes: ["1L", "黑色"] },
      { id: "30", attributes: ["4L", "红色"] },
      // { id: "40", attributes: ["4L", "黑色"] },
    ];

根据properties确定顶点集，一个顶点是一个 attribute，因此顶点集为['1L', '4L', '红色', '黑色']
根据顶点集初始化空的邻接矩阵，即为4*4的元素值均为0的空矩阵。画图表示如下所示：
在这里插入图片描述元素值均为0，故图中没有边连通顶点。
此时的邻接矩阵：

1L4L红色黑色
1L0000
4L0000
红色0000
黑色0000

代码实现如下所示：
vertexList 存储顶点，matrix 存储邻接矩阵

    // 构造初始空邻接矩阵存储无向图
    initEmptyAdjMatrix() {
      this.properties.forEach((prop) => {
        prop.attributes.forEach((attr) => {
          this.vertexList.push(attr.value);
        });
      });
      for (let i = 0; i < this.vertexList.length; i++) {
        this.matrix[i] = new Array(this.vertexList.length).fill(0);
      }
    },

2.邻接矩阵赋值

开始画图，将顶点集合中有联系的 attribute 画一条连线，表示选择了其中一个attribute 后，另一个attribute 可选。
初始邻接矩阵元素值均为0：
在这里插入图片描述

（1）根据 skuList 赋值

接下来根据 skuList 来画图：
以数组中的第一个对象为例：

{ id: "10", attributes: ["1L", "红色"] }

在图中将 1L 和 红色 连接起来
在这里插入图片描述
同理，将 1L和 黑色 / 4L 和 红色 连接起来

  { id: "20", attributes: ["1L", "黑色"] },
  { id: "30", attributes: ["4L", "红色"] },

遍历 skuList 后可以得到下图：
在这里插入图片描述
得到的邻接矩阵如下所示：

1L4L红色黑色
1L0011
4L0010
红色1100
黑色1000

但这步工作还没有完成，若最终的无向图如上图所示，会出现什么情况呢？在选择了 1L 之后，4L 就置灰不可选了，这显然不合常理。
因此，还需要根据 properties 来继续画图：

（2）根据 properties 赋值

以第一个 property 为例，需要将 1L 和 4L 连接起来：

      {
        id: "1",
        name: "容量",
        attributes: [
          { value: "1L", isActive: false, isDisabled: false },
          { value: "4L", isActive: false, isDisabled: false },
        ],
      },

同理将 红色 和 黑色 连接起来，遍历完 properties 后，得到的无向图如下所示：
在这里插入图片描述
得到的最终的邻接矩阵如下所示：

1L4L红色黑色
1L0111
4L1010
红色1101
黑色1010

代码实现如下所示：

    // 根据 skuList 和 properties 设置邻接矩阵的值
    setAdjMatrixValue() {
      this.skuList.forEach((sku) => {
        this.associateAttributes(sku.attributes);
      });
      this.properties.forEach((prop) => {
        this.associateAttributes(prop.attributes);
      });
    },

    // 将 attributes 属性组中的属性在无向图中联系起来
    associateAttributes(attributes) {
      attributes.forEach((attr1) => {
        attributes.forEach((attr2) => {
          // 因 properties 与 skuList 数据结构不一致，需作处理
          if (attr1 !== attr2 || attr1.value !== attr2.value) {
            if (attr1.value && attr2.value) {
              attr1 = attr1.value;
              attr2 = attr2.value;
            }
            const index1 = this.vertexList.indexOf(attr1);
            const index2 = this.vertexList.indexOf(attr2);
            if (index1 > -1 && index2 > -1) {
              this.matrix[index1][index2] = 1;
            }
          }
        });
      });
    },

3.判断 attribute 是否可选

当用户首次进入页面，即任何 attribute 还没有被选的情况下，所有 attribute 均可选。
若用户选择了其中一个 attribute ，根据上一步赋值后的邻接矩阵来判断 attribute 是否可选：
以选择了 黑色 为例，找到 黑色 顶点的这一列，则可以知道在选择黑色的情况下哪些选项可选，哪些不可选。值为1的选项可选，值为0的不可选。即选择 黑色 之后，1L / 红色 可选，4L 则不可选。
在实现时需要知道在选择了 黑色 的情况下，4L 是否可选，可以找到 黑色 和 4L 在顶点集中的索引，从而找到在邻接矩阵中的值，查到是0，说明不可选。
在这里插入图片描述
在本例中，数据较简单，只有两个 property，若有更多的 property 时，则已选的规格可能有多个，此时判断当前规格是否可选，当且仅当 当前规格与每一个已选列表中的选项在邻接矩阵中的值均为1时，当前规格可选，否则不可选。
代码实现如下所示：
selected 存储当前已选的 attribute 列表，如 ['1L'] 或 ['1L', '红色']

    // 判断当前 attribute 是否可选，返回 true 表示可选，返回 false 表示不可选，选项置灰
    canAttributeSelect(attribute) {
      if (!this.selected || !this.selected.length || attribute.isActive) {
        return true;
      }
      let res = [];
      this.selected.forEach((value) => {
        const index1 = this.vertexList.indexOf(value);
        const index2 = this.vertexList.indexOf(attribute.value);
        res.push(this.matrix[index1][index2]);
      });
      return res.every((item) => item === 1);
    },

三、Vue源码

运行如下 Vue 源码可以看到在文章开头展示的实现效果

<template>
  <div class="root">
    <p>商品多规格选择示例</p>
    <div v-for="(property, propertyIndex) in properties" :key="propertyIndex">
      <p>{{ property.name }}</p>
      <div class="sku-box-area">
        <template v-for="(attribute, attributeIndex) in property.attributes">
          <div
            :key="attributeIndex"
            :class="[
              'sku-box',
              'sku-text',
              attribute.isActive ? 'active' : '',
              attribute.isDisabled ? 'disabled' : '',
            ]"
            @click="handleClickAttribute(propertyIndex, attributeIndex)"
          >
            {{ attribute.value }}
          </div>
        </template>
      </div>
    </div>
  </div>
</template>

<script>
export default {
  name: "SkuSelector",
  components: {},
  computed: {},
  data() {
    return {
      properties: [], // property 列表
      skuList: [], // sku 列表
      matrix: [], // 邻接矩阵存储无向图
      vertexList: [], // 顶点数组
      selected: [], // 当前已选的 attribute 列表
    };
  },
  mounted() {
    this.properties = [
      {
        id: "1",
        name: "容量",
        attributes: [
          { value: "1L", isActive: false, isDisabled: false },
          { value: "4L", isActive: false, isDisabled: false },
        ],
      },
      {
        id: "2",
        name: "颜色",
        attributes: [
          { value: "红色", isActive: false, isDisabled: false },
          { value: "黑色", isActive: false, isDisabled: false },
        ],
      },
    ];
    this.skuList = [
      { id: "10", attributes: ["1L", "红色"] },
      { id: "20", attributes: ["1L", "黑色"] },
      { id: "30", attributes: ["4L", "红色"] },
      // { id: "40", attributes: ["4L", "黑色"] },
    ];

    this.initEmptyAdjMatrix();
    this.setAdjMatrixValue();
  },
  methods: {
    // 当点击某个 attribute 时，如：黑色
    handleClickAttribute(propertyIndex, attributeIndex) {
      const attr = this.properties[propertyIndex].attributes[attributeIndex];
      // 若选项置灰，直接返回，表现为点击无响应
      if (attr.isDisabled) {
        return;
      }

      // 重置每个 attribute 的 isActive 状态
      const isActive = !attr.isActive;
      this.properties[propertyIndex].attributes[attributeIndex].isActive =
        isActive;
      if (isActive) {
        this.properties[propertyIndex].attributes.forEach((attr, index) => {
          if (index !== attributeIndex) {
            attr.isActive = false;
          }
        });
      }

      // 维护当前已选的 attribute 列表
      this.selected = [];
      this.properties.forEach((prop) => {
        prop.attributes.forEach((attr) => {
          if (attr.isActive) {
            this.selected.push(attr.value);
          }
        });
      });

      // 重置每个 attribute 的 isDisabled 状态
      this.properties.forEach((prop) => {
        prop.attributes.forEach((attr) => {
          attr.isDisabled = !this.canAttributeSelect(attr);
        });
      });
    },

    // 构造初始空邻接矩阵存储无向图
    initEmptyAdjMatrix() {
      this.properties.forEach((prop) => {
        prop.attributes.forEach((attr) => {
          this.vertexList.push(attr.value);
        });
      });
      for (let i = 0; i < this.vertexList.length; i++) {
        this.matrix[i] = new Array(this.vertexList.length).fill(0);
      }
    },

    // 根据 skuList 和 properties 设置邻接矩阵的值
    setAdjMatrixValue() {
      this.skuList.forEach((sku) => {
        this.associateAttributes(sku.attributes);
      });
      this.properties.forEach((prop) => {
        this.associateAttributes(prop.attributes);
      });
    },

    // 将 attributes 属性组中的属性在无向图中联系起来
    associateAttributes(attributes) {
      attributes.forEach((attr1) => {
        attributes.forEach((attr2) => {
          // 因 properties 与 skuList 数据结构不一致，需作处理
          if (attr1 !== attr2 || attr1.value !== attr2.value) {
            if (attr1.value && attr2.value) {
              attr1 = attr1.value;
              attr2 = attr2.value;
            }
            const index1 = this.vertexList.indexOf(attr1);
            const index2 = this.vertexList.indexOf(attr2);
            if (index1 > -1 && index2 > -1) {
              this.matrix[index1][index2] = 1;
            }
          }
        });
      });
    },

    // 判断当前 attribute 是否可选，返回 true 表示可选，返回 false 表示不可选，选项置灰
    canAttributeSelect(attribute) {
      if (!this.selected || !this.selected.length || attribute.isActive) {
        return true;
      }
      let res = [];
      this.selected.forEach((value) => {
        const index1 = this.vertexList.indexOf(value);
        const index2 = this.vertexList.indexOf(attribute.value);
        res.push(this.matrix[index1][index2]);
      });
      return res.every((item) => item === 1);
    },
  },
};
</script>

<style>
.root {
  width: 350px;
  padding: 24px;
}
.sku-box-area {
  display: flex;
  flex: 1;
  flex-direction: row;
  flex-wrap: wrap;
}
.sku-box {
  border: 1px solid #cccccc;
  border-radius: 6px;
  margin-right: 12px;
  padding: 8px 10px;
  margin-bottom: 10px;
}
.sku-text {
  font-size: 16px;
  line-height: 16px;
  color: #666666;
}
.active {
  border-color: #ff6600;
  color: #ff6600;
}
.disabled {
  opacity: 0.5;
  border-color: #e0e0e0;
  color: #999999;
}
</style>

四、其他

在具体的实践中，发现以上算法存在bug，篇幅有限，修复bug优化实现见下篇文章～
前端商品多规格选择问题 SKU 算法实现优化2.0

点击阅读全文
# 前端 # 算法
Logo
华为开发者空间

华为开发者空间，是为全球开发者打造的专属开发空间，汇聚了华为优质开发资源及工具，致力于让每一位开发者拥有一台云主机，基于华为根生态开发、创新。

更多推荐

cover

开发者必备！基于开发者空间的 DeepSeek 模型 API 调用及参数调试攻略

avatar 华为开发者空间
cover

HCDG城市行·阜阳站——AIGC大师班走进阜阳，技术赋能广电媒体，推动行业创新升级

avatar 华为开发者空间
cover

祝贺！华为云GES完成中国信通院图数据库产品测试

avatar 华为开发者空间