隣接行列から連結判定 - C/C++の宿題のまとめ@Wiki

162 ：デフォルトの名無しさん ：2005/11/01(火) 17:20:58

[1] 授業単元：プログラム演習＆情報数学
[2] 問題文(含コード&リンク)：
隣接行列を入力して、連結かどうかを判定するプログラムを作成せよ。
連結かどうかの判定は、隣接行列をA、 位数（頂点の数）をmとしたとき、
A+A^2+…+A^(m-1) の成分に0があるものが連結ではないと言える。

[3] 環境
　[3.1] OS： Linux
　[3.2] コンパイラ名とバージョン： gcc
　[3.3] 言語： C
[4] 期限： 2005年11月3日まで
[5] その他の制限： 特に無し

以上の内容なのですが、分かる方がいましたら教えてください。
よろしくお願いします。

163 ：デフォルトの名無しさん ：2005/11/01(火) 17:24:50

>>162
ちょっと用語がおかしいかも知れないが、ホップ数m-1以下で
到達する経路の無い奴が有るかどうか調べろってこと？

とりあえず行列のn乗返す関数作ってくる

164 ：162：2005/11/01(火) 17:32:38

>>163
はい、そういう意味の問題です。

165 ：デフォルトの名無しさん ：2005/11/01(火) 17:56:36

>>162 163 じゃないけどさくっと書いちゃったのでうｐ
#include <stdio.h>
#define m 5
int main() {
　int i, j, k, l;
　int A[m][m], B[m][m], C[m][m], tmpB[m][m];
　/* 初期化 (C: 0，B: 単位行列) */
　for (i = 0; i < m; ++i) {
　　for (j = 0; j < m; ++j)
　　　A[i][j] = B[i][j] = C[i][j] = 0;
　　B[i][i] = 1;
　}
　/* 連結してるところを 1 ，その他を 0 に設定 */
　A[0][1] = A[0][2] = A[2][3] = A[3][4] = A[3][1] = A[4][2] = 1;

166 ：デフォルトの名無しさん ：2005/11/01(火) 17:59:36

　for (l = 1; l <= m-1; ++l) { /* C = sum_k A^k */
　　for (i = 0; i < m; ++i)
　　　for (j = 0; j < m; ++j)
　　　　for (k = 0, tmpB[i][j] = 0; k < m; ++k)
　　　　　tmpB[i][j] += B[i][k] * A[k][j]; /* B = A^k は前の値を使って計算 */
　　for (i = 0; i < m; ++i)
　　　for (j = 0; j < m; ++j)
　　　　B[i][j] = tmpB[i][j], C[i][j] += B[i][j];
　}
　for (i = 0; i < m; ++i)
　　for (j = 0; j < m; ++j)
　　　if (C[i][j] == 0)
　　　　printf("%d -> %d cannot approve\n", i, j);
}

オーダーは for 文を数えればわかるように O(V^4)．
Floyd Warshall あたりを使えば O(V^3) でできるはずなので，不利なアルゴリズムと思う．

167 ：165：2005/11/01(火) 18:02:00

>>165 コメントがミスリーディングだった．C = sum_k A^l．

168 ：165：2005/11/01(火) 18:03:11

>>167 C = sum_l A^l 俺氏ね