隣接行列から連結判定


※上記の広告は60日以上更新のない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 じゃないけどさくっと書いちゃったのでうp
#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 俺氏ね
|新しいページ|検索|ページ一覧|RSS|@ウィキご利用ガイド | 管理者にお問合せ
|ログイン|