/*
* @input: 一個有向無環帶權圖，表述為一個二維數組graph[n][n]
* @output: 最小生成樹tree[n-1][3],tree[i][0]及tree[i][1]為邊之頂點，tree[i][2]為權
*/
public class MiniSpanTreeTest
{
static int[][] graph={
{1000,6,1,5,1000,1000},
{6,1000,5,1000,3,1000},
{1,5,1000,5,6,4},
{5,1000,5,1000,1000,2},
{1000,3,6,1000,1000,6},
{1000,1000,4,2,6,1000},
};
static int v=0;
static int[][] tree;
public static void main(String[] args)
{
MiniSpanTree miniSpanTree=new MiniSpanTree();
miniSpanTree.input(graph, v);
tree=miniSpanTree.getTree();
for(int i=0; i<graph.length-1; i++){
System.out.println("邊：" + tree[i][0] + "-" + tree[i][1] + " 權：" + tree[i][2]);
}
}
}
class MiniSpanTree
{
private int[][] graph;
private int v;
private int[][] tree;
private boolean[] s;
void input(int[][] graph, int v)
{
this.graph=graph;
this.v=v;
tree=new int[graph.length-1][];
s=new boolean[graph.length];
for(boolean i : s) i=false;
s[v]=true;
calculate();
}
void calculate()
{
for(int i=0; i<graph.length-1; i++){
int[][] edge ={{0,0,1000,},};
for(int j=0; j<graph.length; j++){
for(int k=0; s[j]==true && k<graph.length; k++){
if(s[k]==false && graph[j][k]<edge[0][2]){
edge[0][0]=j;
edge[0][1]=k;
edge[0][2]=graph[j][k];
}
}
}
tree[i]=edge[0];
s[tree[i][1]]=true;
}
}
int[][] getTree()
{
return tree;
}
}
結果如下：
邊：0-2 權：1
邊：2-5 權：4
邊：5-3 權：2
邊：2-1 權：5
邊：1-4 權：3