Test de connexité sur une matrice d'adjacence d'un graphe
condor_02
Messages postés
1
Date d'inscription
mercredi 12 septembre 2007
Statut
Membre
Dernière intervention
11 octobre 2007
-
11 oct. 2007 à 18:49
The_Guardian Messages postés 317 Date d'inscription vendredi 25 mai 2007 Statut Membre Dernière intervention 19 octobre 2007 - 12 oct. 2007 à 15:08
The_Guardian Messages postés 317 Date d'inscription vendredi 25 mai 2007 Statut Membre Dernière intervention 19 octobre 2007 - 12 oct. 2007 à 15:08
A voir également:
- Matrice d adjacence
- Matrice diagonale ✓ - Forum C
- Rang d'une matrice - Forum C
- Matrice adjacente - Forum Visual Basic 6
- Matrice échelonnée - Forum C
- Matrice de rotation - Forum C / C++ / C++.NET
1 réponse
The_Guardian
Messages postés
317
Date d'inscription
vendredi 25 mai 2007
Statut
Membre
Dernière intervention
19 octobre 2007
1
12 oct. 2007 à 15:08
12 oct. 2007 à 15:08
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
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
