概念
- 圖的生成樹是圖的子圖是尔，并且不形成環(huán)路
- 最小生成樹是帶權圖中所有生成樹里邊權值總和最小的一個解惊奇，可能不唯一
算法思路
- 以圖的一個節(jié)點開始
- 找出所有已被訪問的節(jié)點的鄰接節(jié)點中未訪問且邊權值最小的一個節(jié)點以及對應邊互躬，加入樹中
- 只要樹的邊數(shù)小于節(jié)點數(shù) - 1就執(zhí)行第二步
算法實現(xiàn)
圖的實現(xiàn)
- 此實現(xiàn)方法沒有節(jié)點類
- 采用鄰接矩陣和頂點索引
- 邊類有兩個成員變量，用于記錄兩個端點的索引
int A赊时，int B - 使用枚舉來定義節(jié)點的狀態(tài)
enum Status { UNDISCOVERD, VISITED } - 枚舉數(shù)組
Status[] statuses記錄每個節(jié)點的狀態(tài) - 鄰接矩陣
int[][] matrix(鄰接矩陣無需設置為沿對角線對稱)-
matrix[i][j]表示從索引i的節(jié)點指向索引j的節(jié)點的權值 - 權值為0表示兩點不連接或者自身與自身不連接
-
enum Status { // 節(jié)點對象的狀態(tài)
// 未被發(fā)現(xiàn), 已被遍歷
UNDISCOVERD, VISITED
}
public class Graph<T> {
private int N; // N個節(jié)點
public int[][] matrix; // 鄰接矩陣
private Status[] statuses; // 保存每個節(jié)點的狀態(tài)
private T[] datas; // 保存每個節(jié)點的數(shù)據(jù)
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] +
'>';
}
}
}
核心步驟
- 由于最小生成樹的邊數(shù) = 圖節(jié)點數(shù) - 1吨铸，所以只要最終結果的邊集合長度小于節(jié)點數(shù) - 1
result.size() < N - 1，就循環(huán)執(zhí)行找出權值最小的節(jié)點以及邊 - 每次循環(huán)都需要記錄最小權值
minWeight祖秒，最小權值的邊minEdge- 內(nèi)層循環(huán)遍歷所有已訪問節(jié)點
for (int index : visited)- 最內(nèi)層循環(huán)，先確定當前要找后繼節(jié)點的節(jié)點索引舟奠，也就是for循環(huán)的每一個
index竭缝，然后遍歷鄰接矩陣中index行i列，也就是圖中索引index的節(jié)點指向索引i節(jié)點的邊沼瘫，記錄權值weight = matrix[index][i]- 如果權值大于0
weight > 0并且后繼節(jié)點未被訪問statuses[i] == Status.UNDISCOVERD并且權重小于當前記錄的最小權值weight < minWeight抬纸，則記錄這條邊minEdge = new Edge(index, i)，更新最小權值minWeight = weight - 由于Prim算法是基于節(jié)點的耿戚，所以不用像基于邊的Kruskal算法
一樣判斷是否生成環(huán)湿故，只要選擇未被訪問的節(jié)點，就不會生成環(huán)
- 如果權值大于0
- 最內(nèi)層循環(huán)，先確定當前要找后繼節(jié)點的節(jié)點索引舟奠，也就是for循環(huán)的每一個
- 每次內(nèi)層循環(huán)就找到了一條最小權值邊膜蛔，以及另一個端點坛猪，于是把最小邊加入集合
result.add(minEdge)，該端點加入已訪問的節(jié)點集合visited.add(minEdge.B)皂股，設置該點狀態(tài)為已訪問statuses[minEdge.B] = Status.VISITED
- 內(nèi)層循環(huán)遍歷所有已訪問節(jié)點
while (result.size() < N - 1) {
// 記錄最小權值
int minWeight = Integer.MAX_VALUE;
// 記錄最小權值對應的邊
Edge minEdge = null;
// 遍歷已經(jīng)被訪問過的所有節(jié)點, 查找他們的鄰接節(jié)點
for (int index : visited) {
// 循環(huán)遍歷鄰接矩陣中index行j列, 查看權重
for (int i = 0; i < N; i++) {
// 如果當前節(jié)點指向索引j節(jié)點有路徑, 并且索引j節(jié)點未被訪問
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記錄當前已被訪問的節(jié)點索引
-
- 將第一個節(jié)點狀態(tài)設置為已被訪問
statuses[0] = Status.VISITED - 將第一個節(jié)點添加到
visited - 只要
result元素數(shù)量小于節(jié)點數(shù) - 1result.size() < N - 1則循環(huán)執(zhí)行- 聲明變量最小權值
int minWeight墅茉，最小權值的邊Edge minEdge - 遍歷已經(jīng)被訪問過的所有節(jié)點, 查找他們的鄰接節(jié)點
- 記錄找到的最小權值的節(jié)點，對應邊呜呐，設置節(jié)點狀態(tài)
- 聲明變量最小權值
- 循環(huán)結束后聲明一個樹的鄰接矩陣就斤，遍歷每條邊
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<>();
// 記錄當前已被訪問的節(jié)點索引(只需要N - 1個)
List<Integer> visited = new ArrayList<>();
// 從一個節(jié)點開始
// 找出與該節(jié)點鄰接的所有節(jié)點中路徑權值最小的
// 將這兩個節(jié)點的邊記錄下來, 并且節(jié)點設置為已訪問
statuses[0] = Status.VISITED;
visited.add(0);
// 最終結果有N - 1條邊, 不滿足則循環(huán)執(zhí)行
while (result.size() < N - 1) {
// 記錄最小權值
int minWeight = Integer.MAX_VALUE;
// 記錄最小權值對應的邊
Edge minEdge = null;
// 遍歷已經(jīng)被訪問過的所有節(jié)點, 查找他們的鄰接節(jié)點
for (int index : visited) {
// 循環(huán)遍歷鄰接矩陣中index行j列, 查看權重
for (int i = 0; i < N; i++) {
// 如果當前節(jié)點指向索引j節(jié)點有路徑, 并且索引j節(jié)點未被訪問
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;
}
// 循環(huán)結束后, 打印最小生成樹鄰接矩陣
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));
}
}
測試
- 創(chuàng)建7個節(jié)點的圖
new Graph<>(7) - 設置圖節(jié)點保存的數(shù)據(jù)為"ABCDEFG"七個字母
- 初始化鄰接矩陣
graph.setMatrix(matrix) - 將圖變成無向圖也就是鄰接矩陣沿左對角線對稱
graph.makeUndirected() - 執(zhí)行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 { // 節(jié)點對象的狀態(tài)
// 未被發(fā)現(xiàn), 已被遍歷
UNDISCOVERD, VISITED
}
public class Graph<T> {
private int N; // 節(jié)點個數(shù)
public int[][] matrix; // 鄰接矩陣
private T[] datas; // 保存每個節(jié)點的數(shù)據(jù)
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]; // 泛型數(shù)組實例化
}
/**
* 鄰接矩陣保存的信息是從一個節(jié)點指向另一個節(jié)點的信息
*
* @param from 從這個節(jié)點
* @param to 指向這個節(jié)點
* @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;
}
/**
* 初始化狀態(tài)數(shù)組
*
* @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<>();
// 記錄當前已被訪問的節(jié)點索引(只需要N - 1個)
List<Integer> visited = new ArrayList<>();
// 從一個節(jié)點開始
// 找出與該節(jié)點鄰接的所有節(jié)點中路徑權值最小的
// 將這兩個節(jié)點的邊記錄下來, 并且節(jié)點設置為已訪問
statuses[0] = Status.VISITED;
visited.add(0);
// 最終結果有N - 1條邊, 不滿足則循環(huán)執(zhí)行
while (result.size() < N - 1) {
// 記錄最小權值
int minWeight = Integer.MAX_VALUE;
// 記錄最小權值對應的邊
Edge minEdge = null;
// 遍歷已經(jīng)被訪問過的所有節(jié)點, 查找他們的鄰接節(jié)點
for (int index : visited) {
// 循環(huán)遍歷鄰接矩陣中index行j列, 查看權重
for (int i = 0; i < N; i++) {
// 如果當前節(jié)點指向索引j節(jié)點有路徑, 并且索引j節(jié)點未被訪問
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;
}
// 循環(huán)結束后, 打印最小生成樹鄰接矩陣
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();
}
}
