我是怎么使用最短路径算法解决动态联动问题的

  省市县三级联动问题相信大家都耳熟能详了,选择市下拉选项依赖于省,同样的选择县下拉选项依赖于市。把省市县抽象成三个节点A(省),B(市),C(县),它们的关系如下图(1)。假如把这个联动问题复杂化一点如图(2)所示,现在随便改变一个节点的值,其余节点的值会发生什么变化,你还能直接说出来吗?这个问题就是本篇将要介绍的动态联动问题。

阅读目录

回到顶部

动态联动问题分析

  动态联动相对于普通的联动体现在关系事先不可知,省市县联动改变什么相应联动什么都是事先知道的,所以代码实现是相对很简单的。前台写三个Select标签,每个Select标签绑定onchange事件实现相应的逻辑。

    <div>
        <select id="selProvince" onchange="changeCity()">
            <option></option>
        </select>
        <select id="selCity" onchange="changeArea()">
            <option></option>
        </select>
        <select id="selArea">
            <option></option>
        </select>
    </div>
    <script>
        function changeCity() {
            var Province = $("#selProvince").val();
            //取数,取出该省对应的市
            var data = getData(Province);
            //绑定选择城市下拉选择项
            bindCity(data);
            //清空县下拉选择项和值
            clearArea();
        }

        function changeArea() {
            var City = $("#selCity").val();
            //取数,取出该市对应的县
            var data = getData(City);
            //绑定选择县下拉选择项
            bindArea(data);
        }
    </script>

上面的两个函数代码是类似的,总结一下会发现以下步骤:

 1.获取当前改变项的值(省)

   2.找出其直接影响的项(市),从后台获取对应数据,进行绑定。

   3.找出其间接影响的项(县),将其下拉选择项清空,值清空

动态联动问题的难点在于第二步第三步,怎么找当前改变项的直接影响节点和间接影响节点。

回到顶部

问题转化

    我们用图来描述联动,上图2中改变A节点的值,哪些是直接影响节点和间接影响节点呢。直接节点:B,间接节点C F。这里可能存在一个疑惑点C节点为什也算是间接节点呢,它不是也可以直接由A->C吗。从实际应用来考虑,从A节点到C节点有两条路径A->C,A->B->C。也就是说C是依赖于A,B两个节点的,改变了A的值,我们可以获取到B的下拉选项的值,注意了这个时候用户是没有选择B的值的,也是就说B是空的,所以是算不出来C的下拉选项的值的。不明白的可以从省市县联动来考虑,改变了省是求不出来县的值的,只能求出市。到这里可以给上面说了很多次的直接影响节点和间接影响节点下定义了

直接影响节点:改变节点到该节点不存在中转节点

    间接影响节点:改变节点到该节点存在中转节点

    无影响节点   :改变节点不能到达的节点

  定义图的边路径长度为1,上面三种节点的定义可以改为

直接影响节点:最远距离=1

    间接影响节点:最远距离>1

    无影响节点   :最远距离 =无穷大

回到顶部

最短路径算法实现

    经过分析我们把动态联动问题转换成了最远路径问题,这个时候解决方案就很明确了,图的最短路径算法(最远路径可以先把路径值变成相反值,再求最短路径)。当然要求最短路径就得要求图是无闭环的,如何判断图存在闭环可以参考我的另一篇文章拓扑排序及其实际应用

   最短路径算法经典的有Dijkstra and Floyd算法,Dijkstra算法适合求单个节点到其它节点的最短路径问题,Floyd算法适合求每个节点到其它节点最短路径问题。

   Floyd算法的基本思想如下:从任意节点A到任意节点B的最短路径不外乎2种可能,1是直接从A到B,2是从A经过若干个节点到B,所以,我们假设dist(AB)为节点A到节点B的最短路径的距离,对于每一个节点K,我们检查dist(AK) + dist(KB) < dist(AB)是否成立,如果成立,证明从A到K再到B的路径比A直接到B的路径短,我们便设置 dist(AB) = dist(AK) + dist(KB),这样一来,当我们遍历完所有节点K,dist(AB)中记录的便是A到B的最短路径的距离。

   上图的邻接矩阵表示方法:

  代码实现

static int M = 6;

        static void Main(string[] args)
        {
            int[,] dist = new int[6, 6]{
                {int.MaxValue,1,1,int.MaxValue,int.MaxValue,int.MaxValue},
                {int.MaxValue,int.MaxValue,1,int.MaxValue,int.MaxValue,int.MaxValue},
                {int.MaxValue,int.MaxValue,int.MaxValue,int.MaxValue,int.MaxValue,1},
                {int.MaxValue,int.MaxValue,1,int.MaxValue,int.MaxValue,int.MaxValue},
                {int.MaxValue,int.MaxValue,int.MaxValue,int.MaxValue,int.MaxValue,int.MaxValue},
                {int.MaxValue,int.MaxValue,int.MaxValue,int.MaxValue,int.MaxValue,int.MaxValue}
            };

            int[,] g = new int[6, 6];
            Floyd(dist, g);
            PrintGraph(g, M);
            Console.Read();
        }

        /// <summary>
        /// 输出最短路径矩阵
        /// </summary>
        /// <param name="g"></param>
        /// <param name="v"></param>
        public static void PrintGraph(int[,] g, int v)
        {
            for (int i = 0; i < v; i++)
            {
                for (int j = 0; j < v; j++)
                {
                    if (g[i, j] == int.MaxValue)
                        Console.Write("*" + " ");
                    else
                        Console.Write(g[i, j] + " ");
                }
                Console.WriteLine();
            }
        }

/// <summary>
        /// Floyd最短路径算法
        /// </summary>
        /// <param name="dist">邻接矩阵</param>
        /// <param name="D">最短路径</param>
        public static void Floyd(int[,] dist, int[,] D)
        {
            //复制一份dist
            for (int i = 0; i < M; i++)
            {
                for (int j = 0; j < M; j++)
                {
                    D[i, j] = dist[i, j];
                }
            }
            for (int k = 0; k < M; k++)
            {
                for (int i = 0; i < M; i++)
                {
                    for (int j = 0; j < M; j++)
                    {
                        D[i, j] = Math.Min(D[i, j], (D[i, k] == int.MaxValue || D[k, j] == int.MaxValue) ? int.MaxValue : D[i, k] + D[k, j]);
                    }
                }
            }
        }

其中最外层循环K 表示经过K节点,i,j循环表示从i->j ,合起来的意思就是求min(dist(ij) ,dist(ik) + dist(kj)),可以看到实现很简单,时间复杂性为O(n3)

要求最远路径,只要将路径值变为相反值就行了

  int[,] dest = new int[6, 6];
            dist = new int[6, 6]{
                {0,-1,-1,0,0,0},
                {0,0,-1,0,0,0},
                {0,0,0,0,0,-1},
                {0,0,-1,0,0,0},
                {0,0,0,0,0,0},
                {0,0,0,0,0,0}
            };
  Floyd_OneNode(dist, 0, dest);
  PrintGraph_OneNode(dest, M, 0);

/// <summary>
        /// Floyd最短路径算法,求指定节点到其它节点距离
        /// </summary>
        /// <param name="dist">邻接矩阵</param>
        /// <param name="index">指定节点在邻接矩阵下标</param>
        /// <param name="D">最短路径</param>
        public static void Floyd_OneNode(int[,] dist, int index, int[,] D)
        {
            //复制一份dist
            for (int i = 0; i < M; i++)
            {
                for (int j = 0; j < M; j++)
                {
                    D[i, j] = dist[i, j];
                }
            }
            for (int k = 0; k < M; k++)
            {
                //i为指定节点
                int i = index;
                for (int j = 0; j < M; j++)
                {

                    D[i, j] = Math.Min(D[i, j], (D[i, k] == 0 || D[k, j] ==0) ? 0 : D[i, k] + D[k, j]);
                }
            }
        }

回到顶部

总结

  经过上一篇和这一篇的分析,你会发现联动问题是图论里面的相关知识,涉及到拓扑排序和最短路径算法。实际代码中还会涉及到递归,在这次开发中我感受最深的一点遇到复杂问题,一定要分析和规划清楚找到问题的本质,偏离了问题本质就可能用很复杂的代码实现了。

      动态联动问题的经过总结我给出的步骤

     1.计算每个节点到主节点的最远距离,(这个其实是图的最短路径的变种)。

     2.找出所有最远距离是1的节点,这些节点是需要联动的,而其它最远距离不为无穷大的节点是需要清空的。

     3.循环这些距离为1的节点,找这些节点直接依赖的父级节点连同主节点一起收集,传到后台进行解析。

     理清楚这几个步骤你也可以实现自己的动态联动功能了!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏分布式系统和大数据处理

.Net 项目代码风格参考

代码风格没有正确与否,重要的是整齐划一,这是我拟的一份《.Net 项目代码风格参考》,供大家参考。

1182
来自专栏LinkedBear的个人空间

唠唠SE的面向对象-02——封装 原

1) 我们日常使用的电脑主机,把cpu、内存、主板等等都封装到机箱里面去。假如没有机箱的话的出现什么问题?

833
来自专栏华章科技

10道Hadoop面试真题及解题思路

首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的方法, 比如模1000...

642
来自专栏高性能服务器开发

API设计原则 – QT官网的设计实践总结

原文链接:API Design Principles – Qt Wiki 链接:(http://wiki.qt.io/API_Design_Principles...

992
来自专栏GreenLeaves

C# 事件

一、前言:前面的随笔中说完了委托,现在看看事件到底可以干什么,在前面的随笔中,使用委托的过程中,有一个很别扭,也很显然易见的问题,就是委托第一次必须初始化用"=...

18910
来自专栏互联网高可用架构

白话阿里巴巴Java开发手册(编程规约)

1933
来自专栏jouypub

谈谈mysql中utf8和utf8mb4的区别

MySQL在5.5.3之后增加了这个utf8mb4的编码,mb4就是most bytes 4的意思,专门用来兼容四字节的unicode。好在utf8mb4是ut...

570
来自专栏前端新视界

CSS 预处理器中的循环

本文由 nzbin 翻译,黄利民 校稿。未经许可,禁止转载! 英文出处:Loops in CSS Preprocessors 发表地址:http://we...

2066
来自专栏walterlv - 吕毅的博客

真的要比较 for 和 foreach 的性能吗?(内附性能比较的实测数据)

2017-12-07 15:30

1441
来自专栏IMWeb前端团队

从零开始学web安全(3)

上篇文章写到了一个亲自测试的demo,其中有一个地方讲到了“html字符实体”,这是上次xss成功需要知道的非常重要的一个小知识。不仅html字符实体,要继续学...

19910

扫码关注云+社区