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 :
- il n'y a pas de cycle,
- il y a une seule composante connexe,
- 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.