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

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

相关文章

来自专栏技术沉淀

Ruby练习四

834
来自专栏大闲人柴毛毛

剑指offer——面试题10输入一个十进制整数,统计其中二进制1的个数

/** * 题目:输入一个十进制整数,统计其中二进制1的个数 * @author 大闲人柴毛毛 */ public class CountBitOne {...

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

BZOJ1562: [NOI2009]变换序列(二分图 匈牙利)

30%的数据中N≤50; 60%的数据中N≤500; 100%的数据中N≤10000。

741
来自专栏HansBug's Lab

1798: [Ahoi2009]Seq 维护序列seq

1798: [Ahoi2009]Seq 维护序列seq Time Limit: 30 Sec  Memory Limit: 64 MB Submit: 2930...

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

树上莫队算法

1063
来自专栏mathor

LeetCode410. 分割数组的最大值

 这道题看着好像没什么思路,但其实可以利用二分法来做,二分法中的mid就是最终要返回的值,也就代表着子数组的和最小的值  我们首先还是设置左右区间,左区...

843
来自专栏拂晓风起

Flash:DisplayObject的transform/matrix的潜规则、小bug

1022
来自专栏机器学习从入门到成神

给定一个字符串s,你可以从中删除一些字符,使得剩下的串是一个回文串。如何删除才能使得回文串最长呢?

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

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

P1801 黑匣子_NOI导刊2010提高(06)

题目描述 Black Box是一种原始的数据库。它可以储存一个整数数组,还有一个特别的变量i。最开始的时候Black Box是空的.而i等于0。这个Black ...

3146
来自专栏算法修养

PAT 甲级 1027 Colors in Mars

1027. Colors in Mars (20) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B ...

2756

扫码关注云+社区