遊戲中會用到。
最近共同祖先
等價有限狀态機
實體學Hoshen-Kopelman算法:就是對網格中的像素進行分塊
Hinley-Milner多态類型推斷
Kruskai最小生成樹
Fortran等價語句編譯
形态學開閉屬性
Matlab中關于圖像處理的bwlabel函數
一個N×N的矩陣,判斷頂部和底部是否連通就是滲透問題。
下圖中左側的矩陣能滲透,右側矩陣不能滲透。
滲透問題在電學、流體力學、社會交際中都有應用。
在遊戲中可能需要生成一張地圖,但是作為地圖肯定是需要連通的。那麼如何保證生成的地圖一定是連通的呢?下圖展示了地圖生成的過程,白點表示能夠到達的地方,黑點表示障礙物,藍點表示能夠連通的地方。生成地圖的時候就是不斷增加白點,直到上下能夠連通為止。
為了判斷能否滲透,計算的過程中會增加一個虛拟的節點,這樣就把滲透問題簡化成判斷兩個節點能否連通。下圖展示了虛拟節點示意圖。