---
# System prepended metadata

title: Finding Undirected Steiner Tree
tags: [Algorithms, Data Structures and Algorithms]

---

[Home Page - Algorithms](/@roger61205/Algorithms)
[toc]

Let $G=(V,E)$ be a connected, undirected and weighted path.
# Kou
## Algorithm
### Metric Closure
The metric closure of a graph $G$ is the complete graph in which each edge is weighted by the shortest path distance between the nodes in $G$.
1. Step 1
    Create an empty list $M$ for the metric closure.
2. Step 2
    Find the all-pairs shortest path on $G$.
3. Step 3
    For each $u\in V$, add the shortest path from $u$ to another $v\in V$ to $M$.
### Method
1. Step 1
    Create a metric closure $M$
2. Step 2
    Create a subgraph $H$ including only terminal nodes.
3. Step 3
    Find the edges of the minimum spanning tree of $H$.
4. Step 4
    Find the MST again, over the new set of edges.
5. Step 5
    Removes nodes that are not in the Stenier tree.



**References**
[NetworkX - GitHub](https://github.com/networkx)