日韩亚洲欧美综合,亚洲综合激情网,亚洲日本高清

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

圖－傳遞閉包

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

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

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

下面是代碼：

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++) // 查找每個單元格
19

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

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

//如果 z 可以到達y ，說明z 可以直接到達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 閱讀(941) 評論(0) 編輯收藏所屬分類: 【JAVA算法】

新用戶注冊刷新評論列表


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




網(wǎng)站導航: 博客園 IT新聞 Chat2DB C++博客博問
相關(guān)文章: 【轉(zhuǎn)】通過分析 JDK 源代碼研究 Hash 存儲機制【轉(zhuǎn)】圖－最小樹【轉(zhuǎn)】圖－拓撲排序【轉(zhuǎn)】圖－傳遞閉包【轉(zhuǎn)】圖－每一對端點間的最小距離【轉(zhuǎn)】圖－代權(quán)最小樹【轉(zhuǎn)】圖－最小路徑

JAVA—咖啡館

公告

常用鏈接

留言簿(17)

隨筆分類(542)

隨筆檔案(438)

文章分類(182)

文章檔案(142)

新聞分類

※→ 【JAVA文檔】

※→ 【親人博客】

※→ 【休閑娛樂】

※→ 【友情鏈接】

※→ 【學習網(wǎng)站】

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

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

※→ 【阿里博客】

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

圖－傳遞閉包