Solutions au TD 5

Exercices 1-2, 5 : GrapheVille.java

Exercice 3 : ArcComparator.java

Exercice 4 : UnionFind.java

Exercices 5-8 : SpanningTree.java

Exercice 9 :
C'est un arbre si et seulement si au moins deux des propriétés suivantes sont vraies :

  1. il n'y a pas de cycle,
  2. il y a une seule composante connexe,
  3. nbSommets == nbArcs+1 (mais attention au cas nbArcs == 0).
et la troisième est alors vraie aussi.
L'absence de cycle peut se tester facilement à l'aide d'union-find. Une alternative serait de construire un graphe (non orienté) et de lancer une recherche de cycle adaptée au cas non orienté mais, attention, il y a plusieurs pièges.
L'unicité de la composante connexe se teste aussi facilement à l'aide d'union-find : tous les sommets ont la même racine ou, de manière équivalente, il y a un seul sommet qui est sa propre racine.