根据题意，求的是最大生成树。利用Kruskal算法,对边进行从大到小的顺序进行排序，然后再依次取出边加入结果集中。假设图有n个顶点，那么，当结果集中有n-1条边时，剩下的边的集合即为反馈边集。
package org.xiu68.ch05.ex9; import java.util.ArrayList;
import java.util.Comparator; public class Ex5_21 { public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] edges=new int[][]{
{0,2,1,6},
{2,0,5,3},
{1,5,0,4},
{6,3,4,0}
};
ArrayList<String> vexs=new ArrayList<>();
for(int i=0;i<4;i++)
vexs.add("v"+i);
MGraph<String> m1=new MGraph<String>(4,4,edges,vexs);
m1.kruskal();
//运行结果
/*
(0,3):6
(1,2):5
(2,3):4
(1,3):3
(0,1):2
(0,2):1
*************************************
反馈边集为:
(1,3):3
(0,1):2
(0,2):1
*/
}
} //边类型
class Edge{
public int head; //头顶点序号
public int tail; //尾顶点序号
public int cost; //权值 public Edge(int head, int tail, int cost) {
super();
this.head = head;
this.tail = tail;
this.cost = cost;
}
} //邻接矩阵表示图
class MGraph<T> implements Comparator<Edge>{
public int vexNum; //顶点数量
public int edgeNum; //边数量
public ArrayList<T> vexs; //顶点表
public int[][] edges; //邻接矩阵 public MGraph(int vexNum, int edgeNum, int[][] edges, ArrayList<T> vexs) {
this.vexNum = vexNum;
this.edgeNum = edgeNum;
this.edges = edges;
this.vexs=vexs;
} //返回反馈边集
public void kruskal(){
ArrayList<Edge> eds=new ArrayList<>();
//初始化边集数组
for(int i=0;i<edges.length;i++){
for(int j=i+1;j<edges[i].length;j++){
if(edges[i][j]==0)
continue;
Edge e=new Edge(i,j,edges[i][j]);
eds.add(e);
}
} //对边集数组进行排序
eds.sort(this); for(int i=0;i<eds.size();i++)
System.out.println("("+eds.get(i).head+","+eds.get(i).tail+"):"+eds.get(i).cost); ArrayList<Edge> resultSet=new ArrayList<>(); //存放反馈边集
int[] components=new int[vexNum]; //并查集
for(int i=0;i<vexNum;i++)
components[i]=i; int k=0,j=0;
while(k<vexNum-1){ int h1=eds.get(j).head;
int t1=eds.get(j).tail;
int com1=components[h1];
int com2=components[t1]; //在不同的并查集
if(com1!=com2){
k++;
for(int i=0;i<vexNum;i++){
if(components[i]==com2)
components[i]=com1;
}
}else{
//反馈边集
resultSet.add(eds.get(j));
}
j++;
} //找到n-1条边后，剩下的边也属于反馈边集
for(int i=j;i<eds.size();i++)
resultSet.add(eds.get(i)); System.out.println("*************************************");
System.out.println("反馈边集为:");
for(int i=0;i<resultSet.size();i++)
System.out.println("("+resultSet.get(i).head+","+resultSet.get(i).tail+"):"+resultSet.get(i).cost);
} @Override
public int compare(Edge e1, Edge e2) {
// TODO Auto-generated method stub
//按从大到小排序
if(e1.cost<e2.cost)
return 1;
else
return -1;
}
}