如何在C語(yǔ)言中采用warshall算法判斷一個(gè)無(wú)向圖是否連通？所謂無(wú)向圖連通性是指任意兩點(diǎn)都有一條路徑要到達(dá)所以我們需要驗(yàn)證任意兩點(diǎn)a和B之間是否有路徑Warshall算法是一種動(dòng)態(tài)規(guī)劃算法。首先，讓

如何在C語(yǔ)言中采用warshall算法判斷一個(gè)無(wú)向圖是否連通？

所謂無(wú)向圖連通性是指任意兩點(diǎn)都有一條路徑要到達(dá)

所以我們需要驗(yàn)證任意兩點(diǎn)a和B之間是否有路徑

Warshall算法是一種動(dòng)態(tài)規(guī)劃算法。

首先，讓連通矩陣為m，I，J連通，然后mij=1，否則mij=0

讓可能的中點(diǎn)為C，C=0

檢查所有ij組合，如果mic==1和MCJ==1，則mij變?yōu)?，否則它不會(huì)改變

然后C，如果C大于點(diǎn)數(shù)，則退出

最后，如果m都是1，那么它就是一個(gè)連通圖