Please enable JavaScript.

Coggle requires JavaScript to display documents.

M13 - Coggle Diagram

- - - - It is also helpful for constructing approximate solutions to more
        difficult problems such the traveling salesman problem
        We can represent the points given by vertices of a graph, possible connections
        by the graph’s edges, and the connection costs by the edge weights. Then the
        question can be posed as the minimum spanning tree problem, defined formally
        as follows.
        
        A spanning tree of an undirected connected graph is its connected
        acyclic subgraph (i.e., a tree) that contains all the vertices of the graph. If such a
        graph has weights assigned to its edges, a minimum spanning tree is its spanning
        tree of the smallest weight, where the weight of a tree is defined as the sum of the
        weights on all its edges. The minimum spanning tree problem is the problem of
        finding a minimum spanning tree for a given weighted connected graph.
        
        If we were to try constructing a minimum spanning tree by exhaustive search,
        we would face two serious obstacles. First, the number of spanning trees grows
        exponentially with the graph size (at least for dense graphs). Second, generating
        all spanning trees for a given graph is not easy; in fact, it is more difficult than
        finding a minimum spanning tree for a weighted graph by using one of several
        efficient algorithms available for this problem
        
        Prim’s algorithm constructs a minimum spanning tree through a sequence
        of expanding subtrees. The initial subtree in such a sequence consists of a single
        vertex selected arbitrarily from the set V of the graph’s vertices. On each iteration,
        the algorithm expands the current tree in the greedy manner by simply attaching to
        it the nearest vertex not in that tree. (By the nearest vertex, we mean a vertex not
        in the tree connected to a vertex in the tree by an edge of the smallest weight. Ties
        can be broken arbitrarily.) The algorithm stops after all the graph’s vertices have
        been included in the tree being constructed. Since the algorithm expands a tree
        by exactly one vertex on each of its iterations, the total number of such iterations
        is n − 1, where n is the number of vertices in the graph. The tree generated by the
        algorithm is obtained as the set of edges used for the tree expansions
        The nature of Prim’s algorithm makes it necessary to provide each vertex not
        in the current tree with the information about the shortest edge connecting the
        vertex to a tree vertex
- - - - The algorithm begins by sorting the graph’s edges in nondecreasing order of
        their weights. Then, starting with the empty subgraph, it scans this sorted list,
        adding the next edge on the list to the current subgraph if such an inclusion does
        not create a cycle and simply skipping the edge otherwise.
        
        The correctness of Kruskal’s algorithm can be proved by repeating the essential
        steps of the proof of Prim’s algorithm given in the previous section. The fact
        that ET is actually a tree in Prim’s algorithm but generally just an acyclic subgraph
        in Kruskal’s algorithm turns out to be an obstacle that can be overcome.
      - Applying Prim’s and Kruskal’s algorithms to the same small graph by hand
        may create the impression that the latter is simpler than the former. This impression
        is wrong because, on each of its iterations, Kruskal’s algorithm has to check
        whether the addition of the next edge to the edges already selected would create a
        cycle. It is not difficult to see that a new cycle is created if and only if the new edge
        connects two vertices already connected by a path, i.e., if and only if the two vertices
        belong to the same connected component. Note also that each
        connected component of a subgraph generated by Kruskal’s algorithm is a tree
        because it has no cycles
        
        In view of these observations, it is convenient to use a slightly different
        interpretation of Kruskal’s algorithm.We can consider the algorithm’s operations
        as a progression through a series of forests containing all the vertices of a given
        graph and some of its edges. The initial forest consists of |V | trivial trees, each
        comprising a single vertex of the graph. The final forest consists of a single tree,
        which is a minimum spanning tree of the graph. On each iteration, the algorithm
        takes the next edge (u, v) from the sorted list of the graph’s edges, finds the trees
        containing the vertices u and v, and, if these trees are not the same, unites them
        in a larger tree by adding the edge (u, v).
        
        Fortunately, there are efficient algorithms for doing so, including the crucial
        check for whether two vertices belong to the same tree. They are called unionfind
        algorithms. We discuss them in the following subsection. With an efficient
        union-find algorithm, the running time of Kruskal’s algorithm will be dominated
        by the time needed for sorting the edge weights of a given graph. Hence, with an
        efficient sorting algorithm, the time efficiency of Kruskal’s algorithm will be in
        O(|E| log |E|).
- - - - There are two principal alternatives for implementing this data structure. The
        first one, called the quick find, optimizes the time efficiency of the find operation;
        the second one, called the quick union, optimizes the union operation.
        The quick find uses an array indexed by the elements of the underlying set
        S; the array’s values indicate the representatives of the subsets containing those
        elements. Each subset is implemented as a linked list whose header contains the
        pointers to the first and last elements of the list along with the number of elements
        in the list
        
        There are two principal alternatives for implementing this data structure. The
        first one, called the quick find, optimizes the time efficiency of the find operation;
        the second one, called the quick union, optimizes the union operation.
        The quick find uses an array indexed by the elements of the underlying set
        S; the array’s values indicate the representatives of the subsets containing those
        elements. Each subset is implemented as a linked list whose header contains the
        pointers to the first and last elements of the list along with the number of elements
        in the list
        
        simple way to improve the overall efficiency of a sequence of union operations
        is to always append the shorter of the two lists to the longer one, with ties
        broken arbitrarily. Of course, the size of each list is assumed to be available by, say,
        storing the number of elements in the list’s header. This modification is called the
        union by size. Though it does not improve the worst-case efficiency of a single application
        of the union operation (it is still in (n)), the worst-case running time of
        any legitimate sequence of union-by-size operations turns out to be in O(n log n).
        The quick union—the second principal alternative for implementing disjoint
        subsets—represents each subset by a rooted tree