亚洲美女一区二区三区,亚洲小说图区综合在线,亚洲一区免费观看

JAVA—咖啡館

——?dú)g迎訪問rogerfan的博客，常來《JAVA——咖啡館》坐坐，喝杯濃香的咖啡，彼此探討一下JAVA技術(shù)，交流工作經(jīng)驗(yàn)，分享JAVA帶來的快樂！本網(wǎng)站部分轉(zhuǎn)載文章，如果有版權(quán)問題請(qǐng)與我聯(lián)系。

【轉(zhuǎn)】圖－傳遞閉包

圖－傳遞閉包

圖的傳遞閉包是指修正后的鄰接矩陣表示的圖。(見Graph 圖－鄰接矩陣法 )

在多個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)可以到按照方向到達(dá)一定的節(jié)點(diǎn)，這叫圖的連通性。有種方法直接告訴我們，圖中的兩個(gè)節(jié)點(diǎn)是否可以聯(lián)通，這里說的是WarShall算法。

WarShall的基本原理是，如果A可以到達(dá)B，且C可以到達(dá)A，則C可以到達(dá)B。通過對(duì)鄰接矩陣的修正可以做到這點(diǎn)。隨然這里舉例是將兩步可并成一步，但數(shù)學(xué)上可以證明這種修正可以達(dá)到任意步驟。

下面是代碼：

class WarShall {
2

private boolean[][] adjMat;
3

WarShall(int size) {
5

adjMat = new boolean[size][size];
6

}
7

void connect(int from, int to) {
9

adjMat[from][to] = true;
10

}
11

boolean isConnect(int from, int to) {
13

return adjMat[from][to];
14

}
15

void warshall() { //warshall算法
17

for(int y=0; y<adjMat.length; y++) //查找每一行
18

for(int x=0; x<adjMat.length; x++) // 查找每個(gè)單元格
19

if(adjMat[y][x]) //如果 y 可以到達(dá) x
20

for(int z=0; z<adjMat.length; z++) //查找所有行的y列
21

//如果 z 可以到達(dá)y ，說明z 可以直接到達(dá)x
22

if(adjMat[z][y]) adjMat[z][x] = true;
23

}
25

boolean[][] getConnections() {
27

return adjMat;
28

}
29

public static void main(String[] args) {
31

WarShall w = new WarShall(5);
32

w.connect(0,2);
33

w.connect(1,0);
34

w.connect(1,4);
35

w.connect(3,4);
36

w.connect(4,2);
37

for(boolean[] a: w.getConnections()) {
38

for(boolean b: a) System.out.print(b + " ");
39

System.out.println();
40

}
41

w.warshall();
42

System.out.println("==================");
43

for(boolean[] a: w.getConnections()) {
44

for(boolean b: a) System.out.print(b + " ");
45

System.out.println();
46

}
47

assert w.isConnect(3,2);
49

}
50

}

posted on 2008-05-28 15:54 rogerfan 閱讀(942) 評(píng)論(0) 編輯收藏所屬分類: 【JAVA算法】

新用戶注冊(cè) 刷新評(píng)論列表


只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關(guān)文章: 【轉(zhuǎn)】通過分析 JDK 源代碼研究 Hash 存儲(chǔ)機(jī)制【轉(zhuǎn)】圖－最小樹【轉(zhuǎn)】圖－拓?fù)渑判?/a> 【轉(zhuǎn)】圖－傳遞閉包【轉(zhuǎn)】圖－每一對(duì)端點(diǎn)間的最小距離【轉(zhuǎn)】圖－代權(quán)最小樹【轉(zhuǎn)】圖－最小路徑

JAVA—咖啡館

公告

常用鏈接

留言簿(17)

隨筆分類(542)

隨筆檔案(438)

文章分類(182)

文章檔案(142)

新聞分類

※→ 【JAVA文檔】

※→ 【親人博客】

※→ 【休閑娛樂】

※→ 【友情鏈接】

※→ 【學(xué)習(xí)網(wǎng)站】

※→ 【服務(wù)網(wǎng)站】

※→ 【著名網(wǎng)站】

※→ 【阿里博客】

最新隨筆

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

圖－傳遞閉包