Pseudo Code

Leçon 4 sur 9 du cours Algorithme de Prim - Algorithmes de graphes de Coddy.

prim(n, edges):
   inTree[0] = true; tout le reste à false
   total = 0
   répéter (n - 1) fois :
      best = l'arête traversante (une extrémité dedans, une dehors) avec le poids le plus faible
      if none exists: stop      # déconnecté
      total += best.weight
      inTree[best.outsideEndpoint] = true
   return total

Une arête (u, v, w) traverse la coupe quand inTree[u] et inTree[v] diffèrent.
Parcourir toutes les arêtes à chaque tour pour trouver l'arête traversante la moins chère permet de garder le code simple (aucune file de priorité n'est nécessaire pour les petits graphes).

Essayez vous-même

Cette leçon ne comprend pas de défi de code.

Testez-vous

Cette leçon comprend un petit quiz. Commencez la leçon pour y répondre et suivre votre progression.

Toutes les leçons de Algorithme de Prim - Algorithmes de graphes

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