Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is a Steiner Tree?
3.
Spanning Tree Vs. Steiner Tree
4.
Algorithm
5.
Solution
6.
Applications of Steiner Tree
7.
Frequently Asked Questions
7.1.
What is a Spanning Tree?
7.2.
What is a Minimum Spanning Tree?
7.3.
Can a Steiner Tree contain vertices that are not in the given subset?
8.
Conclusion
Last Updated: Mar 27, 2024

Steiner Tree Problem

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

In the blog, we will look at the Steiner tree problem in which we are given an undirected graph with positive edge weights, and a subset of vertices in that graph are given, the task is to find the minimum cost of the Steiner Tree.

Steiner Tree Problem

What is a Steiner Tree?

In the problem, a graph and a subset of vertices in that graph are given, where a Steiner tree is a tree that spans through the given subset. It is possible that the Steiner tree may contain some vertices which are not a part of the given subset but are used to connect the vertices of the subset. The set of vertices provided is called Terminal vertices, whereas the set of vertices that are used to construct the Steiner tree is called the Steiner vertices.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Spanning Tree Vs. Steiner Tree

A spanning tree or a minimum spanning tree is a tree that has the minimum weight and such that it spans through all the vertices. If the given subset of vertices is equal to the set of vertices in the Steiner Tree problem, then the problem reduces to finding the minimum spanning tree problem. If the given subset has only two vertices, then the problem reduces to the shortest path problem between two vertices. The minimum spanning tree problem is a polynomial-time solvable problem, whereas the minimum Steiner tree problem is NP-Hard, and the related decision problem is NP-Complete.

Algorithm

  • We start with a subtree T such that it contains any one of the given terminal vertexes.
  • While the subtree T doesn’t span all of the terminals
    • Select a terminal (x) such that it is not in subtree T and is closest to a vertex in T.
    • Now, add to the subtree T the shortest path that connects x with T.

The algorithm mentioned above is (2-2/n) approximate, which means that it guarantees that the solution which is produced by this algorithm is not more than this ratio of optimized solution for a given graph with n vertices. 

Solution

Input graph
  • Start by adding terminal B to the subtree T.
  • Now, choose a terminal which is closest to a vertex in T but is not in T itself.
  • The vertices which are connected to B are:
    • A(4)
    • C(6)
    • D(5)
      Choosing the terminal with the minimum weight possible: vertex A.
  • Repeat Step 2 by following Dijkstra’s Algorithm until all vertices are traversed.
  • Dijkstra’s Algorithm uses the formula:
  • dx(y): least cost path from x to y
  • dx(y) = minv { c(x, v) + dv(y) }
  • The final cost of the Steiner tree for the above problem is:
Final cost graph

 

Path: B - A - D - C E - F - G

Cost: 0 + 4 + 5 + 6 + 7 + 7 + 10 = 39

Applications of Steiner Tree

Some of the areas where a Steiner Tree is used are mentioned below:

  • VLSI design
  • Wireless Communication
  • Network Routing
  • Computational biology

Frequently Asked Questions

What is a Spanning Tree?

A Spanning tree is defined as a sub-graph that includes all the vertices of the graph with the minimum possible number of edges.

What is a Minimum Spanning Tree?

A Minimum Spanning Tree is a spanning tree in which the sum of the weight of all the edges is as minimum as possible.

Can a Steiner Tree contain vertices that are not in the given subset?

Yes, a Steiner Tree can contain vertices that are not in the given subset. Such vertices are used to connect the vertices of the given subset.

Conclusion

In this article, we have extensively discussed the Steiner Tree Problem

After reading about this problem, are you not feeling excited to read/explore more articles on Graph? Don’t worry; Coding Ninjas has you covered. To learn about the different types of graphs and applications, what is the difference between a graph and a tree, and what is breadth-first search.  

Check out this problem - Duplicate Subtree In Binary Tree

If you wish to enhance your skills in Data Structures and AlgorithmsCompetitive ProgrammingJavaScript, etc., you should check out our Guided path column at Code studio. We at Coding Ninjas Studio organize many contests in which you can participate. You can also prepare for the contests and test your coding skills by giving the mock test series available. In case you have just started the learning process, and your dream is to crack major tech giants like Amazon, Microsoft, etc., then you should check out the most frequently asked problems and the interview experiences of your seniors that will surely help you in landing a job in your dream company. 

Do upvote if you find the blogs helpful.

Happy Learning!

Thank you Image
Live masterclass