Discussion :

[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

[alex_pi]

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.

[millie]

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.

[sidahmed]

Bonjour,

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Cordialement,
Sidahmed.

[Nemerle]

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!!