一种基于邻接表的网络最小路集确定方法

摘要

本发明提供了一种基于邻接表的网络最小路集确定方法，以解决大型复杂网络系统的设计仿真和性能评估问题。方法主要包括2个步骤：根据网络的拓扑结构建立一种新型的邻接表；采用深度优先搜索和回溯相结合的方法遍历邻接表确定所有的最小路径。本发明对节点和链路无数量限制，适用于有向网络、无向网络和混合网络，在电力、通信、交通、计算机以及市政管网等大型复杂网络系统具有广泛的应用前景。

主权项

一种基于邻接表的网络最小路集确定方法，其特征在于：1)采用了一种新型的邻接表结构。该邻接表由节点和邻接项组成，每个邻接项由节点可以到达的节点和是否访问过该节点两个数据项组成。这种结构与邻接矩阵或联络矩阵相比有效节约了存储空间，且能同时处理有向网络、无向网络和混合网络。2)采用深度优先搜索和回溯相结合的方法遍历邻接表确定所有最小路径。遍历过程中不会重复搜索相同的最小路径，每次搜索到的最小路径可单独输出，不影响后续最小路径的搜索，故不需要一次性保存所有最小路径，有效节约了内存空间。这种方法对网络节点和链路的数量无限制，适用于大型复杂网络系统最小路集的确定。