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

  省市县三级联动问题相信大家都耳熟能详了,选择市下拉选项依赖于省,同样的选择县下拉选项依赖于市。把省市县抽象成三个节点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 条评论
登录 后参与评论

相关文章

来自专栏数说工作室

3行代码实现 Python 并行处理,速度提高6倍!

原标题:Here’s how you can get a 2–6x speed-up on your data pre-processing with Pyth...

2165
来自专栏数据结构与算法

洛谷P2147 [SDOI2008]Cave 洞穴勘测

题目描述 辉辉热衷于洞穴勘测。 某天,他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测,辉辉发现这片区域由n个洞穴(分别编号为1到n)以及若干通道...

3449
来自专栏日常学python

20行代码制作字符画版小黄鸭表情包 | 文末送书抽奖结果

前段时间,一只可爱的小黄鸭火起来了,据说是抖音上一位黄衣小姐姐模仿小黄鸭的动作而走红。这只动作呆萌的小黄鸭表情包也跟着火起来了,小黄鸭表情包也由一只变成多只,颜...

1062
来自专栏Python小屋

Python tkinter版猜数游戏

程序启动后,首先需要启动一次游戏并设置数值范围和猜测次数,然后可以猜数并输入,程序会根据实际情况进行大小提示,退出程序时提示战绩,例如共玩几次和成功几次。 im...

3415
来自专栏开发 & 算法杂谈

基于Lockset和Happens-before的数据竞争方法汇总

之前的文章介绍都是单独使用lockset或是单独使用happens-before关系进行动态数据竞争检测的方法。单纯使用lockset算法,由于不考虑其他的一些...

1817
来自专栏前端新视界

响应式卡片抽奖插件 CardShow

GitHub: https://github.com/nzbin/CardShow/ Demo: https://nzbin.github.io/CardS...

2276
来自专栏PPV课数据科学社区

数据流编程教程:R语言与DataFrame

DataFrame DataFrame 是一个表格或者类似二维数组的结构,它的各行表示一个实例,各列表示一个变量。 一. DataFrame数据流编程 ? 二....

40812
来自专栏牛客网

今日头条三面面经

4.       优先队列的底层数据结构?插入和删除一个节点的时间复杂度是多少? 

4382
来自专栏Coding01

推荐一个制作「ASCII 流程图」工具——Graph Easy

我不止一次看到类似「知乎」网站那种 Console 上直接输出这种「ASCII 文本」。

1032
来自专栏码生

Swift2转Swift3

接触swift 已经有一年多的时间了,由最初的OC代码转为 swift 代码,然后从 swift 2.3 转为 swift 3。每次的转换都感觉是将项目整个的翻...

1215

扫码关注云+社区