?? getlittletree.java.bak
字號:
import java.io.*;
public class GetLittleTree{
public int dim = 0; //記錄圖中結點數
public int[] tem; //用來暫時緩存圖中的數據
public int[][] edge; //使用鄰接矩陣表示圖
public int[][] tree; //用來存放最小生成數的鄰接矩陣
public int[] count; //用來記錄取去結點
public int cop = 1 ;//結點計數器
StreamTokenizer st;
FileOutputStream fw;
public GetLittleTree()throws IOException ,FileNotFoundException{
Reader r = new BufferedReader(new InputStreamReader(new FileInputStream("in.txt")));
st = new StreamTokenizer(r);
fw = new FileOutputStream("out.txt");
st.nextToken();
st.pushBack();
st.nextToken();
dim = (int) st.nval; //獲取圖中的結點數
count = new int[dim];
count[0] = 1; //對于邊割法可以任意選取初始點,不仿取第一個結點作為開始結點
tem = new int[dim*dim];
edge = new int[dim][dim];
tree = new int[dim][dim];
int acc = 0;
int k = 0;
while ((st.nextToken()) != st.TT_EOF) {
st.pushBack();
st.nextToken();
tem[acc++] = (int) st.nval;
}
/*
*將緩存在數組中的數據轉移到表示圖的二維數據結構中
*/
for (int i = 0; i < dim; i++) {
for (int j = 0; j < dim; j++) {
edge[i][j] = tem[k++];
}
}//for
}
/*
*對于邊割法可以任意選取初始點,不仿取第一個結點作為開始結點
*并采用冒泡法尋找最小的元素
*/
public int getLittleValue(int[][] b,int[] count,int[][] tree)throws IOException{
int recoder = 10000;
int len = count.length;
int iflag = 0;
int jflag = 0;
int flag = 1;
for (int i = 0; i < len; i++) { //將count中記錄的所有記錄行,掃描一遍
if (count[i] == 1) {
for (int j = 1; j < len; j++) {
if (count[j] == 1) { //如果count中記錄元素,說明此結點不在所選之中
continue;
} //if
else { //冒泡法找最小元素
if((recoder > b[i][j]) && (b[i][j] != 0)){
recoder = b[i][j];
iflag = i;
jflag = j;
}
} //else
} //for
} //if
} //for
if(recoder == 10000){
System.out.println("此圖不連通,沒有最小生成樹!");
flag = 0;
}
cop++;
count[jflag] = 1; //將最小元素結點記錄在count中
tree[iflag][jflag] = recoder; //將結點連接的邊放在最小生成樹矩陣中
tree[jflag][iflag] = recoder;//圖為對稱
return flag;
}
public void getLittleTree()throws IOException{
while (cop != dim) {
if(getLittleValue(edge, count, tree) == 1){
;
}
else{
break;
}
}
if(cop == dim){
result();
}
}
public void result ()throws IOException ,FileNotFoundException{
for (int i = 0; i < dim; i++) {
for (int j = 0; j < dim; j++) {
fw.write(Integer.toOctalString(tree[i][j]).getBytes("ISO-8859-1"));
fw.write(" ".getBytes());
// bos.writeChars(" ");
System.out.print(tree[i][j]+" ");
} //for
fw.write("\n".getBytes());
System.out.print("\n");
} //for
fw.close();//關閉輸出流
}
/*
* 測試結果是否正確
*/
public static void main(String args[])throws IOException{
GetLittleTree gt = new GetLittleTree();
gt.getLittleTree();
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -