質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.48%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

1回答

1454閲覧

最小の回路・全域木をもとめるアルゴリズムの流れがわからない部分を意訳していただけませんか?

gyro16

総合スコア89

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

0クリップ

投稿2017/04/22 04:40

編集2017/04/23 01:48

###前提・実現したいこと
全頂点を巡る最小全域木
全域木の最小の重みを求めるアルゴリズムらしいですが、
nextMin()の使われ方、reach[]の変移などがわかりにくいのですが、日本語に意訳出来る方いませんか?

入力
5
-1 2 3 1 -1
2 -1 -1 4 -1
3 -1 -1 1 1
1 4 1 -1 3
-1 -1 1 3 -1

-1は点と点が接続していない
leng[x][y]は、x からy への辺の重み

全頂点をめぐる回路・全域木の最小の経路・全域木をもとめる

###発生している問題・エラーメッセージ

この辺りの処理の流れがわかりません

for (int i = 2; i < reach.length; i++) nextMin(); private void nextMin() { int min = Integer.MAX_VALUE; int xx = 0, yy = 0; for (int x = 0; x < leng.length; x++) { if (reach[x] == -1) continue; for (int y = 0; y < leng[x].length; y++) { if (reach[y] != -1||leng[x][y]==-1) continue; if (leng[x][y] < min) { xx = x; yy = y; min = leng[x][y]; } } } reach[yy] = min; }

###該当のソースコード

Java

1import java.util.Scanner; 2 3public class Main { 4 5 public static void main(String[] args){ 6 7 Scanner scan = new Scanner(System.in); 8 9 int n = scan.nextInt(); 10 MSTree mst = new MSTree(n); 11 12 for (int y = 0; y < n; y++) 13 for (int x = 0; x < n; x++) 14 mst.setLeng(x, y, scan.nextInt()); 15 16 System.out.println(mst.getMinTree()); 17 18 scan.close(); 19 System.exit(0); 20 } 21} 22 23class MSTree { 24 int[][] leng; 25 int[] reach; 26 27 public MSTree(int n) { 28 leng = new int[n][n]; 29 reach = new int[n]; 30 for (int i = 0; i < n; i++) 31 reach[i] = -1; 32 } 33 34 public int getMinTree() { 35 int min = Integer.MAX_VALUE; 36 int xx = 0, yy = 0; 37 for (int x = 0; x < leng.length; x++) 38 for (int y = x + 1; y < leng[x].length; y++) 39 if (leng[x][y] !=-1 && leng[x][y] < min) { 40 xx = x; 41 yy = y; 42 min = leng[x][y]; 43 } 44 reach[xx] = 0; 45 reach[yy] = min; 46 for (int i = 2; i < reach.length; i++) 47 nextMin(); 48 49 int total = 0; 50 for (int i = 0; i < reach.length; i++) 51 total += reach[i]; 52 return total; 53 } 54 55 private void nextMin() { 56 int min = Integer.MAX_VALUE; 57 int xx = 0, yy = 0; 58 for (int x = 0; x < leng.length; x++) { 59 if (reach[x] == -1) 60 continue; 61 for (int y = 0; y < leng[x].length; y++) { 62 if (reach[y] != -1||leng[x][y]==-1) 63 continue; 64 if (leng[x][y] < min) { 65 xx = x; 66 yy = y; 67 min = leng[x][y]; 68 } 69 } 70 } 71 reach[yy] = min; 72 } 73 74 public void setLeng(int x, int y, int length) { 75 leng[x][y] = length; 76 } 77 78}

###試したこと
課題に対してアプローチしたことを記載してください

###補足情報(言語/FW/ツール等のバージョンなど)
より詳細な情報

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

leng[x][y]が辺の重み=直接繋がっている頂点xとyとの距離

と考えればいいと思いますが、

reachの目的(あるいはそれが表現している情報)は以下の2つだと思います。

  • 巡回済みの点と巡回していない点の集合を分けること
  • 巡回済みの点pがp以外の巡回済みの点から到達するための最小距離

またnextMinは、与えられたreachで表される巡回済みの点の集合から直接到達可能な未巡回点の中で最短距離で到達可能なものを一つだけ選びそれをreachへ追加する(つまり未巡回から巡回済みに変更する)ための処理。

というふうに見えます。

投稿2017/04/22 05:37

編集2017/04/22 07:33
KSwordOfHaste

総合スコア18394

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.48%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問