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