// グラフ理論：クラスカル アルゴリズム
// 無向グラフの最小全域木を求める
import java.awt.Point;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.stream.Collectors;
public class Main {
static int[][] a2iPath0Matrix = {
//A B C D E F G H
{ 0, 3, 0, 4, 0, 0, 0, 0 }, // A
{ 3, 0, 2, 0, 1, 0, 0, 0 }, // B
{ 0, 2, 0, 0, 8, 12, 0, 0 }, // C
{ 4, 0, 0, 0, 11, 0, 9, 0 }, // D
{ 0, 1, 8, 11, 0, 6, 0, 7 }, // E
{ 0, 0, 12, 0, 6, 0, 0, 5 }, // F
{ 0, 0, 0, 9, 0, 0, 0, 10 }, // G
{ 0, 0, 0, 0, 7, 5, 10, 0 }, // H
};
static int iPathMatrixSize = a2iPath0Matrix.length;
static int[][] a2iPath1Matrix = new int[iPathMatrixSize][iPathMatrixSize];
static ArrayList<Point> daloWeightPosList = new ArrayList<Point>();
static HashMap<Integer, Integer> dhmNodeAffiliatMap = new HashMap<Integer, Integer>();
public static void main(String[] args) {
CheckWeight(a2iPath0Matrix, daloWeightPosList);
Point WP = null;
do {
WP = MinWeight(a2iPath0Matrix, daloWeightPosList);
if (WP != null) {
Integer NAY = dhmNodeAffiliatMap.get(WP.y);
Integer NAX = dhmNodeAffiliatMap.get(WP.x);
int NAU = -1; // Node Affiliat Unity
if (NAX == null | NAY == null) {
NAY = NAY != null ? NAY : WP.y;
NAX = NAX != null ? NAX : WP.x;
NAU = Math.min(NAX, NAY);
} else if (NAX != NAY) {
NAU = Math.min(NAX, NAY);
}
System.out.printf("NAU: %d,%n", NAU);
System.out.println();
if (0 <= NAU) {
a2iPath1Matrix[WP.y][WP.x] = a2iPath0Matrix[WP.y][WP.x];
System.out.println("a2iPath1Matrix");
Display_PathMatrix(a2iPath1Matrix);
// a2iPath0Matrix[WP.y][WP.x] = 0;
// System.out.println("a2iPath0Matrix");
// Display_PathMatrix(a2iPath0Matrix);
dhmNodeAffiliatMap.put(WP.y, NAU);
dhmNodeAffiliatMap.put(WP.x, NAU);
for (Integer k : dhmNodeAffiliatMap.keySet()) {
int NA = dhmNodeAffiliatMap.get(k);
if (NAX == NA | NAY == NA) {
dhmNodeAffiliatMap.put(k, NAU);
}
}
System.out.println("dhmNodeAffiliatMap");
Display_NodeAffiliatMap();
}
a2iPath0Matrix[WP.y][WP.x] = 0;
// System.out.println("a2iPath0Matrix");
// Display_PathMatrix(a2iPath0Matrix);
}
} while (WP != null);
System.out.println("a2iPath1Matrix");
Display_PathMatrix(a2iPath1Matrix);
System.out.println("dhmNodeAffiliatMap");
Display_NodeAffiliatMap();
MirrorhMatrix(a2iPath1Matrix);
System.out.println("a2iPath1Matrix:Mirror");
Display_PathMatrix(a2iPath1Matrix);
}
static Point MinWeight(int[][] a2iPM, ArrayList<Point> daloWPL) {
int Min = Integer.MAX_VALUE;
int ID = -1;
Point WP = null;
for (int i = 0; i < daloWPL.size(); i++) {
WP = daloWPL.get(i);
int w = a2iPM[WP.y][WP.x];
if (0 < w & w < Min) {
Min = w;
ID = i;
}
}
WP = 0 <= ID ? daloWPL.remove(ID) : null;
if (WP != null) {
// a2iPM[WP.y][WP.x] = 0;
}
return WP;
}
static void CheckWeight(int[][] a2iPM, ArrayList<Point> daloWPL) {
for (int y = 0; y < a2iPM.length; y++) {
for (int x = 0; x < a2iPM[y].length; x++) {
if (a2iPM[y][x] != a2iPM[x][y]) {
System.out.printf("a2iPM[%d][%d]!=a2iPM[&d][%d]%n", y, x, x, y);
}
}
}
for (int y = 0; y < a2iPM.length; y++) {
for (int x = 0; x < a2iPM[y].length; x++) {
if (y <= x) {
a2iPM[y][x] = 0;
}
if (0 < a2iPM[y][x]) {
daloWPL.add(new Point(x, y));
}
}
}
Display_PathMatrix(a2iPM);
}
static void MirrorhMatrix(int[][] a2iPM) {
for (int y = 0; y < a2iPM.length; y++) {
for (int x = 0; x < a2iPM[y].length; x++) {
int Max = Math.max(a2iPM[y][x], a2iPM[x][y]);
a2iPM[y][x] = Max;
a2iPM[x][y] = Max;
}
}
}
static void Display_PathMatrix(int[][] a2iPM) {
for (int y = 0; y < a2iPM.length; y++) {
for (int x = 0; x < a2iPM[y].length; x++) {
System.out.print(a2iPM[y][x] + ", ");
}
System.out.println();
}
System.out.println();
}
static void Display_NodeAffiliatMap() {
List<Integer> dlNodeAffiliatKeyList = dhmNodeAffiliatMap
.keySet()
.stream()
.sorted()
.collect(Collectors.toList());
for (Integer k : dlNodeAffiliatKeyList) {
int NA = dhmNodeAffiliatMap.get(k);
System.out.printf("[%d]:%d, ", k, NA);
}
System.out.println();
System.out.println();
}
}
|
|
掲示板に書き込む前に必ず この ”注意書き”を お読み下さい．