文章目录
一、prim算法
1.基本介绍
普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图
普利姆的算法如下:
1.设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点集合，E,D是边的集合
2.若从顶点u开始构造最小生成树，则从集合V中取出顶点u放入集合u中，标记顶点v的visited[u]=1
3.若集合u中顶点ui与集合v-U中的顶点vj之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点vj加入集合U中，将边(ui,vj）加入集合D中，标记visited[vj]=1
4.重复步骤②，直到u与v相等，即所有顶点都被标记为访问过，此时D中有n-1条边
2.应用场景——修路问题
3.代码实现
package com.tx.prim;
import java.util.Arrays;
public class Prim {
public static void main(String[] args) {
char[] data = new char[]{'A','B','C','D','E','F','G'};
int verxs = data.length;
//邻接矩阵的关系使用二维数组表示,10000表示两个点不联通
int [][]weight=new int[][]{
{10000,5,7,10000,10000,10000,2},
{5,10000,10000,9,10000,10000,3},
{7,10000,10000,10000,8,10000,10000},
{10000,9,10000,10000,10000,4,10000},
{10000,10000,8,10000,10000,5,4},
{10000,10000,10000,4,5,10000,6},
{2,3,10000,10000,4,6,10000},};
MGraph graph = new MGraph(verxs);
MinTree minTree = new MinTree();
minTree.createGraph(graph, verxs, data, weight);
minTree.showGraph(graph);
minTree.primMethod(graph, 1);
}
}
//创建最小生成树
class MinTree {
public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) {
int i, j;
for(i = 0; i < verxs; i++) {//顶点
graph.data[i] = data[i];
for(j = 0; j < verxs; j++) {
graph.weight[i][j] = weight[i][j];
}
}
}
public void showGraph(MGraph graph) {
for(int[] link: graph.weight) {
System.out.println(Arrays.toString(link));
}
}
public void primMethod(MGraph graph, int v) {
int visited[] = new int[graph.verxs];
visited[v] = 1;
//h1 和 h2 记录下标
int h1 = -1;
int h2 = -1;
int minWeight = 10000;
for(int k = 1; k < graph.verxs; k++) {
for(int i = 0; i < graph.verxs; i++) {结点
for(int j = 0; j< graph.verxs;j++) {
if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
minWeight = graph.weight[i][j];
h1 = i;
h2 = j;
}
}
}
//找到最小的一条边
System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 值:" + minWeight);
//将当前这个结点标记为已经访问
visited[h2] = 1;
//minWeight 设置为最大值 10000
minWeight = 10000;
}
}
}
class MGraph {
int verxs; //表示图的节点个数
char[] data;//存放结点数据
int[][] weight; //存放边，就是我们的邻接矩阵
public MGraph(int verxs) {
this.verxs = verxs;
data = new char[verxs];
weight = new int[verxs][verxs];
}
}
二、Kruskal算法
1.基本介绍
克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。
基本思想:按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。
具体做法:首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。
2.应用场景
3.代码实现
代码如下（示例）：
ipackage com.tx.kruskal;
import java.util.Arrays;
public class Kruskal {
private int edgeNum; //边的个数
private char[] vertexs; //顶点数组
private int[][] matrix; //邻接矩阵
//表示两个顶点不能连通
private static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) {
char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//邻接矩阵
int matrix[][] = {
{ 0, 12, INF, INF, INF, 16, 14},
{ 12, 0, 10, INF, INF, 7, INF},
{ INF, 10, 0, 3, 5, 6, INF},
{ INF, INF, 3, 0, 4, INF, INF},
{ INF, INF, 5, 4, 0, 2, 8},
{ 16, 7, 6, INF, 2, 0, 9},
{ 14, INF, INF, INF, 8, 9, 0}};
Kruskal kruskalCase = new Kruskal(vertexs, matrix);
kruskalCase.print();
kruskalCase.kruskalmethod();
}
public Kruskal(char[] vertexs, int[][] matrix) {
int vlen = vertexs.length;
this.vertexs = new char[vlen];
for(int i = 0; i < vertexs.length; i++) {
this.vertexs[i] = vertexs[i];
}
this.matrix = new int[vlen][vlen];
for(int i = 0; i < vlen; i++) {
for(int j= 0; j < vlen; j++) {
this.matrix[i][j] = matrix[i][j];
}
}
for(int i =0; i < vlen; i++) {
for(int j = i+1; j < vlen; j++) {
if(this.matrix[i][j] != INF) {
edgeNum++;
}
}
}
}
public void kruskalmethod() {
int index = 0;
int[] ends = new int[edgeNum];
EData[] rets = new EData[edgeNum];
EData[] edges = getEdges();
System.out.println("图的边的集合=" + Arrays.toString(edges) + " 共"+ edges.length); //12
sortEdges(edges);
//遍历edges 数组
for(int i=0; i < edgeNum; i++) {
//获取到第i条边的第一个顶点
int p1 = getPosition(edges[i].start);
//获取到第i条边的第2个顶点
int p2 = getPosition(edges[i].end);
int m = getEnd(ends, p1);
//获取p2到终点
int n = getEnd(ends, p2);
//是否构成回路
if(m != n) {
ends[m] = n;
rets[index++] = edges[i];
}
}
System.out.println("最小生成树为");
for(int i = 0; i < index; i++) {
System.out.println(rets[i]);
}
}
public void print() {
System.out.println("邻接矩阵为: \n");
for(int i = 0; i < vertexs.length; i++) {
for(int j=0; j < vertexs.length; j++) {
System.out.printf("%12d", matrix[i][j]);
}
System.out.println();
}
}
private void sortEdges(EData[] edges) {
for(int i = 0; i < edges.length - 1; i++) {
for(int j = 0; j < edges.length - 1 - i; j++) {
if(edges[j].weight > edges[j+1].weight) {//交换
EData tmp = edges[j];
edges[j] = edges[j+1];
edges[j+1] = tmp;
}
}
}
}
private int getPosition(char ch) {
for(int i = 0; i < vertexs.length; i++) {
if(vertexs[i] == ch) {
return i;
}
}
return -1;
}
private EData[] getEdges() {
int index = 0;
EData[] edges = new EData[edgeNum];
for(int i = 0; i < vertexs.length; i++) {
for(int j=i+1; j <vertexs.length; j++) {
if(matrix[i][j] != INF) {
edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
}
}
}
return edges;
}
private int getEnd(int[] ends, int i) { [0,0,0,0,5,0,0,0,0,0,0,0]
while(ends[i] != 0) {
i = ends[i];
}
return i;
}
}
//创建一个类EData来表示一条边
class EData {
char start; //边的一个点
char end; //边的另外一个点
int weight; //边的权值
public EData(char start, char end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
@Override
public String toString() {
return "EData [<" + start + ", " + end + ">= " + weight + "]";
}
}