import org.eclipse.jetty.util.ArrayQueue;
import java.util.HashMap;
import java.util.Queue;
//图的基本算法
public class Graph {
//图邻接矩阵
//节点之间不连通用 65535表示
private static int[][] arcs;
//节点数
private static int num;
//是否访问过
private static boolean[] hasVisit;
//记录访问过的前一个节点
static int pre;
public static void main(String[] args) {
int[][] arcs = {
{0, 65535, 2, 65535, 6},
{9, 0, 3, 65535, 65535},
{65535, 65535, 0, 5, 65535},
{65535, 65535, 65535, 0, 1},
{65535, 65535, 65535, 65535, 0}
};
int[][] arcswithnodirction = {
{65535, 6, 1, 5, 65535,65535},
{6, 65535, 5, 65535, 3,65535},
{1, 5, 65535, 5, 6,4},
{5, 65535, 5, 65535, 65535,2},
{65535, 3, 6, 65535, 65535,6},
{65535, 65535, 4, 2, 6,65535}
};
// Graph graph = new Graph(arcs);
// graph.traverse_DFS(0);
// graph.traverse_BFS(0);
Graph graph = new Graph(arcswithnodirction);
// graph.miniSpanTree();
graph.miniSpanTree_kruskal();
}
//初始化图
public Graph(int[][] arcs) {
this.arcs = arcs;
num = arcs.length;
}
//深度优先遍历,
public static void traverse_DFS(int begin) {
hasVisit = new boolean[num];
for (int i = 0; i < num; i++) {
DFS(i);
}
}
public static void DFS(int begin) {
if (hasVisit[begin])
return;
System.out.print(begin + ",");
hasVisit[begin] = true;
for (int i = 0; i < num; i++) {
if (!hasVisit[i] && arcs[begin][i] != 65535) {
DFS(i);
}
}
}
// 广度优先遍历，给出图邻接矩阵和开始遍历的节点
public static void traverse_BFS(int begin) {
hasVisit = new boolean[num];
Queue<Integer> bfs=new ArrayQueue<>();
int i=0;
while (bfs.size()>0 || i<num) {
if (bfs.isEmpty())
{
if(!hasVisit[i])
{
bfs.add(i);
}
i++;
}
else {
int t = bfs.poll();
System.out.print(t + ",");
hasVisit[t] = true;
for (int j = 0; j < num; j++) {
if (!hasVisit[j] && arcs[t][j] != 65535) {
bfs.add(j);
}
}
}
}
}
//最小生成树,边是无向边:每次取出剩余边中两个端点不同时在以获取的连通中的边
public static void miniSpanTree()
{
HashMap<Integer,Integer> connected=new HashMap<Integer,Integer>();
//如果节点数小于num就接着查找。
// 找不到不在已经连通的图的点中且不和他们构成环的边就退出（此时图不连通）
StringBuilder sb=new StringBuilder();
while (connected.size()<num)
{
//开始的时候讲第一个节点加入
if (connected.size()==0)
{
int minfirst=0;
for(int i=0;i<num;i++)
{
minfirst=arcs[0][minfirst]>arcs[0][i]?i:minfirst;
}
if(arcs[0][minfirst]==65535)
{
System.out.println("图不是连通的");
return;
}
connected.put(0,0);
connected.put(minfirst,minfirst);
sb.append(0+"---->"+minfirst+":"+arcs[0][minfirst]+" ");
}
else
{
//查找和connected连接的边的最小值，且这些边不能和connected中的边构成环
int minti=-1,mintj=-1;
for(Integer i:connected.keySet())
{
int mint=-1;
for(int j=0;j<num;j++)
{
if(connected.get(j)==null )
{
if(minti==-1 && mintj==-1)
{
minti=i;
mintj=j;
}
else if(arcs[minti][mintj]>arcs[i][j])
{
minti=i;
mintj=j;
}
}
}
}
if(minti!=-1 && mintj!=-1 && arcs[minti][mintj]!=65535)
{
connected.put(minti,minti);
connected.put(mintj,mintj);
sb.append(minti+"---->"+mintj+":"+arcs[minti][mintj]+" ");
}
else
{
System.out.println("图不是连通的");
return;
}
}
}
if(connected.size()==num)
{
System.out.println(sb);
}
}
public static void miniSpanTree_kruskal()
{
int edgenum=0;
//获取边数
for(int i=0;i<num;i++)
{
for(int j=i+1;j<num;j++)
if(arcs[i][j]!=65535)
edgenum+=1;
}
node[] edge=new node[edgenum];
int[] vset=new int[edgenum];
//初始化边
int k=0;
for(int i=0;i<num;i++)
{
for(int j=i+1;j<num;j++)
if(arcs[i][j]!=65535) {
edge[k]=new node();
edge[k].start=i;
edge[k].end=j;
edge[k].value=arcs[i][j];
k++;
}
}
sort(edge);
//初始化边
for(int i=0;i<edgenum;i++)
{
vset[i]=i;
}
int tempnum=0;
for(int i=0;i<edgenum;i++)
{
if(tempnum==num-1)
{
System.out.println("图已经连通");
return;
}
if(vset[edge[i].start]!=vset[edge[i].end])
{
System.out.println(edge[i].start+"-->"+edge[i].end+":"+edge[i].value);
vset[edge[i].end]=vset[edge[i].start];
tempnum++;
}
}
if(tempnum!=num-1)
System.out.println("图不连通");
}
static void sort(node[] nodes)
{
for(int i=0;i<nodes.length;i++)
{
int mini=i;
for(int j=i;j<nodes.length;j++)
{
mini=nodes[mini].value>nodes[j].value?j:mini;
}
//交换节点
node nodetemp=new node();
nodetemp.start=nodes[i].start;
nodetemp.end=nodes[i].end;
nodetemp.value=nodes[i].value;
nodes[i].start=nodes[mini].start;
nodes[i].end=nodes[mini].end;
nodes[i].value=nodes[mini].value;
nodes[mini].start=nodetemp.start;
nodes[mini].end=nodetemp.end;
nodes[mini].value=nodetemp.value;
}
}
}
class node{public int start;public int end;public int value;} ;
