拓?fù)渚W(wǎng)絡(luò)連通性算法

1、網(wǎng)絡(luò)連通性算法網(wǎng)絡(luò)定義節(jié)點(diǎn)與支路的集合，該集合中的節(jié)點(diǎn)與支路的連接關(guān)系可通過(guò)一節(jié)點(diǎn)-節(jié)點(diǎn)關(guān)聯(lián)矩陣A充分表達(dá)：A=aijnm i,j=1,2,n0,當(dāng)節(jié)點(diǎn)i與節(jié)點(diǎn)j間無(wú)支路直接相連，1，當(dāng)節(jié)點(diǎn)i與節(jié)點(diǎn)j間有支路直接相連。n網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)連通性算法理論算法：稱(chēng)矩陣A為網(wǎng)絡(luò)一級(jí)連通矩陣，A2為二級(jí)連通矩陣，2 2 A=AA=aijnxni,j=1,2,n"0,當(dāng)節(jié)點(diǎn)i與節(jié)點(diǎn)j間無(wú)支路直接且經(jīng)第1，當(dāng)節(jié)點(diǎn)i與節(jié)點(diǎn)j間有支路直接或經(jīng)第k=1,2,n，i,j式中：a式中:a2ij=丿An-1為n-1級(jí)連通矩陣。3節(jié)點(diǎn)k相連,3節(jié)點(diǎn)k相連。一n個(gè)An-1=AAA =an-1ijnxni,j=1,2,n

2、式中：n-10當(dāng)節(jié)點(diǎn)i與節(jié)點(diǎn)j間無(wú)支路直接且經(jīng)其它1,2，-，n-2個(gè)節(jié)點(diǎn)相連，a ij=1，當(dāng)節(jié)點(diǎn)i與節(jié)點(diǎn)j間有支路直接或經(jīng)其它1,2,， n-2個(gè)節(jié)點(diǎn)相連。矩陣An-1的每一線性無(wú)關(guān)的行或列中“ 1 ”元素對(duì)應(yīng)的節(jié)點(diǎn)均處于同一連通子集中。實(shí)際算法：若矩陣A第i (i=1,2,n)行元素與第j (j=i+1,i+2,n)行元素中第k列元素aik 和ak同為“1”，則第j行中的其它“ 1”元素均填入第i行的相應(yīng)列中。結(jié)果矩陣 A第 i行中所有“ 1”元素對(duì)應(yīng)的節(jié)點(diǎn)處于同一連通子集中。數(shù)據(jù)定義Nc元件數(shù)Nd節(jié)點(diǎn)數(shù)NOD ( Nc,3)每個(gè)元件的節(jié)點(diǎn)編號(hào)i、j、kKND ( Nc)每個(gè)元件的種類(lèi)(

3、斷路器、隔離開(kāi)關(guān)、母線、線路、變壓器 )CNT (Nc)每個(gè)開(kāi)關(guān)元件的分、合狀態(tài)(邏輯型，例如：合為“真”,分為“假”) NDS0 (Nd)每個(gè)節(jié)點(diǎn)初始所在連通子集編號(hào)NDS ( Nd)每個(gè)節(jié)點(diǎn)所在連通子集編號(hào)NCT0 (Nc)每個(gè)元件初始所在連通子集編號(hào)NCT ( Nc)每個(gè)元件所在連通子集編號(hào)NST( Ns，3) 每個(gè)原始連通子集內(nèi) 子集號(hào)，子集內(nèi)節(jié)點(diǎn)數(shù)，子集內(nèi)首位節(jié)點(diǎn)Ns最大可能連通子集數(shù)RA (Nd) 節(jié)點(diǎn)關(guān)聯(lián)矩陣第 i 行，邏輯型RB (Nd)節(jié)點(diǎn)關(guān)聯(lián)矩陣第j行，邏輯型6 / 6IND=NST(k 0,3)N=0LOOP1 l=1 ，NdIF (NDS0(l) =k0)，END LO

4、OP1檢驗(yàn)第k0個(gè)連通子集的連通性子程序CNTS(k °)初始化 取第 k0 個(gè)連通子集的首位節(jié)點(diǎn)號(hào) 連通子集數(shù)置 0 l 從 1 至 Nd 循環(huán)NDS(l)=0 第 k0 個(gè)連通子集的節(jié)點(diǎn) l 的子集號(hào)臨時(shí)置 0連通性檢驗(yàn)大循環(huán)10 NSUM=1節(jié)點(diǎn)關(guān)聯(lián)矩陣“真”元素計(jì)數(shù)置為 1LOOP1 l=1 ，Nd RA(l)=FALSEEND LOOP1RA(IND)=TRUEM=1l 從 1 至 Nd 循環(huán)第 k0 個(gè)連通子集中第 IND 行第 l 列元素置為“假”節(jié)點(diǎn)關(guān)聯(lián)矩陣第 IND 行對(duì)角元素置 1節(jié)點(diǎn)關(guān)聯(lián)矩陣第 IND 行 “真”元素計(jì)數(shù)置為 1形成節(jié)點(diǎn)關(guān)聯(lián)矩陣的第LOOP1 l

5、=1,NcIND 行 RAl 從 1 至 Nc 循環(huán)IF(NCT0(l)=k 0)，THENIF(KND(I)工開(kāi)關(guān)'or (KND(I)='開(kāi)關(guān)'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 的各端節(jié)點(diǎn)號(hào)如果節(jié)點(diǎn)號(hào)I等于節(jié)點(diǎn)號(hào)IND，則如果節(jié)點(diǎn)號(hào)J不等于0和I，則關(guān)聯(lián)矩陣第IND行第J列元素置為“真” 關(guān)聯(lián)矩陣第 IND 行“真”元素計(jì)數(shù) +1如果節(jié)點(diǎn)號(hào)K不等于0和I和J,則 關(guān)聯(lián)矩陣第IND行第K列元素置

7、為“真” 關(guān)聯(lián)矩陣第 IND 行“真”元素計(jì)數(shù) +1如果節(jié)點(diǎn)號(hào)J等于節(jié)點(diǎn)號(hào)IND，則 如果節(jié)點(diǎn)號(hào)I不等于0和I，則 關(guān)聯(lián)矩陣第 IND 行第 I 列元素置為“真” 關(guān)聯(lián)矩陣第 IND 行“真”元素計(jì)數(shù) +1如果節(jié)點(diǎn)號(hào)K不等于0和I和J,則 關(guān)聯(lián)矩陣第IND行第K列元素置為“真” 關(guān)聯(lián)矩陣第 IND 行“真”元素計(jì)數(shù) +1如果節(jié)點(diǎn)號(hào)K等于節(jié)點(diǎn)號(hào)IND，則 如果節(jié)點(diǎn)號(hào)I不等于0和K，貝U 關(guān)聯(lián)矩陣第 IND 行第 I 列元素置為“真” 關(guān)聯(lián)矩陣第 IND 行“真”元素計(jì)數(shù) +1如果節(jié)點(diǎn)號(hào)J不等于0和I和K，貝URA(J)=TRUEM=M+1END IFEND IF關(guān)聯(lián)矩陣第IND行第J列元素置為“

8、真” 關(guān)聯(lián)矩陣第IND行“真”元素計(jì)數(shù)+1END IFEND IFEND L00P1將節(jié)點(diǎn)連通矩陣第IND+1Nd行與第IND行比較，尋找包含節(jié)點(diǎn)IND的連通子集LOOP1 WHILE(M v NST(ko,2) and M>NSUM)當(dāng) M v子集 ko 節(jié)點(diǎn)數(shù)且有新“真”元素NSUM=M出現(xiàn)時(shí)，循環(huán)LOOP2 ld=IND+1，Nd ld 自 IND+1 至 Nd 循環(huán)IF (NDSO(ld)=ko and RA(ld)=FALSE and NDS(ld)=0)，THEN 當(dāng)LOOP3 l=1，NdRB(I)=FALSEEND LOOP3RB(ld)=TRUE形成節(jié)點(diǎn)關(guān)聯(lián)矩陣的第LO

9、OP3 l=1，NcIF(NCT0(l)=k o)，l自1至nd循環(huán) 關(guān)聯(lián)矩陣第ld行第l列元素置為“假”節(jié)點(diǎn)關(guān)聯(lián)矩陣第Id節(jié)點(diǎn)ld屬于連通子 集k。，且關(guān)聯(lián)矩陣第IND行第ld列元素為“假”，且未找到 節(jié)點(diǎn)ld新連通子集 號(hào)時(shí)，循環(huán) 行對(duì)角元素置1Id 行 RBTHENIF(KND(l)工開(kāi)關(guān)or (KND(l)=l自1至Nc循環(huán)如果元件l屬于原連通子集ko,則 '開(kāi)關(guān)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的各端節(jié)

10、點(diǎn)號(hào)如果節(jié)點(diǎn)號(hào)I等于節(jié)點(diǎn)號(hào)ld，則如果節(jié)點(diǎn)號(hào)J不等于0和I，則 關(guān)聯(lián)矩陣第ld行第J列元素置為“真”RB(K)=TRUE END IF關(guān)聯(lián)矩陣第ld行第K列元素置為“真”IF(K工0 and Km I and K工J)，THEN如果節(jié)點(diǎn)號(hào)K不等于0和I和J,則END IFIF(J=ld)，THENIF(I m 0 and Im J)，THENRB(I)=TRUE如果節(jié)點(diǎn)號(hào)J等于節(jié)點(diǎn)號(hào)ld，則如果節(jié)點(diǎn)號(hào)I不等于0和J,則關(guān)聯(lián)矩陣第ld行第I列元素置為“真”END IFIF(Km 0 and Km I and Km J)，THEN如果節(jié)點(diǎn)號(hào)K不等于0和I和J,貝URB(K)=TRUE關(guān)聯(lián)矩陣第ld

11、行第K列元素置為“真”END IFEND IFIF(K=ld)，THEN如果節(jié)點(diǎn)號(hào)K等于節(jié)點(diǎn)號(hào)ld，貝UIF(I m0 and Im K)，THEN如果節(jié)點(diǎn)號(hào)I不等于0和K，貝URB(I)=TRUE關(guān)聯(lián)矩陣第ld行第I列元素置為“真”END IFIF(Jm0 and Jm I and Jm K)，THEN如果節(jié)點(diǎn)號(hào)K不等于0和I和J,則RB(J)=TRUE關(guān)聯(lián)矩陣第ld行第J列元素置為“真”END IFEND IFEND IF END IFEND LOOP3L00P3 1=1 , Nd l 自 1 至 Nd 循環(huán)IF(NDSO(l)=k o and RA(I) and RB(I) , THEN

12、L00P4 j=1, Nd jl 自 1 至 Nd 循環(huán)IF(RA(j)=FALSE and RB(j)=TRUE) , THENRA(j)=TRUE 行 IND 列 j 置為“真” M=M+1END IF如果節(jié)點(diǎn)I屬于原連通子集 k0,且 關(guān)聯(lián)矩陣第IND行第I列元素與第 ld行第I列元素同為“真”，貝U 如果第IND行第j列元素為“假”， 且Id行第j列元素為“真”，則關(guān)聯(lián)矩陣第IND行“真”元素計(jì)數(shù)+1END LOOP4將原始連通子集k0內(nèi)的連通子集數(shù)置為NI自1至Nc循環(huán)如果元件I屬于初始連通子集k0,則'開(kāi)關(guān)and CNT（I）= 合），THENI=元件I的第一個(gè)節(jié)點(diǎn)號(hào) 如果

13、I為0，貝UI=元件I的第二個(gè)節(jié)點(diǎn)號(hào) 如果I為0，貝UI=元件I的第三個(gè)節(jié)點(diǎn)號(hào) 如果I為0，貝U 元件I所在連通子集號(hào)為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)工開(kāi)關(guān)'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跳出循環(huán)3連通子集計(jì)數(shù)+1如果M