- 普利姆(Prim)算法
最小生成树
* A
* / | \
* B- -F- -E
* \ / \ /
* C -- D
* A B C D E F
* 0 1 2 3 4 5
*
* A-B 6 A-E 5 A-F 1
* B-C 3 B-F 2
* C-F 8 C-D 7
* D-F 4 D-E 2
* E-F 9仔细看最小生成树的边比点少一个。
普利姆(Prim)算法是先根据一个点找出与这个点相连接的边来，在从待选边的集合中找到权值最小的边，依次往下找。
- 克鲁斯卡尔算法
克鲁斯卡尔算法是先遍历所有的边，在从边中找到最小权值的边。
就需要定义一个Edge类
package graph;
/** * Created by yxf on 2018/4/6. */
public class Edge {
private int nodeIndexA; //第一个点
private int nodeIndexB; //第二个点
private int wegiht; //权重
private boolean selected=false; //是否被选择
public Edge() {
}
public Edge(int nodeIndexA, int nodeIndexB, int wegiht) {
this.nodeIndexA = nodeIndexA;
this.nodeIndexB = nodeIndexB;
this.wegiht = wegiht;
}
public int getNodeIndexA() {
return nodeIndexA;
}
public void setNodeIndexA(int nodeIndexA) {
this.nodeIndexA = nodeIndexA;
}
public int getNodeIndexB() {
return nodeIndexB;
}
public void setNodeIndexB(int nodeIndexB) {
this.nodeIndexB = nodeIndexB;
}
public int getWegiht() {
return wegiht;
}
public void setWegiht(int wegiht) {
this.wegiht = wegiht;
}
public boolean isSelected() {
return selected;
}
public void setSelected(boolean selected) {
this.selected = selected;
}
}
- graph类
package graph;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/** * Created by yxf on 2018/4/6. * <p> * A * / \ * B D * / \ / \ * C F G- H * \ / * E * <p> * A B C D E F G H * A 1 1 * B 1 1 1 * C 1 1 1 * D 1 1 1 * E 1 * F 1 1 * G 1 1 * H 1 1 * 最小生成树 * A * / | \ * B- -F- -E * \ / \ / * C -- D * A B C D E F * 0 1 2 3 4 5 * * A-B 6 A-E 5 A-F 1 * B-C 3 B-F 2 * C-F 8 C-D 7 * D-F 4 D-E 2 * E-F 9 */
public class Graph<T> {
private final int DEFAULT_SIZE = 8;//设置默认尺寸
private int capacity; //图中最多可容纳的顶点数
private int nodeCount;//已经添加的顶点（结点）个数
private Node[] nodeArray; //用来存放顶点数组
private int[] matrix; //用来存放邻接矩阵
private final int value = 1; //默认权重
private Edge[] pEdge; //最小生成树边的集合
public static class Node<T> {
private T data; //数据
private boolean m_bIsVisted = false; //当前结点是否访问
public Node(T data) {
this.data = data;
}
public Node(T data, boolean m_bIsVisted) {
this.data = data;
this.m_bIsVisted = m_bIsVisted;
}
}
public Graph() {
capacity = DEFAULT_SIZE;
nodeArray = new Node[capacity];
matrix = new int[capacity * capacity];
pEdge = new Edge[capacity - 1];
}
public Graph(int capacity) {
this.capacity = capacity;
nodeArray = new Node[capacity];
matrix = new int[this.capacity * this.capacity];
pEdge = new Edge[capacity - 1];
}
//向图中加入顶点（结点）
public boolean addNode(T element) {
if (nodeCount < 0 && nodeCount > capacity)
throw new IndexOutOfBoundsException("数组异常出界..");
Node node = new Node(element);
nodeArray[nodeCount] = node;
nodeCount++;
return true;
}
//重置结点
public void resetNode() {
for (int i = 0; i < nodeCount; i++) {
nodeArray[i].m_bIsVisted = false;
}
}
/** * 为有向图设置邻接矩阵 * * @param row * @param col * @param val 权值 默认为1 * @return */
public boolean setValueToMatrixForDirectedGraph(int row, int col, int val) {
if (row < 0 || row > capacity || col < 0 || col > capacity) {
return false;
}
matrix[row * capacity + col] = val;
return true;
}
public boolean setValueToMatrixForDirectedGraph(int row, int col) {
if (row < 0 || row > capacity || col < 0 || col >= capacity) {
return false;
}
matrix[row * capacity + col] = value;
return true;
}
/** * 为无向图设置邻接矩阵 * * @param row * @param col * @param val 权值 默认为1 * @return */
public boolean setValueToMatrixForUndirectedGraph(int row, int col, int val) {
if (row < 0 || row > capacity || col < 0 || col >= capacity) {
return false;
}
matrix[row * capacity + col] = val;
matrix[col * capacity + row] = val;
return true;
}
public boolean setValueToMatrixForUndirectedGraph(int row, int col) {
if (row < 0 || row > capacity || col < 0 || col >= capacity) {
return false;
}
matrix[row * capacity + col] = value;
matrix[col * capacity + row] = value;
return true;
}
//从矩阵中获取权值
private int getValueFromMatrix(int row, int col) {
if (row < 0 || row > capacity || col < 0 || col >= capacity) {
return -1;
}
return matrix[row * capacity + col];
}
// 深度优先遍历
public void depthFirstTraverse(int nodeIndex) {
int value;
System.out.print(nodeArray[nodeIndex].data + " ");
nodeArray[nodeIndex].m_bIsVisted = true;
for (int i = 0; i < capacity; i++) {
value = getValueFromMatrix(nodeIndex, i);
if (value != 0) {
//访问过了就退出
if (nodeArray[i].m_bIsVisted) {
continue;
}
depthFirstTraverse(i);
}
}
}
//广度优先遍历
public void breadthFirstTraverse(int nodeIndex) {
System.out.println();
System.out.print(nodeArray[nodeIndex].data + " ");
nodeArray[nodeIndex].m_bIsVisted = true;
ArrayList list = new ArrayList();
list.add(nodeIndex);
breadthFirstTraverseImpl(list);
}
public void breadthFirstTraverseImpl(ArrayList list) {
int value;
ArrayList curList = new ArrayList();
for (int i = 0; i < list.size(); i++) { //上一层结点
for (int j = 0; j < capacity; j++) { //上一层的结点与其他点是否有连接
value = getValueFromMatrix((Integer) list.get(i), j);
if (value != 0) {
if (nodeArray[j].m_bIsVisted) { //访问过了就退出
continue;
}
System.out.print(nodeArray[j].data + " ");
nodeArray[j].m_bIsVisted = true;
curList.add(j);
}
}
}
if (curList.size() == 0)
return;
else {
breadthFirstTraverseImpl(curList);
}
}
//普里姆生成树
public void primTree(int nodeIndex) {
int value;
int edgeCount = 0; //存储边
LinkedList<Integer> nodeList = new LinkedList();//存储点集合
List<Edge> edgeList = new ArrayList<Edge>();//存储待选边集合
System.out.println("点:" + nodeArray[nodeIndex].data);
nodeList.add(nodeIndex);
nodeArray[nodeIndex].m_bIsVisted = true;
//找出的边比点少1个
while (edgeCount < capacity - 1) {
int temp = nodeList.getLast();
for (int i = 0; i < capacity; i++) {
value = getValueFromMatrix(temp, i);
if (value != 0) {
if (nodeArray[i].m_bIsVisted) {
continue;
}
Edge edge = new Edge(temp, i, value);
//存入待选边集合
edgeList.add(edge);
}
}
//从待选边集合中找出最小的边
int edgeIndex = getMinEdge(edgeList);
//将最小边设置为true
edgeList.get(edgeIndex).setSelected(true);
System.out.print("最小边：" + edgeList.get(edgeIndex).getNodeIndexA() + "----" + edgeList.get(edgeIndex).getNodeIndexB() + " ");
System.out.print("权值: " + edgeList.get(edgeIndex).getWegiht());
System.out.println();
//将选出来的边放到最小生成树边的集合中
pEdge[edgeCount] = edgeList.get(edgeIndex);
edgeCount++;
//找出下一个点
int nextNodeIndex = edgeList.get(edgeIndex).getNodeIndexB();
nodeList.add(nextNodeIndex);
//将这个点标记为true
nodeArray[nextNodeIndex].m_bIsVisted = true;
System.out.println("下一个点：" + nodeArray[nextNodeIndex].data);
}
}
//从待选边集合中找出最小的边
private int getMinEdge(List<Edge> edgeList) {
int minWeight = 0; //最小权重
int edgeIndex = 0;
int i = 0;
for (; i < edgeList.size(); i++) {
//边都没有被选择过
if (!edgeList.get(i).isSelected()) {
minWeight = edgeList.get(i).getWegiht();
edgeIndex = i;
break;
}
}
if (minWeight == 0)
return -1;
for (; i < edgeList.size(); i++) {
if (edgeList.get(i).isSelected()) {
continue;
}
if (minWeight > edgeList.get(i).getWegiht()) {
minWeight = edgeList.get(i).getWegiht();
edgeIndex = i;
}
}
return edgeIndex;
}
//克鲁斯卡尔算法
public void kruskalTree(int nodeIndex) {
int value;
int edgeCount = 0; //存储边
ArrayList<ArrayList<Integer>> nodeList = new ArrayList();//存储点集合
List<Edge> edgeList = new ArrayList<Edge>();//存储待选边集合
//取出所有边
for (int i = 0; i < capacity; i++) {
for (int j = i + 1; j < capacity; j++) {
value = getValueFromMatrix(i, j);
if (value != 0) {
Edge edge = new Edge(i, j, value);
//存入待选边集合
edgeList.add(edge);
}
}
}
//1.找到算法结束条件
while (edgeCount < capacity - 1) {
//2.从集合中找到最小边
int minEdgeIndex = getMinEdge(edgeList);
//将最小边设置为true
edgeList.get(minEdgeIndex).setSelected(true);
//3.找到最小边连接的点
int nodeIndexA = edgeList.get(minEdgeIndex).getNodeIndexA();
int nodeIndexB = edgeList.get(minEdgeIndex).getNodeIndexB();
//4.找出点所在的点集合
int nodeALabel = -1;
int nodeBLabel = -1;
boolean nodeA = false;
boolean nodeB = false;
for (int i = 0; i < nodeList.size(); i++) {
nodeA = isInList(nodeList.get(i), nodeIndexA);
if (nodeA)
nodeALabel = i;
}
for (int i = 0; i < nodeList.size(); i++) {
nodeB = isInList(nodeList.get(i), nodeIndexB);
if (nodeB)
nodeBLabel = i;
}
//5.根据点所在集合的不同做出不同处理
if (nodeALabel == -1 && nodeBLabel == -1) {
ArrayList<Integer> nodeList1 = new ArrayList<Integer>();
nodeList1.add(nodeIndexA);
nodeList1.add(nodeIndexB);
nodeList.add(nodeList1);
} else if (nodeALabel == -1 && nodeBLabel != -1) {
nodeList.get(nodeBLabel).add(nodeIndexA);
} else if (nodeALabel != -1 && nodeBLabel == -1) {
nodeList.get(nodeALabel).add(nodeIndexB);
} else if (nodeALabel != -1 && nodeBLabel != -1 && nodeALabel != nodeBLabel) {
mergeNodeList(nodeList.get(nodeALabel), nodeList.get(nodeBLabel));
for (int i = nodeBLabel; i < nodeList.size() - 1; i++) {
nodeList.remove(i);
}
} else if (nodeALabel != -1 && nodeBLabel != -1 && nodeALabel == nodeBLabel) {
continue;
}
pEdge[edgeCount] = edgeList.get(minEdgeIndex);
edgeCount++;
System.out.print("最小边：" + edgeList.get(minEdgeIndex).getNodeIndexA() + "----" + edgeList.get(minEdgeIndex).getNodeIndexB() + " ");
System.out.print("权值: " + edgeList.get(minEdgeIndex).getWegiht());
System.out.println();
}
}
private void mergeNodeList(ArrayList<Integer> nodeListA, ArrayList<Integer> nodeListB) {
for (int i=0;i<nodeListB.size();i++){
nodeListA.add(nodeListB.get(i));
}
}
//判断target是否在列表中
private boolean isInList(ArrayList<Integer> nodeList, int target) {
for (int i=0;i<nodeList.size();i++){
if(nodeList.get(i)==target){
return true;
}
}
return false;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < capacity; i++) {
for (int j = 0; j < capacity; j++) {
sb.append(matrix[i * capacity + j] + " ");
}
sb.append("\r\n");
}
int len = sb.length();
return sb.delete(len - 2, len).toString();
}
}
- 测试类
@Test
public void minSpanTreePrimTest(){
Graph graph = new Graph(6);
graph.addNode("A");
graph.addNode("B");
graph.addNode("C");
graph.addNode("D");
graph.addNode("E");
graph.addNode("F");
graph.setValueToMatrixForUndirectedGraph(0,1,6);
graph.setValueToMatrixForUndirectedGraph(0,4,5);
graph.setValueToMatrixForUndirectedGraph(0,5,1);
graph.setValueToMatrixForUndirectedGraph(1,2,3);
graph.setValueToMatrixForUndirectedGraph(1,5,2);
graph.setValueToMatrixForUndirectedGraph(2,5,8);
graph.setValueToMatrixForUndirectedGraph(2,3,7);
graph.setValueToMatrixForUndirectedGraph(3,5,4);
graph.setValueToMatrixForUndirectedGraph(3,4,2);
graph.setValueToMatrixForUndirectedGraph(4,5,9);
graph.primTree(0);
//graph.kruskalTree(0);
}输出
普里姆:
点:A
最小边：0----5 权值: 1
下一个点：F
最小边：5----1 权值: 2
下一个点：B
最小边：1----2 权值: 3
下一个点：C
最小边：5----3 权值: 4
下一个点：D
最小边：3----4 权值: 2
下一个点：E克鲁斯卡尔算法:
最小边：0----5 权值: 1
最小边：1----5 权值: 2
最小边：3----4 权值: 2
最小边：1----2 权值: 3
最小边：3----5 权值: 4
Process finished with exit code 0