使用BFS(广度优先搜索)算法解决无限级分类子集取值

最近工作中碰到一个系统角色的开发需求，其中有一项功能点比较值得拿来说，就是需要根据数据权限范围去获取组织架构中当前部门所有子集的这么一个情况，年前已完成递归组装层级结构的逻辑，但是现在获取子集的话难道还得通过递归的方式么？

首先部门表结构如下：

CREATE TABLE `departments` (
  `id` int unsigned NOT NULL AUTO_INCREMENT,
  `company_id` int unsigned NOT NULL DEFAULT '0' COMMENT '公司ID',
  `pid` int unsigned NOT NULL DEFAULT '0' COMMENT '父级ID',
  `leader_id` int unsigned NOT NULL DEFAULT '0' COMMENT '负责人ID',
  `name` varchar(64) COLLATE utf8mb4_general_ci NOT NULL COMMENT '名称',
  `code` varchar(255) COLLATE utf8mb4_general_ci NOT NULL COMMENT '编码',
  `remark` varchar(2048) CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci NOT NULL COMMENT '备注',
  `status` tinyint unsigned NOT NULL DEFAULT '1' COMMENT '状态：1正常，2注销',
  `created_at` timestamp NULL DEFAULT CURRENT_TIMESTAMP COMMENT '添加时间',
  `updated_at` timestamp NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '修改时间',
  PRIMARY KEY (`id`),
  KEY `idx_company_id` (`company_id`) USING BTREE COMMENT '公司ID索引',
  KEY `idx_leader_id` (`leader_id`) USING BTREE COMMENT '负责人ID索引'
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_general_ci COMMENT='部门表';

这里用pid来标记层级关系，首先看一下部门层级关系列表的结构体如下：

type Departments struct {
    Id       int           `json:"id"`       // 部门ID
    Name     string        `json:"name"`     // 名称
    Children []Departments `json:"children"` // 子部门
}

获取部门的层级关系列表是使用递归来实现的：

func GetChildrenDepartments(companyId int, pid int, departments []models.Departments) []Departments {
    var result []Departments
    for _, item := range departments {
        if item.CompanyId != companyId {
            continue
        }

        if pid != item.Pid {
            continue
        }

        // 使用递归循环组装子集
        children := GetChildrenDepartments(companyId, item.Id, departments)
        data := Departments{
            Id:       item.Id,
            Name:     item.Name,
            Children: children,
        }
        result = append(result, data)
    }

    return result
}

通过请教同事后获知可以使用广度优先遍历多叉树算法去解决这类的情况，关于BFS(广度优先搜索)算法的介绍，可以查看这篇文章： DFS（深度优先搜索）和BFS（广度优先搜索）

其实就是用队列去处理获取逻辑：

// 使用广度优先遍历取出分管部门数据
func getChildrenDepartmentIds(companyId int, pid int, departments []models.Departments) []int {
    var departmentIds []int
    // 取出部门下的层级关系数据，用作队列
    queue := department.GetChildrenDepartments(companyId, pid, departments)

    for len(queue) > 0 {
        var count = 0
        for i := range queue {
            // 计数+1
            count++
            // 保存值
            departmentIds = append(departmentIds, queue[i].Id)
            // 子节点入队
            for j := range queue[i].Children {
                queue = append(queue, queue[i].Children[j])
            }
        }

        // 类似于出队，将遍历过的删掉
        queue = queue[count:]
    }

    return departmentIds
}

然后在使用中只需要传入公司ID、部门ID、库中的部门数据，就可以直接获取到所有子集ID的切片

参考文献：
Go 广度优先遍历多叉树

使用BFS(广度优先搜索)算法解决无限级分类子集取值

发表评论