【图论】最小生成树（python和cpp）

一、声明

• 本帖持续更新中
• 如有纰漏望指正！

二、简介

（a）点云建立的k近邻图	（b）k近邻图上建立的最小生成树

最小生成树 (Minimum Spanning Tree，简称 MST) 是一种在带权无向图中的树，它连接了图中所有节点并且总权重最小。在最小生成树中，任意两个节点之间有且仅有一条路径，同时这些路径的权重之和最小。
最小生成树的应用场景非常广泛。以下是一些常见的应用场景：

• 网络设计：在计算机网络或通信网络中，最小生成树可以用来构建最优的网络拓扑结构，以便实现高效的数据传输和通信。
• 物流规划：在物流管理中，最小生成树可以用来确定最短路径，从而有效地规划货物的运输路线，降低物流成本。
• 电力传输：在电力系统中，最小生成树可以用于确定电力输电线路的布置，确保电力从发电站到各个用户点的传输成本最小。
• 集群分析：在数据挖掘和机器学习中，最小生成树可以用于聚类分析，帮助发现数据点之间的相关性和相似性。
• 电路板设计：在电路板设计中，最小生成树可以用来确定电路中的连接线路，以便最小化电路板的制造成本。

最小生成树算法有多种，其中最著名且常用的算法是普里姆算法（Prim’s algorithm）和克鲁斯卡尔算法（Kruskal’s algorithm），它们可以高效地找到最小生成树。

三、代码

C++代码

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <iostream>
#include <vector>int main() {// Define the graph using adjacency_listtypedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,boost::no_property, boost::property<boost::edge_weight_t, int>> Graph;typedef boost::graph_traits<Graph>::edge_descriptor Edge;typedef boost::property_map<Graph, boost::edge_weight_t>::type WeightMap;// Create a graph objectGraph g;// Add edges to the graphadd_edge(0, 1, 2, g);add_edge(1, 2, 3, g);add_edge(0, 3, 1, g);// ... Add other edges as needed// Vector to store the resulting MST edgesstd::vector<Edge> spanning_tree;// Compute the minimum spanning tree using Kruskal's algorithmboost::kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));// Print the edges in the MSTfor (std::vector<Edge>::iterator ei = spanning_tree.begin(); ei != spanning_tree.end(); ++ei) {std::cout << source(*ei, g) << " <--> " << target(*ei, g)<< " with weight of " << get(boost::edge_weight, g, *ei) << std::endl;}return 0;
}

Python代码

import open3d as o3d
import numpy as np
import networkx as nx
from scipy.spatial import KDTree
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3Ddef create_knn_graph(point_cloud, k):# Convert Open3D point cloud to numpy arraypoints = np.asarray(point_cloud.points)# Build a KDTree for efficient nearest neighbor searchtree = KDTree(points)# Create a graphG = nx.Graph()# Add nodes and edges based on k nearest neighborsfor i in range(len(points)):distances, indices = tree.query(points[i], k=k+1)  # k+1 because the point itself is includedfor j in range(1, k+1):  # Skip the first one (itself)G.add_edge(i, indices[j], weight=distances[j])return Gdef find_mst(graph):# Compute the minimum spanning treereturn nx.minimum_spanning_tree(graph)def plot_3d_graph(graph, pos_3d):# Create a 3D plotfig = plt.figure(figsize=(8, 6))ax = fig.add_subplot(111, projection='3d')# Extract the x, y, z coordinates of each nodexs, ys, zs = zip(*[pos_3d[node] for node in graph.nodes()])# Plot the nodesax.scatter(xs, ys, zs)# Plot the edgesfor edge in graph.edges():x_coords, y_coords, z_coords = zip(*(pos_3d[edge[0]], pos_3d[edge[1]]))ax.plot(x_coords, y_coords, z_coords, color='blue')# Set labels and show plotax.set_xlabel('X axis')ax.set_ylabel('Y axis')ax.set_zlabel('Z axis')# plt.show()plt.axis("equal")plt.savefig("1.png")# Load point cloud
pcd = o3d.io.read_point_cloud("1.ply") # Adjust the file path# Create the kNN graph (choose your k)
k = 5  # For example, k=5
knn_graph = create_knn_graph(pcd, k)# Find the minimum spanning tree
mst = find_mst(knn_graph)# Extract positions from the 3D point cloud
pos_3d = {i: pos for i, pos in enumerate(np.asarray(pcd.points))}# Plot the 3D graph of the minimum spanning tree
plot_3d_graph(mst, pos_3d)