首页 > 代码库 > 图
图
下面用java实现了图,这个图使用邻接矩阵来实现。然后图的遍历使用了:深度遍历,广度遍历。最小生成树使用普利姆算法以及克鲁斯卡尔算法
package net.itaem.graph; public class Edge implements Comparable<Edge>{ private int start; //起点 private int end; //终点 private int weight = Integer.MAX_VALUE / 2; //权值,默认为无穷大 public Edge(int start, int end, int weight){ this.start = start; this.end = end; this.weight = weight; } public int getStart() { return start; } public void setStart(int start) { this.start = start; } public int getEnd() { return end; } public void setEnd(int end) { this.end = end; } public int getWeight() { return weight; } public void setWeight(int weight) { this.weight = weight; } @Override public String toString() { return "Edge [start=" + start + ", end=" + end + ", weight=" + weight + "]"; } //实现了Comparable<Edge>接口,用于排序的时候使用 @Override public int compareTo(Edge that) { if(that == this) return 0; return this.getWeight() - that.getWeight(); } }
package net.itaem.graph; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.LinkedList; import java.util.List; /** * 使用邻接矩阵来实现图 * */ public class Graph { private List<String> vexList; private List<Edge> edgeList; private int[][] edgeArray; private boolean[] visited; //创建一个图 public Graph(int size){ this.vexList = new ArrayList<String>(); this.edgeList = new ArrayList<Edge>(); this.edgeArray = new int[size][size]; for(int i=0; i<size; i++){ for(int j=0; j<size; j++){ edgeArray[i][j] = Integer.MAX_VALUE / 2; } } createGraph(); } public boolean isEdgeExists(int start, int end){ if(edgeArray[start][end] != Integer.MAX_VALUE/2){ return true; }else{ return false; } } private void createGraph(){ vexList.add("V0"); vexList.add("V1"); vexList.add("V2"); vexList.add("V3"); vexList.add("V4"); vexList.add("V5"); vexList.add("V6"); vexList.add("V7"); vexList.add("V8"); //初始化4条边,因为是无向边,所以都是成对出现 Edge edge1 = new Edge(0, 1, 10); Edge edge2 = new Edge(0, 5, 11); Edge edge3 = new Edge(1, 0, 10); Edge edge4 = new Edge(5, 0, 11); Edge edge5 = new Edge(1, 2, 18); Edge edge6 = new Edge(1, 6, 16); Edge edge7 = new Edge(1, 8, 12); Edge edge8 = new Edge(2, 1, 18); Edge edge9 = new Edge(6, 1, 16); Edge edge10 = new Edge(8, 1, 12); Edge edge11 = new Edge(2, 3, 22); Edge edge12 = new Edge(2, 8, 8); Edge edge13 = new Edge(3, 2, 22); Edge edge14 = new Edge(8, 2, 8); Edge edge15 = new Edge(3, 4, 20); Edge edge16 = new Edge(3, 7, 16); Edge edge17 = new Edge(3, 8, 21); Edge edge18 = new Edge(4, 3, 20); Edge edge19 = new Edge(7, 3, 16); Edge edge20 = new Edge(8, 3, 21); Edge edge21 = new Edge(4, 5, 26); Edge edge22 = new Edge(4, 7, 7); Edge edge23 = new Edge(5, 4, 26); Edge edge24 = new Edge(7, 4, 7); Edge edge25 = new Edge(5, 6, 17); Edge edge26 = new Edge(6, 5, 17); Edge edge27 = new Edge(6, 7, 19); Edge edge28 = new Edge(7, 6, 19); Edge edge29 = new Edge(1, 8, 12); Edge edge30 = new Edge(8, 1, 12); add(edge29); add(edge30); add(edge1); add(edge2); add(edge3); add(edge4); add(edge5); add(edge6); add(edge7); add(edge8); add(edge9); add(edge10); add(edge11); add(edge12); add(edge13); add(edge14); add(edge15); add(edge16); add(edge17); add(edge18); add(edge19); add(edge20); add(edge21); add(edge22); add(edge23); add(edge24); add(edge25); add(edge26); add(edge27); add(edge28); } public void add(Edge edge){ for(int i=0; i<vexList.size(); i++){ for(int j=0; j<vexList.size(); j++){ //设置这个权值到数组中 if(i != j && i == edge.getStart() && j == edge.getEnd() && edgeArray[i][j] == Integer.MAX_VALUE/2){ edgeArray[i][j] = edge.getWeight(); }else if(i == j){ edgeArray[i][j] = 0; } } } edgeList.add(edge); } public String toString(){ StringBuilder sb = new StringBuilder(); for(int i=0; i<vexList.size(); i++){ for(int j=0; j<vexList.size(); j++){ if(edgeArray[i][j] != Integer.MAX_VALUE/2) sb.append(edgeArray[i][j]+ " "); else sb.append("00" + " "); } sb.append("\n"); } return sb.toString(); } public static void main(String[] args) { Graph graph = new Graph(9); System.out.println(graph); System.out.println("DFS======================================"); graph.DFS(); System.out.println("======================================DFS"); System.out.println(); System.out.println("BFS======================================"); graph.BFS(); System.out.println("end======================================BFS"); System.out.println("=======minSpanTreePrim=================="); graph.minSpanTreePrim(); System.out.println("=======minSpanTreePrim=================="); System.out.println("=======miniSpanTreeKruskal=================="); graph.miniSpanTreeKruskal(); System.out.println("=======miniSpanTreeKruskal=================="); } //深度优先遍历这个图 public void DFS(){ visited = new boolean[vexList.size()]; //标识每个节点是否被访问,这里全部重置 for(int i=0; i<vexList.size(); i++){ if(!visited[i]){ DFS0(i); } } } public void DFS0(int index){ System.out.println("vex "+ index +" value is " + vexList.get(index)); //输出这个节点,也可以更换成其它操作 visited[index] = true; //设置该节点已经被访问过了 for(int j=0; j<vexList.size(); j++){ if(isEdgeExists(index, j) && !visited[j]){ DFS0(j); } } } //广度优先,遍历这个图 public void BFS(){ visited = new boolean[vexList.size()]; //标识每个节点是否被访问,这里全部重置 LinkedList<Integer> queue = new LinkedList<Integer>(); for(int i=0; i<vexList.size(); i++){ //如果这个节点没有被访问过,就访问 if(!visited[i]){ visited[i] = true; System.out.println("vex " + i + " is " + vexList.get(i)); //输出这个节点,也可以更换成其它操作 queue.addLast(i); //将这个节点i加入队列 while(!queue.isEmpty()){ int index = queue.removeFirst(); //出队列,并且将这个下标记住 for(int j=0; j<vexList.size(); j++){ if(isEdgeExists(index, j) && !visited[j]){ visited[j] = true; System.out.println("vex " + j + " is " + vexList.get(j)); //输出这个节点,也可以更换成其它操作 queue.addLast(j); } } } }else{ //System.out.println(i + " vex is visited"); } } } /** * 最小生成树,普利姆算法 * 出发点:从其中一个顶点出发 * 前提条件:无 * * */ public void minSpanTreePrim(){ int min = 0, i = 0, j = 0, k = 0; int[] adjvex = new int[vexList.size()]; //保存顶点相关下标 int[] lowcost = new int[vexList.size()]; //保存定点之间的权值 lowcost[0] = 0; //初始化第一个权值为0,也就是V0加入生成树 adjvex[0] = 0; //初始化顶一个定点下标为0 for(i=1; i<vexList.size(); i++){ //循环其它的定点 lowcost[i] = edgeArray[0][i]; //取出V0连的边的全部权值 adjvex[i] = 0; //初始化都为V0下标 } for(i=1; i<vexList.size(); i++){ min = Integer.MAX_VALUE / 2; //初始化权值最小为无穷大 j = 1; k = 0; while(j < vexList.size()){ if(lowcost[j] != 0 && lowcost[j] < min){ //如果权值不为0并且小于MIN,也就是该节点相连的边中最小权值 min = lowcost[j]; k = j; //让最小的值的下标存入k } j++; } System.out.println("(" + adjvex[k] + "," + k + ")"); //输出边 lowcost[k] = 0; //将当前顶点的权值设置为0,表示此顶点已经完成任务 for(j = 1; j<vexList.size(); j++){ if(lowcost[j] != 0 && edgeArray[k][j] < lowcost[j]){ lowcost[j] = edgeArray[k][j]; adjvex[j] = k; } } } } /** * 库鲁斯卡尔算法 * 出发点:从边出发 * * 前提:这些变都按照权值大小排序好 * * 从图的每一条边出发,然后查看这条边是否形成环,如果没有,加入到最小生成树 * * */ public void miniSpanTreeKruskal(){ int n = 0, m = 0, i = 0; int[] parent = new int[vexList.size()]; //定义一个数组用来判断是否形成环路,初始化的值都为0 //获得排序好的所有边集合,也就是前提条件 Collections.sort(edgeList); Edge[] edges = new Edge[edgeList.size()/2]; int index = 0; for(int j=0; j < edgeList.size(); j++){ if(j % 2 == 0){ edges[index++] = edgeList.get(j); } } //循环每一条边 for(i=0; i<edges.length; i++){ n = find(parent, edges[i].getStart()); //找到这条边的起点 m = find(parent, edges[i].getEnd()); //找到这条边的终点 //如果没有形成环,加入到最小生成树 if(n != m){ //如果不相等,说明没有构成环 parent[n] = m; //将此边的结尾顶点放入到下边起点的parent中,表示此顶点已经在生成树中 System.out.println("(" + edges[i].getStart() + "," + edges[i].getEnd() + ")" + " weight " + edges[i].getWeight()); } } } private int find(int[] parent, int f){ //查找连线节点的尾部下标 while(parent[f] > 0) f = parent[f]; return f; } }
下面是是输出结果
0 10 00 00 00 11 00 00 00 10 0 18 00 00 00 16 00 12 00 18 0 22 00 00 00 00 8 00 00 22 0 20 00 00 16 21 00 00 00 20 0 26 00 7 00 11 00 00 00 26 0 17 00 00 00 16 00 00 00 17 0 19 00 00 00 00 16 7 00 19 0 00 00 12 8 21 00 00 00 00 0 DFS====================================== vex 0 value is V0 vex 1 value is V1 vex 2 value is V2 vex 3 value is V3 vex 4 value is V4 vex 5 value is V5 vex 6 value is V6 vex 7 value is V7 vex 8 value is V8 ======================================DFS BFS====================================== vex 0 is V0 vex 1 is V1 vex 5 is V5 vex 2 is V2 vex 6 is V6 vex 8 is V8 vex 4 is V4 vex 3 is V3 vex 7 is V7 end======================================BFS =======minSpanTreePrim================== (0,1) (0,5) (1,8) (8,2) (1,6) (6,7) (7,4) (7,3) =======minSpanTreePrim================== =======miniSpanTreeKruskal================== (4,7) weight 7 (2,8) weight 8 (0,1) weight 10 (0,5) weight 11 (1,8) weight 12 (1,6) weight 16 (3,7) weight 16 (6,7) weight 19 =======miniSpanTreeKruskal==================
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。