「隣接行列から連結判定」の編集履歴（バックアップ）一覧はこちら
「隣接行列から連結判定」(2005/11/07 (月) 06:06:05) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
<dl>
<dt>162 ：<a href="mailto:sage"><b>デフォルトの名無しさん</b></a>
：2005/11/01(火) 17:20:58</dt>
<dd>[1] 授業単元：プログラム演習＆情報数学<br>
[2] 問題文(含コード&リンク)：<br>
隣接行列を入力して、連結かどうかを判定するプログラムを作成せよ。<br>
連結かどうかの判定は、隣接行列をA、
位数（頂点の数）をmとしたとき、<br>
A+A^2+…+A^(m-1)
の成分に0があるものが連結ではないと言える。<br>
<br>
[3] 環境<br>
[3.1] OS： Linux<br>
[3.2] コンパイラ名とバージョン： gcc<br>
[3.3] 言語： C<br>
[4] 期限： 2005年11月3日まで<br>
[5] その他の制限： 特に無し<br>
<br>
以上の内容なのですが、分かる方がいましたら教えてください。<br>
よろしくお願いします。<br>
<br></dd>
<dt>163 ：<a href="mailto:sage"><b>デフォルトの名無しさん</b></a>
：2005/11/01(火) 17:24:50</dt>
<dd><a href="http://pc8.2ch.net/test/read.cgi/tech/1130431335/162" target=
"_blank">>>162</a><br>
ちょっと用語がおかしいかも知れないが、ホップ数m-1以下で<br>
到達する経路の無い奴が有るかどうか調べろってこと？<br>
<br>
とりあえず行列のn乗返す関数作ってくる<br>
<br></dd>
<dt>164 ：<a href="mailto:sage"><b>162</b></a>：2005/11/01(火) 17:32:38</dt>
<dd><a href="http://pc8.2ch.net/test/read.cgi/tech/1130431335/163" target=
"_blank">>>163</a><br>
はい、そういう意味の問題です。<br>
<br></dd>
<dt>165 ：<a href="mailto:sage"><b>デフォルトの名無しさん</b></a>
：2005/11/01(火) 17:56:36</dt>
<dd><a href="http://pc8.2ch.net/test/read.cgi/tech/1130431335/162" target=
"_blank">>>162</a> 163
じゃないけどさくっと書いちゃったのでうｐ<br>
#include <stdio.h><br>
#define m 5<br>
int main() {<br>
int i, j, k, l;<br>
int A[m][m], B[m][m], C[m][m], tmpB[m][m];<br>
/* 初期化 (C: 0，B: 単位行列) */<br>
for (i = 0; i < m; ++i) {<br>
for (j = 0; j < m; ++j)<br>
A[i][j] = B[i][j] = C[i][j] = 0;<br>
B[i][i] = 1;<br>
}<br>
/* 連結してるところを 1 ，その他を 0 に設定 */<br>
A[0][1] = A[0][2] = A[2][3] = A[3][4] = A[3][1] = A[4][2] = 1;<br>
<br></dd>
<dt>166 ：<a href="mailto:sage"><b>デフォルトの名無しさん</b></a>
：2005/11/01(火) 17:59:36</dt>
<dd> for (l = 1; l <= m-1; ++l) { /* C = sum_k A^k */<br>
for (i = 0; i < m; ++i)<br>
for (j = 0; j < m; ++j)<br>
for (k = 0, tmpB[i][j] = 0; k < m; ++k)<br>
tmpB[i][j] += B[i][k] * A[k][j]; /* B = A^k
は前の値を使って計算 */<br>
for (i = 0; i < m; ++i)<br>
for (j = 0; j < m; ++j)<br>
B[i][j] = tmpB[i][j], C[i][j] += B[i][j];<br>
}<br>
for (i = 0; i < m; ++i)<br>
for (j = 0; j < m; ++j)<br>
if (C[i][j] == 0)<br>
printf("%d -> %d cannot approve\n", i, j);<br>
}<br>
<br>
オーダーは for 文を数えればわかるように O(V^4)．<br>
Floyd Warshall あたりを使えば O(V^3)
でできるはずなので，不利なアルゴリズムと思う．<br>
<br></dd>
<dt>167 ：<a href="mailto:sage"><b>165</b></a>：2005/11/01(火) 18:02:00</dt>
<dd><a href="http://pc8.2ch.net/test/read.cgi/tech/1130431335/165" target=
"_blank">>>165</a> コメントがミスリーディングだった．C =
sum_k A^l．<br>
<br></dd>
<dt>168 ：<a href="mailto:sage"><b>165</b></a>：2005/11/01(火) 18:03:11</dt>
<dd><a href="http://pc8.2ch.net/test/read.cgi/tech/1130431335/167" target=
"_blank">>>167</a> C = sum_l A^l 俺氏ね</dd>
</dl>
表示オプション
横に並べて表示：
変化行の前後のみ表示：
