Re: [問題] 30 ITSA-Problem2.圖形簡單性質
最簡單的方法，用 Floyd-Warshall 演算法
原本題目給的 adjacency matrix...
權重要先改一下，相連的邊長是 1，未相連的是 infinity
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < n; ++k) {
matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);
}
}
}
時間複雜度 O(n^3)
※ 引述《goodwayhow 看板: C_and_CPP》之銘言：
: 開發平台(Platform): (Ex: VC++, GCC, Linux,
: C++
: 問題(Question)：
: 想請問這題關於無向圖diameter判斷多大,會不會有任兩頂點都不會相連?
: http://140.116.249.152/e-Tutor/mod/programming/view.php?id=19474
: 餵入的資料(Input)：
: 3
: 0 1 1
: 1 0 1
: 1 1 0
: 預期的正確結果(Expected Output)：
: 3 3 2 1
: 錯誤結果(Wrong Output)：
: 這提是放在etuto上題目,所以不清楚背後測資怎樣,但自行判斷輸出都沒問題
: 程式碼(Code)：(請善用置底文網頁, 記得排版)
: 這是我diameter的想法,不知版大有無更好的方法建議小弟
: for(int i=0;i<n;i++)
: {
: for(int j=0;j<n;j++)
: {
: if(i!=j)
: {
: if(a[i][j]==0)
: { //先找到不相連的座標
: temp1[s1++]=j;//紀錄y座標j
: temp2=temp1[0];
: for(int k=0;k<n;k++)
: {
: if(a[temp2][k]==1)//然後把y座標放到x,從x
: 那一列開始找到相連點
: {
: diam++;
: temp2=k;
: break;
: }
: if(diam==n-1)
: {
: break;
: }
: }
: }
: }
: }
: }
: 補充說明(Supplement)：
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.47.74.121
※ 文章網址: http://www.ptt.cc/bbs/C_and_CPP/M.1399284239.A.572.html
推
05/05 18:12, , 1F
05/05 18:12, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：