algorithmique (école d'ingénieur) · Chapitre 7 · Exercice de TD
Afficher un graphe
Graphes sans circuit et ordonnancement de projets · niveau 1 (application)
Énoncé
Un réseau de bus dessert villes ; il est représenté par le tableau de listes d'arcs Liste[] G avec , , , et .
- Écrire les instructions Java qui construisent ce graphe.
- Écrire une fonction
void afficher(Liste[] G)qui affiche le graphe sous la forme ci-dessous (une ligne par sommet, suivie de ses successeurs).
0 : 1 3 4
1 : 2 4
2 : 3 4
3 : 4
4 :Corrigé
Les listes se construisent de la fin vers le début :
Liste[] G = new Liste[5]; // cinq listes vides (null)
G[0] = new Liste(1, new Liste(3, new Liste(4, null)));
G[1] = new Liste(2, new Liste(4, null));
G[2] = new Liste(3, new Liste(4, null));
G[3] = new Liste(4, null);
static void afficher(Liste[] G) {
for (int i = 0; i < G.length; i++) { // pour chaque sommet i
System.out.print(i + " :");
for (Liste l = G[i]; !vide(l); l = reste(l))
System.out.print(" " + premier(l)); // les successeurs de i
System.out.println();
}
}Chaque sommet et chaque arc est touché une fois : l'affichage est en .
100 % gratuit
La suite du chapitre est sur Adloun
- 11 autres exercices corrigés dans ce chapitre
- Les 2 QCM du chapitre, le premier sans compte
- Le podcast et la vidéo du chapitre : 2 minutes d'écoute sans compte
- Le tuteur, qui guide pas à pas sans donner la réponse
Sans compte : le cours, le premier QCM et 2 minutes de podcast et de vidéo. Exercices et tuteur : inscription gratuite en 30 secondes, sans carte bancaire.