拓扑排序在顶尖风控团队的业务落地

ゞ浴缸里的玫瑰 2023-10-02 13:25 21阅读 0赞

> 你好，我是小黄，一名独角兽企业的Java开发工程师。  
> 感谢茫茫人海中我们能够相遇，  
> 俗话说：当你的才华和能力，不足以支撑你的梦想的时候，请静下心来学习，  
> 希望优秀的你可以和我一起学习，一起努力，实现属于自己的梦想。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_12_color_FFFFFF_t_70_g_se_x_16_pic_center]

#### 文章目录 ####

*  一、引言
 *  二、什么是拓扑排序
 *  三、拓扑排序的风控落地
 *  四、决策流的实现代码
 *  四、总结

## 一、引言 ##

上一章我们讲解了关于图的搜索方法，主要是深度优先搜索和广度优先搜索，两种方法的搜索方式各有优点

不知道大家在日常工作中有没有碰到这种情况：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_13_color_FFFFFF_t_70_g_se_x_16]  
比如，我们只有完成工作一之后，才能去完成工作二、工作三，当工作二和工作三同时完成时，我们的工作四才开始开始

简单来说，当前工作必须依赖别的工作完成之后，才能实施工作，那么我们怎么判断哪一份工作需要提前完成呢？

这就是我们今天要讲的 **拓扑排序**

## 二、什么是拓扑排序 ##

在图论中，拓扑排序（Topological Sorting）是一个有向无环图的所有顶点的线性序列。

且该序列必须满足下面两个条件：

*  每个顶点出现且只出现一次。
 *  若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

有向无环图才有拓扑排序，有环图没有拓扑排序一说  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_8_color_FFFFFF_t_70_g_se_x_16]

对于上图来说，拓扑排序可以帮我们做点什么呢？

*  分析每一个点的前后完成的位置
 *  判断该图是否有环无环

## 三、拓扑排序的风控落地 ##

在常见的风控公司，有这样一个功能：**决策流**

简单来说，用户通过配置规则、dubbo服务，做一个流式的计算，如图所示：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_18_color_FFFFFF_t_70_g_se_x_16]  
这是一个比较简单的决策流，它由三个策略集编排，并有起始和结束，是符合BPMN规范的

我们的决策流在执行时，通过拓扑排序去判断每一个策略集完成的前后顺序，进行决策的判断

而dubbo接口的作用，通过远程服务调用，获取我们需要的信息去进行决策的判断，最终获取一个分数

## 四、决策流的实现代码 ##

![在这里插入图片描述][1737a545b2bb4f43b1a1552c184f5e3a.png]

组装成图的思路可见：[给我5分钟，带你秒杀所有图算法之图的对象化描述][5]

拓扑排序的思路：**对于当前图中入度为0的点，即为当前可以执行操作的点**

简单理解就是：**当前的点，没有人指向他**

对于上述思路，我们简单的遍历一遍所有点，可以得出第一次需要执行的点

当我们把第一个点给使用掉之后，我们需要将该点所连接的点的入度减一

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_7_color_FFFFFF_t_70_g_se_x_16]  
我们直接看下代码：

public static void getScore(DecisionFlowGraph graph, HashMap<String, String> map) {
        
            // 使用一个队列
            Queue<DecisionFlowPoint> queue = new LinkedList<>();
    
            // 遍历所有的点，找到入度为 0 的点
            for (DecisionFlowPoint point : graph.points.values()) {
        
                // 入度为0
                if (point.in == 0) {
        
                    queue.add(point);
                }
            }
            
            // 当前的队列不为空
            while (!queue.isEmpty()) {
        
                // 弹出当前队列的头
                DecisionFlowPoint point = queue.poll();
                // 使用当前该点代表的策略集
                finalScore = finalScore + resolve(point, map);
                // 将该点所连接的点的入度减一
                for (DecisionFlowPoint next : point.points) {
        
                    next.in--;
                    if (next.in == 0) {
        
                        queue.add(next);
                    }
                }
            }
        }

整个流程的代码由于太长的原因，在这里就不展示了，有兴趣的可以公众号回复：**算法源码**

不仅包括图的源码，还包括如下内容：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_12_color_FFFFFF_t_70_g_se_x_16]

展示下最终的使用情况：  
![在这里插入图片描述][019d728264a34220a7408bfbacdd44f1.png]

## 四、总结 ##

简单来说，拓扑排序在我们实际业务中，用到的场景也是挺多的

比如：文中提到的决策流、工作流等

当然，看完本篇文章之后，也需要大量的场景去进行练习，不然容易生疏

*  题目一：[207. 课程表][207.]
 *  题目二：[210. 课程表 II][210. _ II]
 *  题目三：[1436. 旅行终点站][1436.]

本期的内容就到这里，下期将会讲述 **最小生成树（Prim、Kruskal）** 算法。

我是一名独角兽企业的Java开发工程师，希望可以点个关注呀，有问题可以留言或者私信加我微信，我们下期再见！  
![在这里插入图片描述][f56dab9358d59e78cdf7352e966dc172.png]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_12_color_FFFFFF_t_70_g_se_x_16_pic_center]: https://img-blog.csdnimg.cn/c47c521ccc094a90be0f431c8fa27fd9.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_12,color_FFFFFF,t_70,g_se,x_16#pic_center
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_13_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/78e8987515ed4e42a2efea87f20ca974.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_13,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_8_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/009e7626c4844b8b98751904a4a08c4f.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_8,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_18_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/5323274955674e7db1dfb83bb94330cf.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_18,color_FFFFFF,t_70,g_se,x_16
[1737a545b2bb4f43b1a1552c184f5e3a.png]: https://img-blog.csdnimg.cn/1737a545b2bb4f43b1a1552c184f5e3a.png
[5]: https://blog.csdn.net/qq_40915439/article/details/120713128
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_7_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/aee3d0c2fd4f499299592e63a2277b2c.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_7,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_12_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/71151e8d729a4279a77e0fad7891886d.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_12,color_FFFFFF,t_70,g_se,x_16
[019d728264a34220a7408bfbacdd44f1.png]: https://img-blog.csdnimg.cn/019d728264a34220a7408bfbacdd44f1.png
[207.]: https://leetcode-cn.com/problems/course-schedule/
[210. _ II]: https://leetcode-cn.com/problems/course-schedule-ii/
[1436.]: https://leetcode-cn.com/problems/destination-city/
[f56dab9358d59e78cdf7352e966dc172.png]: https://img-blog.csdnimg.cn/img_convert/f56dab9358d59e78cdf7352e966dc172.png