拓扑网络连通性算法

1、网络连通性算法网络定义节点与支路的集合，该集合中的节点与支路的连接关系可通过一节点-节点关联矩阵A充分表达：A=aijnm i,j=1,2,n0,当节点i与节点j间无支路直接相连，1，当节点i与节点j间有支路直接相连。n网络节点数连通性算法理论算法：称矩阵A为网络一级连通矩阵，A2为二级连通矩阵，2 2 A=AA=aijnxni,j=1,2,n"0,当节点i与节点j间无支路直接且经第1，当节点i与节点j间有支路直接或经第k=1,2,n，i,j式中：a式中:a2ij=丿An-1为n-1级连通矩阵。3节点k相连,3节点k相连。一n个An-1=AAA =an-1ijnxni,j=1,2,n

2、式中：n-10当节点i与节点j间无支路直接且经其它1,2，-，n-2个节点相连，a ij=1，当节点i与节点j间有支路直接或经其它1,2,， n-2个节点相连。矩阵An-1的每一线性无关的行或列中“ 1 ”元素对应的节点均处于同一连通子集中。实际算法：若矩阵A第i (i=1,2,n)行元素与第j (j=i+1,i+2,n)行元素中第k列元素aik 和ak同为“1”，则第j行中的其它“ 1”元素均填入第i行的相应列中。结果矩阵 A第 i行中所有“ 1”元素对应的节点处于同一连通子集中。数据定义Nc元件数Nd节点数NOD ( Nc,3)每个元件的节点编号i、j、kKND ( Nc)每个元件的种类(

3、断路器、隔离开关、母线、线路、变压器 )CNT (Nc)每个开关元件的分、合状态(逻辑型，例如：合为“真”,分为“假”) NDS0 (Nd)每个节点初始所在连通子集编号NDS ( Nd)每个节点所在连通子集编号NCT0 (Nc)每个元件初始所在连通子集编号NCT ( Nc)每个元件所在连通子集编号NST( Ns，3) 每个原始连通子集内 子集号，子集内节点数，子集内首位节点Ns最大可能连通子集数RA (Nd) 节点关联矩阵第 i 行，逻辑型RB (Nd)节点关联矩阵第j行，逻辑型6 / 6IND=NST(k 0,3)N=0LOOP1 l=1 ，NdIF (NDS0(l) =k0)，END LO

4、OP1检验第k0个连通子集的连通性子程序CNTS(k °)初始化 取第 k0 个连通子集的首位节点号 连通子集数置 0 l 从 1 至 Nd 循环NDS(l)=0 第 k0 个连通子集的节点 l 的子集号临时置 0连通性检验大循环10 NSUM=1节点关联矩阵“真”元素计数置为 1LOOP1 l=1 ，Nd RA(l)=FALSEEND LOOP1RA(IND)=TRUEM=1l 从 1 至 Nd 循环第 k0 个连通子集中第 IND 行第 l 列元素置为“假”节点关联矩阵第 IND 行对角元素置 1节点关联矩阵第 IND 行 “真”元素计数置为 1形成节点关联矩阵的第LOOP1 l

5、=1,NcIND 行 RAl 从 1 至 Nc 循环IF(NCT0(l)=k 0)，THENIF(KND(I)工开关'or (KND(I)='开关'I=NOD(l,1) J=NOD(l,2) K=NOD(l,3) IF(I=IND) ，THENIF(Jm0 and 冃 I), THEN RA(J)=TRUEM=M+1END IFIF(K 工0 and Km I and K工 J), THEN RA(K)=TRUEM=M+1END IFEND IFIF(J=IND), THENIF(Im0 and ImJ), THEN RA(I)=TRUEM=M+1END IFIF(Km

6、0 and KmI and KmJ), THEN RA(K)=TRUEM=M+1END IFEND IFIF(K=IND) , THENIF(Im0 and ImK), THEN RA(I)=TRUEM=M+1END IFIF(Jm 0 and Jm I and JmK), THEN如果元件I属于初始连通子集ko,则and CNT(I)= 合' ), THEN取元件 I 的各端节点号如果节点号I等于节点号IND，则如果节点号J不等于0和I，则关联矩阵第IND行第J列元素置为“真” 关联矩阵第 IND 行“真”元素计数 +1如果节点号K不等于0和I和J,则 关联矩阵第IND行第K列元素置

7、为“真” 关联矩阵第 IND 行“真”元素计数 +1如果节点号J等于节点号IND，则 如果节点号I不等于0和I，则 关联矩阵第 IND 行第 I 列元素置为“真” 关联矩阵第 IND 行“真”元素计数 +1如果节点号K不等于0和I和J,则 关联矩阵第IND行第K列元素置为“真” 关联矩阵第 IND 行“真”元素计数 +1如果节点号K等于节点号IND，则 如果节点号I不等于0和K，贝U 关联矩阵第 IND 行第 I 列元素置为“真” 关联矩阵第 IND 行“真”元素计数 +1如果节点号J不等于0和I和K，贝URA(J)=TRUEM=M+1END IFEND IF关联矩阵第IND行第J列元素置为“

8、真” 关联矩阵第IND行“真”元素计数+1END IFEND IFEND L00P1将节点连通矩阵第IND+1Nd行与第IND行比较，寻找包含节点IND的连通子集LOOP1 WHILE(M v NST(ko,2) and M>NSUM)当 M v子集 ko 节点数且有新“真”元素NSUM=M出现时，循环LOOP2 ld=IND+1，Nd ld 自 IND+1 至 Nd 循环IF (NDSO(ld)=ko and RA(ld)=FALSE and NDS(ld)=0)，THEN 当LOOP3 l=1，NdRB(I)=FALSEEND LOOP3RB(ld)=TRUE形成节点关联矩阵的第LO

9、OP3 l=1，NcIF(NCT0(l)=k o)，l自1至nd循环 关联矩阵第ld行第l列元素置为“假”节点关联矩阵第Id节点ld属于连通子 集k。，且关联矩阵第IND行第ld列元素为“假”，且未找到 节点ld新连通子集 号时，循环 行对角元素置1Id 行 RBTHENIF(KND(l)工开关or (KND(l)=l自1至Nc循环如果元件l属于原连通子集ko,则 '开关and CNT(l)= 合)，THENI=NOD(l,1) J=NOD(l,2) K=NOD(I,3)IF(I=ld)，THENIF(Jm0 and Jm I)，THENRB(J)=TRUEEND IF取元件l的各端节

10、点号如果节点号I等于节点号ld，则如果节点号J不等于0和I，则 关联矩阵第ld行第J列元素置为“真”RB(K)=TRUE END IF关联矩阵第ld行第K列元素置为“真”IF(K工0 and Km I and K工J)，THEN如果节点号K不等于0和I和J,则END IFIF(J=ld)，THENIF(I m 0 and Im J)，THENRB(I)=TRUE如果节点号J等于节点号ld，则如果节点号I不等于0和J,则关联矩阵第ld行第I列元素置为“真”END IFIF(Km 0 and Km I and Km J)，THEN如果节点号K不等于0和I和J,贝URB(K)=TRUE关联矩阵第ld

11、行第K列元素置为“真”END IFEND IFIF(K=ld)，THEN如果节点号K等于节点号ld，贝UIF(I m0 and Im K)，THEN如果节点号I不等于0和K，贝URB(I)=TRUE关联矩阵第ld行第I列元素置为“真”END IFIF(Jm0 and Jm I and Jm K)，THEN如果节点号K不等于0和I和J,则RB(J)=TRUE关联矩阵第ld行第J列元素置为“真”END IFEND IFEND IF END IFEND LOOP3L00P3 1=1 , Nd l 自 1 至 Nd 循环IF(NDSO(l)=k o and RA(I) and RB(I) , THEN

12、L00P4 j=1, Nd jl 自 1 至 Nd 循环IF(RA(j)=FALSE and RB(j)=TRUE) , THENRA(j)=TRUE 行 IND 列 j 置为“真” M=M+1END IF如果节点I属于原连通子集 k0,且 关联矩阵第IND行第I列元素与第 ld行第I列元素同为“真”，贝U 如果第IND行第j列元素为“假”， 且Id行第j列元素为“真”，则关联矩阵第IND行“真”元素计数+1END LOOP4将原始连通子集k0内的连通子集数置为NI自1至Nc循环如果元件I属于初始连通子集k0,则'开关and CNT（I）= 合），THENI=元件I的第一个节点号 如果

13、I为0，贝UI=元件I的第二个节点号 如果I为0，贝UI=元件I的第三个节点号 如果I为0，贝U 元件I所在连通子集号为0 （孤立元件）GOTO 20END LOOP320 END LOOP2END LOOP1N=N+1IF(M=NST(k 0,2), THENLOOP1 l=1,NdIF(NDS0(l)=k0), NDS(l)=1END LOOP1ELSELOOP1 l=1,NdIF(RA(l)=TRUE) , NDS(l)=NEND LOOP1LOOP1 l=IND+1 , NdIF(NDSO(l)=k 0 and NDS(l)=0) THEN IND=lGOTO 10END IFEND LOOP1END IFNST(k0,1)=NLOOP1 l=1 , NcIF(NCT0(l)=k0), THENIF(KND(l)工开关'or (KND(l)= I=NOD(l,1) IF(I=0), THENI=NOD(l,2)IF(I=0) , THENI=NOD(l,3) IF(I=0) , THEN30NCT(l)=0GOTO 40END IFEND IFEND IFELSEGOTO30END IFEND IF跳出循环3连通子集计数+1如果M