概念
- 图的生成树是图的子图，并且不形成环路
- 最小生成树是带权图中所有生成树里边权值总和最小的一个解，可能不唯一
算法思路
- 以图的一个节点开始
- 找出所有已被访问的节点的邻接节点中未访问且边权值最小的一个节点以及对应边，加入树中
- 只要树的边数小于节点数 - 1就执行第二步
算法实现
图的实现
- 此实现方法没有节点类
- 采用邻接矩阵和顶点索引
- 边类有两个成员变量，用于记录两个端点的索引
int A，int B - 使用枚举来定义节点的状态
enum Status { UNDISCOVERD, VISITED } - 枚举数组
Status[] statuses记录每个节点的状态 - 邻接矩阵
int[][] matrix(邻接矩阵无需设置为沿对角线对称)-
matrix[i][j]表示从索引i的节点指向索引j的节点的权值 - 权值为0表示两点不连接或者自身与自身不连接
-
enum Status { // 节点对象的状态
// 未被发现, 已被遍历
UNDISCOVERD, VISITED
}
public class Graph<T> {
private int N; // N个节点
public int[][] matrix; // 邻接矩阵
private Status[] statuses; // 保存每个节点的状态
private T[] datas; // 保存每个节点的数据
class Edge {
int A; // 顶点索引
int B; // 顶点索引
public Edge(int a, int b) {
A = a;
B = b;
}
@Override
public String toString() {
return "<" +
datas[A] +
"-" + matrix[A][B] + "-" + datas[B] +
'>';
}
}
}
核心步骤
- 由于最小生成树的边数 = 图节点数 - 1，所以只要最终结果的边集合长度小于节点数 - 1
result.size() < N - 1，就循环执行找出权值最小的节点以及边 - 每次循环都需要记录最小权值
minWeight，最小权值的边minEdge- 内层循环遍历所有已访问节点
for (int index : visited)- 最内层循环，先确定当前要找后继节点的节点索引，也就是for循环的每一个
index，然后遍历邻接矩阵中index行i列，也就是图中索引index的节点指向索引i节点的边，记录权值weight = matrix[index][i]- 如果权值大于0
weight > 0并且后继节点未被访问statuses[i] == Status.UNDISCOVERD并且权重小于当前记录的最小权值weight < minWeight，则记录这条边minEdge = new Edge(index, i)，更新最小权值minWeight = weight - 由于Prim算法是基于节点的，所以不用像基于边的Kruskal算法
一样判断是否生成环，只要选择未被访问的节点，就不会生成环
- 如果权值大于0
- 最内层循环，先确定当前要找后继节点的节点索引，也就是for循环的每一个
- 每次内层循环就找到了一条最小权值边，以及另一个端点，于是把最小边加入集合
result.add(minEdge)，该端点加入已访问的节点集合visited.add(minEdge.B)，设置该点状态为已访问statuses[minEdge.B] = Status.VISITED
- 内层循环遍历所有已访问节点
while (result.size() < N - 1) {
// 记录最小权值
int minWeight = Integer.MAX_VALUE;
// 记录最小权值对应的边
Edge minEdge = null;
// 遍历已经被访问过的所有节点, 查找他们的邻接节点
for (int index : visited) {
// 循环遍历邻接矩阵中index行j列, 查看权重
for (int i = 0; i < N; i++) {
// 如果当前节点指向索引j节点有路径, 并且索引j节点未被访问
int weight = matrix[index][i];
if (weight > 0 && statuses[i] == Status.UNDISCOVERD && weight < minWeight) {
// 如果这个权重比最小权重还小
// 记录这条边
minEdge = new Edge(index, i);
// 更新最小权值
minWeight = weight;
} }
}
// 最小边加入集合
result.add(minEdge);
// 最小边另一个端点得加入visited
visited.add(minEdge.B);
// 设置边的端点为已访问
statuses[minEdge.B] = Status.VISITED;
}
完整步骤
- 声明变量
-
List<Edge> result记录最小生成树的边 -
List<Integer> visited记录当前已被访问的节点索引
-
- 将第一个节点状态设置为已被访问
statuses[0] = Status.VISITED - 将第一个节点添加到
visited - 只要
result元素数量小于节点数 - 1result.size() < N - 1则循环执行- 声明变量最小权值
int minWeight，最小权值的边Edge minEdge - 遍历已经被访问过的所有节点, 查找他们的邻接节点
- 记录找到的最小权值的节点，对应边，设置节点状态
- 声明变量最小权值
- 循环结束后声明一个树的邻接矩阵，遍历每条边
for (Edge edge : result)并把树的邻接矩阵设置好treeMatrix[edge.A][edge.B] = matrix[edge.A][edge.B] - 输出查看最小生成树的边集合
result，树邻接矩阵treeMatrix
/**
* 普利姆算法-最小生成树
*
* @return void
*/
public void PrimTree() {
// 记录最小生成树的边的集合
List<Edge> result = new ArrayList<>();
// 记录当前已被访问的节点索引(只需要N - 1个)
List<Integer> visited = new ArrayList<>();
// 从一个节点开始
// 找出与该节点邻接的所有节点中路径权值最小的
// 将这两个节点的边记录下来, 并且节点设置为已访问
statuses[0] = Status.VISITED;
visited.add(0);
// 最终结果有N - 1条边, 不满足则循环执行
while (result.size() < N - 1) {
// 记录最小权值
int minWeight = Integer.MAX_VALUE;
// 记录最小权值对应的边
Edge minEdge = null;
// 遍历已经被访问过的所有节点, 查找他们的邻接节点
for (int index : visited) {
// 循环遍历邻接矩阵中index行j列, 查看权重
for (int i = 0; i < N; i++) {
// 如果当前节点指向索引j节点有路径, 并且索引j节点未被访问
int weight = matrix[index][i];
if (weight > 0 && statuses[i] == Status.UNDISCOVERD) {
// 如果这个权重比最小权重还小
if (weight < minWeight) {
// 记录这条边
minEdge = new Edge(index, i);
// 更新最小权值
minWeight = weight;
}
}
}
}
// 最小边加入集合
result.add(minEdge);
// 最小边另一个端点得加入visited
visited.add(minEdge.B);
// 设置边的端点为已访问
statuses[minEdge.B] = Status.VISITED;
}
// 循环结束后, 打印最小生成树邻接矩阵
int[][] treeMatrix = new int[N][N];
for (Edge edge : result) {
treeMatrix[edge.A][edge.B] = matrix[edge.A][edge.B];
}
System.out.println(result);
System.out.println("最小生成树的邻接矩阵: ");
for (int[] nums : treeMatrix) {
System.out.println(Arrays.toString(nums));
}
}
测试
- 创建7个节点的图
new Graph<>(7) - 设置图节点保存的数据为"ABCDEFG"七个字母
- 初始化邻接矩阵
graph.setMatrix(matrix) - 将图变成无向图也就是邻接矩阵沿左对角线对称
graph.makeUndirected() - 执行Prim算法
graph.PrimTree()
public static void main(String[] args) {
Graph<String> graph = new Graph<>(7);
graph.setDatas(new String[]{"A", "B", "C", "D", "E", "F", "G"});
int[][] matrix = {
{0, 7, 3, 2, 2, 0, 0},
{0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 4, 3, 0},
{0, 0, 0, 0, 1, 10, 2},
{0, 0, 0, 0, 0, 4, 2},
{0, 0, 0, 0, 0, 0, 7},
{0, 0, 0, 0, 0, 0, 0}};
graph.setMatrix(matrix);
graph.makeUndirected();
graph.PrimTree();
}
给定的图
输出结果
[<A-2-D>, <D-1-E>, <D-2-G>, <A-3-C>, <C-1-B>, <C-3-F>]
最小生成树的邻接矩阵:
[0, 0, 3, 2, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 3, 0]
[0, 0, 0, 0, 1, 0, 2]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
最小生成树
完整代码
enum Status { // 节点对象的状态
// 未被发现, 已被遍历
UNDISCOVERD, VISITED
}
public class Graph<T> {
private int N; // 节点个数
public int[][] matrix; // 邻接矩阵
private T[] datas; // 保存每个节点的数据
public List<Edge> edges = new ArrayList<>(); // 边集合
class Edge {
int A; // 顶点索引
int B; // 顶点索引
public Edge(int a, int b) {
A = a;
B = b;
}
// 重写toString()方法方便查看结果
@Override
public String toString() {
return "<" +
datas[A] +
"-" + matrix[A][B] + "-" + datas[B] +
'>';
}
}
public Graph(int N) {
this.N = N;
matrix = new int[N][N];
statuses = new Status[N];
datas = (T[]) new Object[N]; // 泛型数组实例化
}
/**
* 邻接矩阵保存的信息是从一个节点指向另一个节点的信息
*
* @param from 从这个节点
* @param to 指向这个节点
* @param weight 路径权重
* @return void
*/
public void setMatrix(int from, int to, int weight) {
matrix[from][to] = weight;
}
/**
* 重载方法: 用传进来的矩阵初始化图的邻接矩阵
* @param matrix 传进来用于初始化邻接矩阵的矩阵
* @return void
*/
public void setMatrix(int[][] matrix) {
this.matrix = matrix;
}
/**
* 使图变成无向图(把邻接矩阵镜像化)
*
* @return void
*/
public void makeUndirected() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (matrix[i][j] > 0 && matrix[i][j] != matrix[j][i]) {
matrix[j][i] = matrix[i][j];
}
}
}
}
public void setDatas(T[] datas) {
this.datas = datas;
}
/**
* 初始化状态数组
*
* @return void
*/
private void initStatuses() {
for (int i = 0; i < N; i++) {
statuses[i] = Status.UNDISCOVERD;
}
}
/**
* 普利姆算法-最小生成树
*
* @return void
*/
public void PrimTree() {
// 记录最小生成树的边的集合
List<Edge> result = new ArrayList<>();
// 记录当前已被访问的节点索引(只需要N - 1个)
List<Integer> visited = new ArrayList<>();
// 从一个节点开始
// 找出与该节点邻接的所有节点中路径权值最小的
// 将这两个节点的边记录下来, 并且节点设置为已访问
statuses[0] = Status.VISITED;
visited.add(0);
// 最终结果有N - 1条边, 不满足则循环执行
while (result.size() < N - 1) {
// 记录最小权值
int minWeight = Integer.MAX_VALUE;
// 记录最小权值对应的边
Edge minEdge = null;
// 遍历已经被访问过的所有节点, 查找他们的邻接节点
for (int index : visited) {
// 循环遍历邻接矩阵中index行j列, 查看权重
for (int i = 0; i < N; i++) {
// 如果当前节点指向索引j节点有路径, 并且索引j节点未被访问
int weight = matrix[index][i];
if (weight > 0 && statuses[i] == Status.UNDISCOVERD && weight < minWeight) {
// 如果这个权重比最小权重还小
// 记录这条边
minEdge = new Edge(index, i);
// 更新最小权值
minWeight = weight;
}
}
}
// 最小边加入集合
result.add(minEdge);
// 最小边另一个端点得加入visited
visited.add(minEdge.B);
// 设置边的端点为已访问
statuses[minEdge.B] = Status.VISITED;
}
// 循环结束后, 打印最小生成树邻接矩阵
int[][] treeMatrix = new int[N][N];
for (Edge edge : result) {
treeMatrix[edge.A][edge.B] = matrix[edge.A][edge.B];
}
System.out.println(result);
System.out.println("最小生成树的邻接矩阵: ");
for (int[] nums : treeMatrix) {
System.out.println(Arrays.toString(nums));
}
}
public static void main(String[] args) {
Graph<String> graph = new Graph<>(7);
graph.setDatas(new String[]{"A", "B", "C", "D", "E", "F", "G"});
int[][] matrix = {
{0, 7, 3, 2, 2, 0, 0},
{0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 4, 3, 0},
{0, 0, 0, 0, 1, 10, 2},
{0, 0, 0, 0, 0, 4, 2},
{0, 0, 0, 0, 0, 0, 7},
{0, 0, 0, 0, 0, 0, 0}};
graph.setMatrix(matrix);
graph.makeUndirected();
graph.PrimTree();
}
}
