Scribd Logo
Upload

Welcome to Scribd!

  • 31 views

    Showclassmst

    Uploaded by

    Vijaya Azimuddin
    This document discusses minimum spanning trees and algorithms for finding them in graphs. It introduces minimum spanning trees as sets of edges that connect all vertices of a graph with minimum total cost. Two common algorithms are presented: Prim's algorithm, which builds up the tree by iteratively adding the lowest-weight connecting edge; and Kruskal's algorithm, which sorts edges by weight and adds them if they do not form cycles. The algorithms run in O(E log V) time using priority queues and disjoint set data structures. Applications of minimum spanning trees include networking, circuit design, clustering, and approximating graphs.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Showclassmst

    Uploaded by

    Vijaya Azimuddin
    31 views17 pages
    This document discusses minimum spanning trees and algorithms for finding them in graphs. It introduces minimum spanning trees as sets of edges that connect all vertices of a graph with minimum total cost. Two common algorithms are presented: Prim's algorithm, which builds up the tree by iteratively adding the lowest-weight connecting edge; and Kruskal's algorithm, which sorts edges by weight and adds them if they do not form cycles. The algorithms run in O(E log V) time using priority queues and disjoint set data structures. Applications of minimum spanning trees include networking, circuit design, clustering, and approximating graphs.

    Original Title

    showclassmst

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses minimum spanning trees and algorithms for finding them in graphs. It introduces minimum spanning trees as sets of edges that connect all vertices of a graph with minimum total cost. Two common algorithms are presented: Prim's algorithm, which builds up the tree by iteratively adding the lowest-weight connecting edge; and Kruskal's algorithm, which sorts edges by weight and adds them if they do not form cycles. The algorithms run in O(E log V) time using priority queues and disjoint set data structures. Applications of minimum spanning trees include networking, circuit design, clustering, and approximating graphs.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    31 views17 pages

    Showclassmst

    Uploaded by

    Vijaya Azimuddin
    This document discusses minimum spanning trees and algorithms for finding them in graphs. It introduces minimum spanning trees as sets of edges that connect all vertices of a graph with minimum total cost. Two common algorithms are presented: Prim's algorithm, which builds up the tree by iteratively adding the lowest-weight connecting edge; and Kruskal's algorithm, which sorts edges by weight and adds them if they do not form cycles. The algorithms run in O(E log V) time using priority queues and disjoint set data structures. Applications of minimum spanning trees include networking, circuit design, clustering, and approximating graphs.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 17

    Graph Algorithms

    CptS 223 Advanced Data Structures Larry Holder School of Electrical Engineering and Computer Science Washington State University

    Minimum Spanning Trees


    Find a minimum-cost set of edges that connect all vertices of a graph Applications
    Connecting nodes with a minimum of wire
    Networking Circuit design

    Collecting nearby nodes


    Clustering, taxonomy construction

    Approximating graphs
    Most graph algorithms are faster on trees
    2

    Minimum Spanning Tree


    A tree is an acyclic, undirected, connected graph A spanning tree of a graph is a tree containing all vertices from the graph A minimum spanning tree is a spanning tree, where the sum of the weights on the trees edges are minimal
    3

    Minimum Spanning Tree


    Graph:

    MST:

    Minimum Spanning Tree


    Problem
    Given an undirected, weighted graph G=(V,E) with weights w(u,v) for each (u,v)E Find an acyclic, connected graph G=(V,E), E E, that minimizes (u,v)E w(u,v) G is a minimum spanning tree
    There can be more than one
    5

    Minimum Spanning Tree


    Solution #1
    Start with an empty tree T While T is not a spanning tree
    Find the lowest-weight edge that connects a vertex in T to a vertex not in T Add this edge to T

    T will be a minimum spanning tree Called Prims algorithm (1957)


    6

    Prims Algorithm: Example

    Prims Algorithm
    Similar to Dijkstras shortestpath algorithm Except
    v.known = v in T v.dist = weight of lowest-weight edge connecting v to a known vertex in T v.path = last neighboring vertex changing (lowering) vs dist value (same as before)
    8

    Prims Algorithm

    Running time same as Dijkstra: O(|E| log |V|) using binary heaps.

    Prims Algorithm: Example

    10

    Prims Algorithm: Example

    11

    Minimum Spanning Tree


    Solution #2
    Start with T = V (no edges) For each edge in increasing order by weight
    If adding edge to T does not create a cycle Then add edge to T

    T will be a minimum spanning tree Called Kruskals algorithm (1956)


    12

    Kruskals Algorithm: Example

    13

    Kruskals Algorithm
    Uses Disjoint Set and Priority Queue data structures.

    14

    Kruskals Algorithm: Analysis


    Worst case: O(|E| log |E|) Since |E| = O(|V|2), worst case also O(|E| log |V|)
    Running time dominated by heap operations

    Typically terminates before considering all edges, so faster in practice


    15

    Minimum Spanning Tree: Applications


    Feature extraction from remote sensing images (e.g., roads, rivers, etc.) Cosmological structure formation Cancer imaging
    Arrangement of cells in the epithelium (tissue surrounding organs)

    Approximate solution to traveling salesman problem Most of above use Euclidian MST I.e., weights are Euclidean distances between vertices
    16

    Minimum Spanning Trees: Summary


    Finding set of edges that minimally connect all vertices Fast algorithm with many important applications Utilizes advanced data structures to achieve fast performance

    17

    You might also like