基于Matlab的有向图及无向图所有生成树搜索的算法与实现

配电网运行时的拓扑结构图为树状网络,配电网无向图的生成树与网络重构的候选解一一对应。无向图所有生成树的快速搜索算法对于配电网网络重构具有重要的理论研究与实际应用价值。以Matlab为平台具体实现了一种基于深度搜索与由原路返回的无向图及有向图所有生成树的搜索算法,算法包括邻接函数、节点类、双链表类、支路扩张函数和主函数。对于有向图,该算法的时间复杂度为O(V+E+EN),空间复杂度为O(V+E),其中V为顶点数,E为边数,N为生成树的个数。对于无向图,该算法的时间复杂度为O(V+E+VN),空间复杂度为O(V+E)。算例表明,所建立的算法可以快速找到无向图及有向图的所有生成树,具有十分优越的性能。