Understanding Minimal Spanning Trees in Graph Theory
Dive into the concept of minimal spanning trees in graph theory with a focus on algorithms like Prim's and Kruskal's. Explore the definition of trees, spanning trees, and weighted graphs. Learn about the importance of finding the minimal spanning tree in a graph and how it contributes to optimization problems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Lecture 19 Minimal Spanning Trees CSCI 1900 Mathematics for Computer Science Fall 2014 Bill Pine
Lecture Introduction Reading Rosen Sections 11.4, 11.5 Spanning tree Weighted graphs Minimal spanning tree Two algorithms to generate Prim's algorithm Kruskal's algorithm CSCI 1900 Lecture 19 - 2
Tree Recall the definition of a tree A connected acyclic graph Any tree with n vertices has n - 1 edges CSCI 1900 Lecture 19 - 3
Spanning Tree T is a spanning tree of graph G, if T is a tree with The same vertices as G, and A subset of the edges of G CSCI 1900 Lecture 19 - 4
Notation A weighted graph is a graph, whose edges have an associated real-number weight Example: 30 B 10 C A 15 7 D The weight of the edge {A, B} is also called the distance between A and B CSCI 1900 Lecture 19 - 5
Notation Two vertices are neighbors if they are connected by an edge Two vertices are adjacent if they are neighbors The nearest neighbor of a vertex is the neighbor with the smallest weight CSCI 1900 Lecture 19 - 6
Notation (cont) Neighbors of A: B, C Neighbors of C: B, A, D B 30 10 C A 15 7 D Nearest Neighbor of A: C Nearest Neighbor of C: D CSCI 1900 Lecture 19 - 7
Minimal Spanning Tree A minimal spanning tree is a spanning tree for which the sum of the weights of all the edges is as small as possible CSCI 1900 Lecture 19 - 8
Spanning Trees Example B B 30 10 10 C C A A 15 15 7 7 wi = 32 D D B B 30 30 10 C C A C A 15 7 7 wi = 52 wi = 47 D D CSCI 1900 Lecture 19 - 9
Prims Algorithm Let R be a symmetric, connected relation with n vertices 1. Chose a vertex v1 of R Let V = {v1} and E ={ } 2. Choose a nearest neighbor vi of V that is adjacent to vj, vj V, and for which the edge (vi, vj) does not form a cycle with existing elements of E 3. Repeat step 2 until | E | = n-1 CSCI 1900 Lecture 19 - 10
Prims Algorithm (cont) Prim s algorithm is a member of the class of algorithms call greedy algorithms Greedy algorithms take decisions based upon what is optimal locally Greedy algorithms do not always generate an overall optimal solution However, Prim s algorithm can be shown to be optimal Running time = ( n2 ) CSCI 1900 Lecture 19 - 11
Prims Algorithm f f 6 6 5 7 12 h c h c 13 1 1 1 1 8 e e 11 2 2 b b 10 3 3 g g 7 2 2 d d 5 6 3 3 a a Start with vertex f CSCI 1900 Lecture 19 - 12
Kruskals Algorithm Let R be a symmetric, connected relation with n vertices, with S = { e1, e2, , ek}: the set of weighted edges 1. Choose an edge e1 in S of the smallest weight Let E = {e1} Replace S with S {e1} 2. Chose an edge ei in S of the smallest weight that does not make a cycle with members of E Replace E with E U {ei} and S with S {e1} 3. Repeat Step 2 until | E | = n-1 CSCI 1900 Lecture 19 - 13
Kruskals Algorithm (cont) Kruskal s algorithm is also a greedy algorithm Running time = (n lg( n )) CSCI 1900 Lecture 19 - 14
Kruskals Algorithm f f 6 5 6 7 12 h c h c 13 1 1 1 1 8 e e 11 2 2 b b 10 3 g 3 g 7 2 2 d 5 d 6 3 3 a a CSCI 1900 Lecture 19 - 15
Key Concepts Summary Spanning tree Weighted graphs Minimal spanning tree Two algorithms to generate Prim's algorithm Kruskal's algorithm Reading for next time Kolman Section 10.3 CSCI 1900 Lecture 19 - 16
