Test de connexité sur une matrice d'adjacence d'un graphe

Signaler
Messages postés
1
Date d'inscription
mercredi 12 septembre 2007
Statut
Membre
Dernière intervention
11 octobre 2007
-
Messages postés
317
Date d'inscription
vendredi 25 mai 2007
Statut
Membre
Dernière intervention
19 octobre 2007
-
Bonjour,
Est ce que je peux trouver un programme en C qui teste la connexité d'un graphe à partir de sa matrice d'adjacence.
Je suis un peu pressé par le temps et ce test fait partie d'un programme que je suis en train d'élaborer.
Merci

1 réponse

Messages postés
317
Date d'inscription
vendredi 25 mai 2007
Statut
Membre
Dernière intervention
19 octobre 2007

Bonjour,


Je ne peux pas te donner un programme tout fait,  je préfère te montrer comment on pêche et en plus c'est vendredi c'est la journée du poisson :p
Donc pour tester la (forte) connexité de ton graphe avec ta matrice, tu pars d'une matrice NxN disons, avec des 0 quand il n'y a pas d'arête et 1 quand il y en a.
(1) tu construis un vecteur de N éléments qui valent tous 0
(2) tu prends un noeud arbitrairement, par exemple le noeud d'indice 0
_ et tu mets 1 dans la case v[0]
(3) tu mets aussi le numéro du noeud, donc 0, dans une pile p
(4) tantque la pile est pas vide faire
  n <-- depiler p
v[n] = 1
 pour i de 0 a N faire
si M[n,i]==1 alors
     si v[i]==0 alors
 empiler i dans p
         v[i] = 1
    finsi
   finsi
 finpour
5) tu parcours ton vecteur v, si y'a un seul noeud qui est à 0, ton graphe est pas connexe
sinon il l'est

=

Une autruche ne se cuit pas aux petits lardons