图基本算法：深度广度遍历最小生成树

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;} ;