Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim’s Algorithm - Coggle Diagram
Prim’s Algorithm
-
Kruskal’s Algorithm
Kruskal’s algorithm looks at a minimum spanning tree of a weighted connected graph G =V,E as an acyclic subgraph with |V | − 1 edges for which the sum of the edge weights is the smallest.
Consequently, the algorithm constructs a minimum spanning tree as an expanding sequence of subgraphs that are always acyclic but are not necessarily connected on the intermediate stages of the algorithm.
-
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.
Hence, with an efficient sorting algorithm, the time efficiency of Kruskal’s algorithm will be in O(|E| log |E|).
Dijkstra’s Algorithm
For graphs represented by their adjacency
lists and the priority queue implemented as a min-heap, it is in O(|E| log |V |).
-
-
spanning tree
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.
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.
-
-