拓扑网络连通性算法

网络连通性算法 网络定义 节点与支路的集合，该集合中的节点与支路的连接关系可通过一节点-节点关联矩阵A 充分表达： A=[aij]n ×n i,j=1,2,„,n 式中：aij=间有支路直接相连。与节点，当节点间无支路直接相连，与节点，当节点ji1ji0 n —网络节点数 连通性算法 理论算法： 称矩阵A 为网络一级连通矩阵，A2 为二级连通矩阵，„，An -1 为 n -1 级连通矩阵。 A2=AA=[a2ij]n ×n i,j=1,2,„,n 式中：a2ij= 相连。节点间有支路直接或经第与节点，当节点相连，节点间无支路直接且经第与节点，当节点k3ji1 3ji0k k =1,2,„,n ，k ≠i,j „„ An -1=个1nAAA =[an -1ij]n ×n i,j=1,2,„,n 式中： an-1ij= 个节点相连。，，，间有支路直接或经其它与节点，当节点个节点相连，，，，间无支路直接且经其它与节点，当节点221ji1 221ji0nn 矩阵An -1 的每一线性无关的行或列中“1”元素对应的节点均处于同一连通子集中。 实际算法： 若矩阵A 第 i（i=1,2,„,n ）行元素与第 j（j=i+1,i+2,„,n ）行元素中第 k 列元素 aik和 ajk 同为“1”，则第 j 行中的其它“1”元素均填入第 i 行的相应列中。结果矩阵A 第i 行中所有“1”元素对应的节点处于同一连通子集中。 数据定义 Nc—元件数 Nd—节点数 NOD（Nc,3）—每个元件的节点编号 i、j、k KND（Nc）—每个元件的种类（断路器、隔离开关、母线、线路、变压器„„） CNT（Nc）—每个开关元件的分、合状态（逻辑型，例如：合为“真”，分为“假”） NDS0（Nd）—每个节点初始所在连通子集编号 NDS（Nd）—每个节点所在连通子集编号 NCT0（Nc）—每个元件初始所在连通子集编号 NCT（Nc）—每个元件所在连通子集编号 NST（Ns，3）—每个原始连通子集内[子集号，子集内节点数，子集内首位节点号] Ns—最大可能连通子集数 RA（Nd）—节点关联矩阵第 i 行，逻辑型 RB（Nd）—节点关联矩阵第 j 行，逻辑型 检验第k0 个连通子集的连通性子程序CNTS(k0) 初始化 IND=NST(k0,3) 取第k0 个连通子集的首位节点号 N=0 连通子集数置0 LOOP1 l=1，Nd l 从1 至Nd 循环 IF (NDS0（l）=k0)， NDS（l）=0 第k0 个连通子集的节点l 的子集号临时置0 END LOOP1 连通性检验大循环 10 NSUM=1 节点关联矩阵“真”元素计数置为1 LOOP1 l=1，Nd l 从1 至Nd 循环 RA(l)=FALSE 第k...