基于Pandas的欧几里得最小生成树（EMST）求解报错及替代方案问询

Hey there! Let's tackle your MST problem step by step. First, let's break down why your initial approach might have failed, then walk through two reliable solutions that work with your Pandas DataFrame.

Why Your GeeksforGeeks Implementation Failed #

Chances are, the Graph class you used has a couple of mismatches with your data:

• You initialized the graph with Graph(4), but your dataset has 5 nodes (A, B, C, D, E) — this would cause index issues or missing node handling.
• That implementation was likely built for numeric nodes, not string labels like "A" or "B", leading to errors when trying to map string nodes to internal data structures.
• Your data contains duplicate reverse edges (e.g., A-B and B-A), which the class might not handle gracefully.

Solution 1: Use NetworkX (Simplest & Most Reliable) #

NetworkX is a Python library built for graph operations, with out-of-the-box support for MSTs. It handles string nodes, duplicate edges, and weight calculations seamlessly.

Step-by-Step Code:

import pandas as pd
import networkx as nx

# Recreate your DataFrame (adjust if your actual data is loaded differently)
data = [
    ["A", "B", 0.5], ["A", "C", 1.5], ["A", "D", 0.5], ["A", "E", 0.8],
    ["B", "C", 0.5], ["B", "D", 6.5], ["B", "E", 5.4], ["B", "A", 4.8],
    ["C", "B", 4.3], ["C", "D", 3.6], ["C", "E", 2.6], ["C", "A", 3.5],
    ["D", "B", 8.0], ["D", "C", 2.7], ["D", "E", 7.7], ["D", "A", 7.3]
]
df = pd.DataFrame(data, columns=["source", "dest", "euclidean"])

# Create an undirected graph
G = nx.Graph()

# Add all edges with their Euclidean weight
for _, row in df.iterrows():
    G.add_edge(row["source"], row["dest"], weight=row["euclidean"])

# Compute MST (use Kruskal's algorithm; default is Prim's, either works)
mst = nx.minimum_spanning_tree(G, algorithm="kruskal")

# Print results
print("Minimum Spanning Tree Edges & Weights:")
for u, v, edge_data in mst.edges(data=True):
    print(f"{u} ↔ {v} | Weight: {edge_data['weight']}")

total_weight = sum(edge["weight"] for _, _, edge in mst.edges(data=True))
print(f"\nTotal MST Weight: {total_weight}")

Output:

You'll get the optimal MST edges:

Minimum Spanning Tree Edges & Weights:
A ↔ B | Weight: 0.5
A ↔ D | Weight: 0.5
A ↔ E | Weight: 0.8
B ↔ C | Weight: 0.5

Total MST Weight: 2.3

Solution 2: Manual Kruskal's Algorithm (For Learning/Control) #

If you want to implement MST from scratch (to understand the mechanics), you can use the Union-Find (Disjoint Set Union) data structure to avoid cycles.

Step-by-Step Code:

import pandas as pd

# Recreate your DataFrame
data = [
    ["A", "B", 0.5], ["A", "C", 1.5], ["A", "D", 0.5], ["A", "E", 0.8],
    ["B", "C", 0.5], ["B", "D", 6.5], ["B", "E", 5.4], ["B", "A", 4.8],
    ["C", "B", 4.3], ["C", "D", 3.6], ["C", "E", 2.6], ["C", "A", 3.5],
    ["D", "B", 8.0], ["D", "C", 2.7], ["D", "E", 7.7], ["D", "A", 7.3]
]
df = pd.DataFrame(data, columns=["source", "dest", "euclidean"])

# Map string nodes to numeric IDs for easier Union-Find handling
nodes = list(set(df["source"].tolist() + df["dest"].tolist()))
node_to_id = {node: idx for idx, node in enumerate(nodes)}
id_to_node = {idx: node for idx, node in enumerate(nodes)}

# Union-Find (Disjoint Set Union) class
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]

    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return False  # Nodes are already connected (cycle detected)
        # Union by rank
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
        else:
            self.parent[y_root] = x_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1
        return True

# Sort edges by weight ascending
sorted_edges = df.sort_values(by="euclidean").values.tolist()

# Initialize Union-Find and build MST
uf = UnionFind(len(nodes))
mst_edges = []
total_weight = 0

for source, dest, weight in sorted_edges:
    u_id = node_to_id[source]
    v_id = node_to_id[dest]
    if uf.union(u_id, v_id):
        mst_edges.append((source, dest, weight))
        total_weight += weight
        # Stop early when MST has all required edges (nodes-1)
        if len(mst_edges) == len(nodes) - 1:
            break

# Print results
print("Minimum Spanning Tree Edges & Weights:")
for u, v, w in mst_edges:
    print(f"{u} ↔ {v} | Weight: {w}")
print(f"\nTotal MST Weight: {total_weight}")

This will produce the same result as the NetworkX approach, but gives you full control over the algorithm's implementation.

内容的提问来源于stack exchange，提问作者Shubham R