Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees. We can also assign a weight to each edge, which is a number representing how unfavorable it is, and use this to assign a weight to a spanning tree by computing the sum of the weights of the edges in that spanning tree. | Minimum Spanning Tree Spanning Tree Given a connected weighted undirected graph G, a spanning tree of G is a subgraph of G that contains all of G’s nodes and enough of its edges to form a tree. v1 v4 v3 v5 v2 Spanning tree Spanning tree is not unique! Tell the students some application of spanning tree. What is A Spanning Tree? u v b a c d e f A spanning tree for an undirected graph G=(V,E) is a subgraph of G that is a tree and contains all the vertices of G Can a graph have more than one spanning tree? Yes Can an unconnected graph have a spanning tree? No DFS spanning tree Generate the spanning tree edge during the DFS traversal. Algorithm dfsSpanningTree(v) mark v as visited; for (each unvisited node u adjacent to v) { mark the edge from u to v; dfsSpanningTree(u); } Similar to DFS, the spanning tree edges can be generated based on BFS traversal. Example of generating spanning tree based on DFS v1 v4 v3 v5 v2 G stack v3 v3 v2 v3, v2 v1 v3, v2, v1 backtrack v3, v2 v4 v3, v2, v4 v5 v3, v2, v4 , v5 backtrack v3, v2, v4 backtrack v3, v2 backtrack v3 backtrack empty x x x x x Spanning Tree Use BFS and DFS Find a spanning subgraph of G and draw it below. Draw all the different spanning trees of G Minimal Spanning Tree. 4 4 3 2 9 15 8 10 14 3 u v b a c d e f Mst T: w( T )= (u,v) T w(u,v ) is minimized The weight of a subgraph is the sum of the weights of it edges. A minimum spanning tree for a weighted graph is a spanning tree with minimum weight. Can a graph have more then one minimum spanning tree? Yes, maybe Minimum Spanning Tree Consider a connected undirected graph where Each node x represents a country x Each edge (x, y) has a number which measures the cost of placing telephone line between country x and country y Problem: connecting all countries while minimizing the total cost Solution: find a spanning tree with minimum total weight, that is, minimum spanning tree Formal definition of minimum spanning tree Given a connected | Minimum Spanning Tree Spanning Tree Given a connected weighted undirected graph G, a spanning tree of G is a subgraph of G that contains all of G’s nodes and enough of its edges to form a tree. v1 v4 v3 v5 v2 Spanning tree Spanning tree is not unique! Tell the students some application of spanning tree. What is A Spanning Tree? u v b a c d e f A spanning tree for an undirected graph G=(V,E) is a subgraph of G that is a tree and contains all the vertices of G Can a graph have more than one spanning tree? Yes Can an unconnected graph have a spanning tree? No DFS spanning tree Generate the spanning tree edge during the DFS traversal. Algorithm dfsSpanningTree(v) mark v as visited; for (each unvisited node u adjacent to v) { mark the edge from u to v; dfsSpanningTree(u); } Similar to DFS, the spanning tree edges can be generated based on BFS traversal. Example of generating spanning tree based on DFS v1 v4 v3 v5 v2 G stack v3 v3 v2 v3, v2 v1 v3, v2, v1 backtrack v3, v2 v4
