Pseudo Code

Lição 4 de 9 do curso Algoritmo de Prim - Algoritmos de Grafos da Coddy.

prim(n, edges):
   inTree[0] = true; todo o resto falso
   total = 0
   repeat (n - 1) times:
      best = a aresta de corte (uma extremidade dentro, uma fora) com o menor peso
      if none exists: stop      # desconectado
      total += best.weight
      inTree[best.outsideEndpoint] = true
   return total

Uma aresta (u, v, w) cruza o corte quando inTree[u] e inTree[v] são diferentes.
Escanear todas as arestas a cada rodada para encontrar a aresta de corte mais barata mantém o código simples (nenhuma fila de prioridade é necessária para grafos pequenos).

Experimente você mesmo

Esta lição não inclui um desafio de código.

Teste seus conhecimentos

Esta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.

Todas as lições de Algoritmo de Prim - Algoritmos de Grafos

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2