Théorie des graphes : Structure de donnees avancee en c td3 énoncés
Télécharger PDFUNIVERSITE CADI AYYAD
Facult ́e PolyDisciplinaire de Safi
Fili`ere SMI
2019−2020
Structure de donn ́ee avanc ́ee en C
(partie II)
TD 3Graphes
Exercice 1́
Ecrire un programme complet en C permettant de r ́ealiser quelques manipulations de base
sur les graphes notamment les tˆaches suivantes :
1. D ́efinir un graphe. Un graphe est repr ́esent ́e par sa matrice d’adjacences.
2. Construire un graphe `a partir d’un fichier.
3. Tester si un graphe et orient ́e ou non.
4. Donner le degr ́e d’un sommet donn ́e. Noter que dans le cas d’un graphe orient ́e, le degr ́e
d’un sommet ́egal `a la sommet des degr ́es entrants et degr ́es sortants du mˆeme sommet.
5. Donner le degr ́e maximal et minimal d’un graphe.
6. Donner le plus court chemin dans graphe (Algorithme de Floyd-Warsall).
7. Donner la distance entre deux sommets dans un graphe.
8. Donner le diam`etre d’un graphe.
Exercice 2La ville de Safi compte r ́ealiser un projet d’assainissement entre les quartiers 1 et 12.
Les coˆuts de construction sont indiqu ́es sur la figure ci-dessous. Les quartiers 1 et 2, et 7
et 11 sont d ́ej`a reli ́ees par des canaux d’assainissement et si on utilise ces canaux le coˆut
de construction est n ́egligeable. ́
Ecrire un programme qui vous permet de d ́eterminer les
quartiers interm ́ediaires pour que le coˆut de construction soit minimal.1 710 124 82 59 63 11(7) (8)(12) (0)(5) (6)(7) (4)(6) (4)(12) (5)(6) (9)(7) (8)(7) (0)(4) (8)(4) 1Mustapha KCHIKECH
UNIVERSITE CADI AYYAD
Facult ́e PolyDisciplinaire de Safi
Fili`ere SMI
2019−2020
Structure de donn ́ee avanc ́ee en C
(partie II)
Exercice 3Le tableau ci-dessous indique les connexions a ́eriennes possibles entre les villes et les temps
de vol en heures, correspondance incluse(ligne = ville de d ́epart, colonne = ville d’arriv ́ee.
Ecrire un programme qui permet de trouver le vol qui dure moins de temps entre Casa et
New York.
HambourgAmsterdamLondresBerlinEdimbourgOsloStockholmNew YorkCasa734 Hambourg11
Amsterdam218
Londres2
Berlin232
Edimbourg376Oslo2 Stockholm25
Exercice 4́
Ecrire un programme complet en C permettant de r ́ealiser quelques manipulations de base
sur les graphes notamment les tˆaches suivantes :
1. D ́efinir un graphe. Un graphe est repr ́esent ́e par un tableau de listes d’adjacences.
2. Construire un graphe `a partir d’un fichier.
3. Tester si un graphe et orient ́e ou non.
4. Donner le degr ́e d’un sommet donn ́e. Noter que dans le cas d’un graphe orient ́e, le degr ́e
d’un sommet ́egal `a la sommet des degr ́es entrants et degr ́es sortants du mˆeme sommet.
5. Donner le degr ́e maximal et minimal d’un graphe.
6. Impl ́ementer les algorithmes de parcours de graphes (Largeur et profondeur).
7. Donner le plus court chemin dans graphe (Algorithme de Dijkstra).
8. Donner la distance entre deux sommets dans un graphe.
9. Donner le diam`etre d’un graphe.
Exercice 5Traiter les probl`emes de l’exercice 2 et 3 par les graphes repr ́esent ́es par un tableau de
listes d’adjacences.
2Mustapha KCHIKECH