Test de connexité sur graphe non orienté

Bonjour,
Je ne trouve pas de solution à mon problème.
Je souhaite faire un test de connexité sur un graphe non orienté.
Je veux savoir si à partir d'un sommet on peut atteindre tous les autres sommets.
Est ce que vous pouvez me guider un peu
Pour info: Je compte développer ça en langage C
Merci

Citation:

---

Envoyé par condor_01

Bonjour,
Je ne trouve pas de solution à mon problème.
Je souhaite faire un test de connexité sur un graphe non orienté.
Je veux savoir si à partir d'un sommet on peut atteindre tous les autres sommets.
Est ce que vous pouvez me guider un peu
Pour info: Je compte développer ça en langage C
Merci

---

Tu colories tes sommets par un parcours en profondeur ou en largeur, et tu regardes si tous tes sommets sont coloriés.

Si les parcours ne te sont pas familiers, trouve un cours d'algorithmique de base traitant des graphes.

Citation:

---

Envoyé par alex_pi

Tu colories tes sommets par un parcours en profondeur ou en largeur, et tu regardes si tous tes sommets sont coloriés.

Si les parcours ne te sont pas familiers, trouve un cours d'algorithmique de base traitant des graphes.

---

Tu pourras d'ailleurs jetter un oeil au cours suivant : http://lapoire.developpez.com/algorithmique/graphes/

Sinon, +1 avec la méthode d'alex_pi qui est la méthode standard.

Bonjour,

Citation:

---

Envoyé par condor_01

Je souhaite faire un test de connexité sur un graphe non orienté.

---

Juste une petite astuce qui te permet de gagner quelques itérations :

Code:

---

1 2 3 4 5

n : nombre de nœuds; m : nombre d'arêtes   Si (m < n - 1) alors afficher("Le graphe G n'est pas connexe");

---

La condition m >= n - 1 est une condition nécessaire mais non suffisante 8-)

Cordialement,
Sidahmed.

Citation:

---

Envoyé par condor_01

Bonjour,
Je ne trouve pas de solution à mon problème.
Je souhaite faire un test de connexité sur un graphe non orienté.
Je veux savoir si à partir d'un sommet on peut atteindre tous les autres sommets.
Est ce que vous pouvez me guider un peu
Pour info: Je compte développer ça en langage C
Merci

---

Tu vas poster combien de fois le même sujet? ;)

Mon ami, nombre de réponses données entre autre par Millie, Pseudocode,etc..; t'ont été données. Et si cela ne suffit pas, google te donne rapidement la solution. Et si google est un échec, vient vers nous avec DES TENTATIVES de solutions! ;)

Et si cela ne suffit pas, cherche "test de connexité sur un graphe orienté", en considérant que tes chemins non orientés sont des chemins oritentés dans les deux sens... ;)

Bon courage!!