Parcours d'un graphe - Java

Required Files: Graphe.java, maison.txt, Executable.java (Download)
Maximum number of files: 8
Type of work: Individual work

On vous propose une implémentation de la classe Graphe.java. Cet exercice a comme objectif d'implémenter des parcours de graphes et de les utiliser. Attention à bien conserver l’ordre des sommets dans vos réponses pour permettre l’évaluation automatique de votre solution.

Question 1 – Implémentez la fonction public int[] BFS(int racine) qui fait un parcours en largeur du graphe et renvoie un tableau des distances de chaque sommet à la racine. Vous pouvez utiliser la fonction public List<Integer> voisins(int v). La distance d'un sommet non atteignable est par convention à -1.

Question 2 – En vous basant sur la méthode BFS, implémentez la fonction public int nbComposantes()qui renvoie le nombre de composantes connexes du graphe. 

Question 3 – Implémentez une fonction DFS qui fait un parcours en profondeur du graphe à partir d'une sommet racine. Cette fonction n'est pas évaluée. Vous devez donc proposer vos propres tests pour vérifier qu'elle fonctionne correctement. Vous pouvez par exemple vérifier qu'en changeant l'algorithme de parcours dans la fonction qui calcule le nombre de composantes connexe, les tests passent toujours.

Requested files

Graphe.java

Loading

maison.txt

Loading

Executable.java

Loading