寻找节点d＝n的节点算法

这里的算法是毕设过程中，自己想到的，也不知道有不有人提出过。这里就记录下发现的过程的具体的算法，以后会用到

背景描述

毕设做的是「社交网络中病毒传播的预测」，前期过程主要是模拟几个网络的数据，然后从一个节点开始传播，研究传播过程的预测性。

其中一步，需要研究距离桥节点（两个网络的俩连接点）距离为n的节点为病毒源的传播过程。这里产生一个需求：寻找与节点A距离为n的节点们。

毕设过程基本是重复博士生姐姐已发表的论文，不过由于年轻气盛给导师说要自己做，只是博士生姐姐提供主线思路。每次都是自己做出来后，给博士生姐姐讲，然后给我讲他的。发现，寻找离节点A距离n的节点们，博士生姐姐都是用Dijkstra算法先把整个网络的节点距离算出来，再找需要的节点。

但是，这样做的缺点是浪费不必要的时间和空间，因为我们的需求中只需要计算距离特定点A长度d＝n的节点们，而不需要计算所有节点的所有距离长度节点。

算法内容

算法思路是根据最直接的想法进行的，即寻找与节点A距离d＝n的节点算法：

寻找与节点A距离d＝n－1的的邻居节点
第一步的节点中减去d＝n－2，n－3，。。。，1，0的邻居节点

js写的伪代码(直接用的毕设时的数据结构)

   /*

        寻找网络Net中距离节点node距离distance的节点们

        Net = {

            '1': {

                'status': 1, // 节点编号1的节点状态是已感染。

                'connect': [2,3,4,5] // 节点编号1的节点的邻居节点。

            },

            ...

        }

    */

    function findDistanceNodes(Net, node, distance) {

        var findNodes = [];

        if(distance == 0) {

            findNodes.push(node);

        } else {

            // 寻找距离  distance - 1 的节点们的邻居们

            var lastDistanceNodes = findDistanceNodes(Net, node, distance - 1);

            for(var i =0; i < lastDistanceNodes.length; i++) {

                findNodes = array_merge(Net[lastDistanceNodes[i]].connect, findNodes);

            }

            // 去重

            findNodes = rmSameArr(findNodes);

            // 从刚才的邻居们中排除 距离node d＝0,1,2,3,4,...distance-1的节点

            for(var i = 0; i < distance; i++) {

                findNodes = minArrFromArr(findNodes, findDistanceNodes(Net, node, i));

            }

        }

        return findNodes;

    }

结尾

以上算法经过毕设结果验证，和博士生姐姐的结果一致，整体运行速度也比其快。这里粗略记录下研究过程，希望也能感受到毕设中的苦与甜。

巴特西

寻找节点d＝n的节点算法

背景描述

算法内容

最新文章

热门文章