{"id":83641,"date":"2021-08-20T09:00:34","date_gmt":"2021-08-20T03:30:34","guid":{"rendered":"https:\/\/techvidvan.com\/tutorials\/?p=83641"},"modified":"2021-08-20T09:00:34","modified_gmt":"2021-08-20T03:30:34","slug":"spanning-tree","status":"publish","type":"post","link":"https:\/\/techvidvan.com\/tutorials\/spanning-tree\/","title":{"rendered":"Spanning Tree in Data Structure"},"content":{"rendered":"

A spanning tree is a tree that connects all the vertices of a graph with the minimum possible number of edges. Thus, a spanning tree is always connected. Also, a spanning tree never contains a cycle. A spanning tree is always defined for a graph and it is always a subset of that graph. Thus, a disconnected graph can never have a spanning tree.<\/p>\n

Spanning Trees Terminologies:<\/h3>\n

1. Connected Graph:<\/strong> A connected graph is a graph in which we can reach any vertex from any vertex. Thus, in a connected graph, all vertices are connected to each other through at least one path.<\/p>\n

2. Undirected Graph:<\/strong> It is a graph in which the edges don\u2019t have a particular direction. In an undirected graph, the edges are bidirectional.<\/p>\n

3. Directed Graph:<\/strong> In this case, the edges are unidirectional. Thus, we can go from only one end to the other ends. For every edge, there is an associated direction.<\/p>\n

4. Simple graph:<\/strong> A simple graph is a graph that does not contain cycles and loops.<\/p>\n

Defining a Spanning Tree:<\/h3>\n

Every undirected and connected graph has a minimum of one spanning tree. Consider a graph having V vertices and E number of edges. Then, we will represent the graph as G(V, E)<\/strong>. Its spanning tree will be represented as G\u2019(V, E\u2019)<\/strong> where E\u2019 \u2286 E<\/strong> and the number of vertices remain the same. So, a spanning tree G\u2019 is a subgraph of G whose vertex set is the same but edges may be different.<\/p>\n

Example:<\/strong>
\nConsider the following undirected, simple and connected graph G having 4 vertices: A, B, C and D.<\/p>\n

\"Spanning<\/a><\/p>\n

There are many spanning trees possible for this graph. Some of them are shown below:<\/p>\n

\"\"<\/a> \"\"<\/a> \"\"<\/a> \"\"<\/a> \"\"<\/a> \"\"<\/a> \"Spanning<\/a><\/p>\n

The above graph G was a complete graph having 4 vertices. For any complete graph, the number of spanning trees is nn-2.<\/strong> Thus, in the worst case, the number of spanning trees formed is of the order O(n2).<\/strong><\/p>\n

General Properties of Spanning Trees:<\/h3>\n
    \n
  • There can be more than one spanning tree possible for an undirected, connected graph.<\/li>\n
  • In the case of directed graphs, the minimum spanning tree is the one having minimum edge weight.<\/li>\n
  • All the possible spanning trees of a graph have the same number of edges and vertices.<\/li>\n
  • A spanning tree can never contain a cycle.<\/li>\n
  • Spanning tree is always minimally connected<\/strong> i.e. if we remove one edge from the spanning tree, it will become disconnected.<\/li>\n
  • A spanning tree is maximally acyclic<\/strong> i.e. if we add one edge to the spanning tree, it will create a cycle or a loop.<\/li>\n
  • It is possible to have more than one minimum spanning tree if the graph weights of some edges are the same.<\/li>\n
  • Any connected and undirected graph will always have at least one spanning tree.<\/li>\n<\/ul>\n

    Mathematical Properties of Spanning Trees:<\/h3>\n
      \n
    • For any complete graph, the number of spanning trees is nn-2.<\/strong><\/li>\n
    • In a complete graph, we can create a spanning tree by removing a maximum of E-N+1<\/strong> edges. Here, E = Number of edges and N = Number of nodes\/vertices.<\/li>\n
    • For a simple connected graph, its spanning tree will have N-1<\/strong> edges, where N is the number of vertices.<\/li>\n<\/ul>\n

      Minimum Spanning Tree:<\/h3>\n

      A minimum spanning tree is defined for a weighted graph. A spanning tree having minimum weight is defined as a minimum spanning tree. This weight depends on the weight of the edges. In real-world applications, the weight could be the distance between two points, cost associated with the edges or simply an arbitrary value associated with the edges.<\/p>\n

      Minimum Spanning Tree Algorithms:<\/h3>\n

      There are various algorithms in computer science that help us find the minimum spanning tree for a weighted graph. Some of these algorithms are:<\/p>\n

      1. Prim\u2019s Algorithm
      \n2. Kruskal\u2019s Algorithm
      \n3. Both these algorithms follow the greedy approach to find the minimum cost spanning tree.<\/p>\n

      Applications of Spanning Tree:<\/h3>\n
        \n
      • For implementing Routing protocols in computer networks<\/li>\n
      • In civil network planning to build networks<\/li>\n
      • For clustering i.e. grouping similar objects under one category and distinguishing from other categories<\/li>\n<\/ul>\n

        Applications of Minimum Spanning Tree:<\/h3>\n
          \n
        • In designing telecommunication networks and water supply networks<\/li>\n
        • For finding paths in a map<\/li>\n
        • In electrical grid systems<\/li>\n<\/ul>\n

          Conclusion:<\/h3>\n

          In this article, we have seen what is a spanning tree and what is a minimum spanning tree. We have also seen their examples and applications. The article also covers the general as well as mathematical properties of spanning trees.<\/p>\n","protected":false},"excerpt":{"rendered":"

          A spanning tree is a tree that connects all the vertices of a graph with the minimum possible number of edges. Thus, a spanning tree is always connected. Also, a spanning tree never contains...<\/p>\n","protected":false},"author":1,"featured_media":84144,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3555],"tags":[4080,4081,4082,4083],"class_list":["post-83641","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structure","tag-minimum-spanning-tree","tag-spanning-tree","tag-spanning-trees","tag-spanning-trees-in-data-structure"],"yoast_head":"\nSpanning Tree in Data Structure - TechVidvan<\/title>\n<meta name=\"description\" content=\"Learn what is a spanning tree and what is a minimum spanning tree. See their properties, examples and applications.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/techvidvan.com\/tutorials\/spanning-tree\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Spanning Tree in Data Structure - TechVidvan\" \/>\n<meta property=\"og:description\" content=\"Learn what is a spanning tree and what is a minimum spanning tree. See their properties, examples and applications.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/techvidvan.com\/tutorials\/spanning-tree\/\" \/>\n<meta property=\"og:site_name\" content=\"TechVidvan\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/TechVidvan\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-08-20T03:30:34+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/08\/TV-Spanning-tree-in-DS.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"628\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"TechVidvan Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@vidvantech\" \/>\n<meta name=\"twitter:site\" content=\"@vidvantech\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"TechVidvan Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"5 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Spanning Tree in Data Structure - TechVidvan","description":"Learn what is a spanning tree and what is a minimum spanning tree. See their properties, examples and applications.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/techvidvan.com\/tutorials\/spanning-tree\/","og_locale":"en_US","og_type":"article","og_title":"Spanning Tree in Data Structure - TechVidvan","og_description":"Learn what is a spanning tree and what is a minimum spanning tree. See their properties, examples and applications.","og_url":"https:\/\/techvidvan.com\/tutorials\/spanning-tree\/","og_site_name":"TechVidvan","article_publisher":"https:\/\/www.facebook.com\/TechVidvan\/","article_published_time":"2021-08-20T03:30:34+00:00","og_image":[{"width":1200,"height":628,"url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/08\/TV-Spanning-tree-in-DS.jpg","type":"image\/jpeg"}],"author":"TechVidvan Team","twitter_card":"summary_large_image","twitter_creator":"@vidvantech","twitter_site":"@vidvantech","twitter_misc":{"Written by":"TechVidvan Team","Est. reading time":"5 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/techvidvan.com\/tutorials\/spanning-tree\/#article","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/spanning-tree\/"},"author":{"name":"TechVidvan Team","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22"},"headline":"Spanning Tree in Data Structure","datePublished":"2021-08-20T03:30:34+00:00","mainEntityOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/spanning-tree\/"},"wordCount":733,"commentCount":0,"publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/spanning-tree\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/08\/TV-Spanning-tree-in-DS.jpg","keywords":["Minimum Spanning Tree","Spanning Tree","Spanning Trees","Spanning Trees in Data Structure"],"articleSection":["Data Structure Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/techvidvan.com\/tutorials\/spanning-tree\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/techvidvan.com\/tutorials\/spanning-tree\/","url":"https:\/\/techvidvan.com\/tutorials\/spanning-tree\/","name":"Spanning Tree in Data Structure - TechVidvan","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/#website"},"primaryImageOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/spanning-tree\/#primaryimage"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/spanning-tree\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/08\/TV-Spanning-tree-in-DS.jpg","datePublished":"2021-08-20T03:30:34+00:00","description":"Learn what is a spanning tree and what is a minimum spanning tree. See their properties, examples and applications.","breadcrumb":{"@id":"https:\/\/techvidvan.com\/tutorials\/spanning-tree\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/techvidvan.com\/tutorials\/spanning-tree\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/spanning-tree\/#primaryimage","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/08\/TV-Spanning-tree-in-DS.jpg","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/08\/TV-Spanning-tree-in-DS.jpg","width":1200,"height":628,"caption":"Spanning tree in Data Structure"},{"@type":"BreadcrumbList","@id":"https:\/\/techvidvan.com\/tutorials\/spanning-tree\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/techvidvan.com\/tutorials\/"},{"@type":"ListItem","position":2,"name":"Spanning Tree in Data Structure"}]},{"@type":"WebSite","@id":"https:\/\/techvidvan.com\/tutorials\/#website","url":"https:\/\/techvidvan.com\/tutorials\/","name":"TechVidvan Blogs","description":"","publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/techvidvan.com\/tutorials\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/techvidvan.com\/tutorials\/#organization","name":"TechVidvan","url":"https:\/\/techvidvan.com\/tutorials\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","width":200,"height":50,"caption":"TechVidvan"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/TechVidvan\/","https:\/\/x.com\/vidvantech"]},{"@type":"Person","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22","name":"TechVidvan Team","description":"The TechVidvan Team delivers practical, beginner-friendly tutorials on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. Our experts are here to help you upskill and excel in today\u2019s tech industry."}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/83641","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/comments?post=83641"}],"version-history":[{"count":0,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/83641\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media\/84144"}],"wp:attachment":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media?parent=83641"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/categories?post=83641"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/tags?post=83641"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}