Please enable JavaScript.
Coggle requires JavaScript to display documents.
M14 - Algorithms and Data Structures - Coggle Diagram
M14 - Algorithms and Data Structures
9 Greedy Technique
9.1 Prim’s Algorithm
given n points, connect them in the cheapest possible way so that there will be a path between every pair of points.
DEFINITION
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
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.
The algorithm stops after all the graph’s vertices have been included in the tree being constructed
How efficient is Prim’s algorithm?
if a graph is represented by its weight matrix and the priority queue is implemented as an unordered array, the algorithm’s running time will be in
Θ(|V|²)
If a graph is represented by its adjacency lists and the priority queue is implemented as a min-heap, the running time of the algorithm is in
O(|E| log |V|)
9.2 Kruskal’s Algorithm
Disjoint Subsets and Union-Find Algorithms
Disjoint subsets: quick-find
find ∈ Θ(1)
union ∈ Θ(n)
Array: representative element for each subset elements
Each subset implement as a linked list
Optimisation (union by size): append shortest list to the largest one
Disjoint subsets: quick-union
Using a parent pointer tree: root is the representative element
find ∈ Θ(n)
union ∈ Θ(1)
Optimisation (union by size/rank): link smallest tree to the largest one
The size of a tree can be measured either by the number of nodes (this version is called
union by size
) or by its height (this version is called
union by rank
).
Size: number of nodes
Rank: subtree height
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
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.
with an efficient sorting algorithm, the time efficiency of Kruskal’s algorithm will be in
O(|E| log |E|).
Prim: best for dense graphs
Kruskal: best for sparse graphs
A
Minimum Spanning Tree (MST)
é um subgrafo de um grafo conexo e ponderado que conecta todos os vértices com o menor custo total possível, sem formar ciclos. Em outras palavras, a MST inclui todos os vértices do grafo original, mas com o mínimo de arestas necessárias para garantir que o grafo permaneça conectado e o peso total das arestas seja o menor possível.
Propriedades do MST
Conexidade
: A MST conecta todos os vértices do grafo.
Arestas
: O número de arestas na MST é sempre V - 1, onde V é o número de vértices no grafo
Peso Mínimo
: A soma dos pesos das arestas na MST é mínima em comparação a qualquer outro subgrafo que conecte todos os vértices.
Aplicações do MST
Redes de Computadores:
Construção de redes de comunicação eficientes.
Distribuição de Energia:
Planejamento de redes de distribuição de energia com custos mínimos.
Design de Circuitos:
Redução do comprimento total dos fios usados.
Problemas de Roteamento:
Otimização de rotas para minimizar custos de transporte ou tempo.
Algoritmos para Encontrar MST
Algoritmo de Kruskal:
Funciona escolhendo as arestas de menor peso e adicionando-as à árvore, desde que não formem um ciclo.
Utiliza a estrutura de dados Union-Find para ajudar na verificação de ciclos.
Algoritmo de Prim:
Começa com um único vértice e adiciona arestas de menor peso, expandindo a árvore até incluir todos os vértices.
Utiliza uma fila de prioridade (geralmente implementada com um heap) para selecionar a próxima aresta de menor peso.