Discussion :

[condor_01]

Bonjour,
Est ce qu'il y'a quelqu'un parmi vous qui a travaillé sur les problèmes de graphe avant?
J'essaie de faire un programme pour tester la connexité d'un graphe non orienté à partir de sa matrice d'adjacence.
Sauriez vous m'aider
Merci

[millie]

Bonjour,
Est ce qu'il y'a quelqu'un parmi vous qui a travaillé sur les problèmes de graphe avant?
J'essaie de faire un programme pour tester la connexité d'un graphe non orienté à partir de sa matrice d'adjacence.
Sauriez vous m'aider
Merci

N'est-ce pas plutôt un problème d'algorithmique ?
A quel endroit coinces tu ?

[condor_01]

J'ai déjà fait un programme qui remplit une matrice d'adjacence à partir de 2 fichiers texte qui sépcifient les coordonnées et le voisinage de chaque noeud
Mais je me suis bloqué sur la partie : test de connexité.
Je veux tester la connexité en me basant sur la matrice d'adjacence.
Merci

[rvfranck]

Salut,

As tu vérifié s'il n'existe pas déjà des algos qui teste la connexité d'un graphe non orienté?
Je ne sais plus trop où, et si celà est vrai, mais je crois avoir lu qu'après de légères modifications sur Kruskal ou Dijkstra (je ne sais plus trop) on pouvait vérifier cela.

Cherche de ce côté là. a+

[Nemerle]

Il y a un thread... 7 lignes en dessous du tien http://www.developpez.net/forums/sho...d.php?t=423641

[Trap D]

Il y a un thread... 7 lignes en dessous du tien http://www.developpez.net/forums/sho...d.php?t=423641

Effectivement, généré par le même P.O.

[acacia]

Salut!

Je te laisse en déduire un algo qui te permettent de déterminer si un graphe non orienté est connexe, mais même si un graphe orienté l'est bien.

un graphe orienté n'est pas toujours connexe.

[Jedai]

un graphe orienté n'est pas toujours connexe.

Ce n'est pas ce qu'il a dit, il a montré qu'avec une matrice d'adjacence, pourvu qu'on comprenait comment l'utiliser, il était trivial de montrer la connexité (ou non) d'un graphe donné, qu'il soit orienté ou non.

--
Jedaï

[acacia]

Ce n'est pas ce qu'il a dit, il a montré qu'avec une matrice d'adjacence, pourvu qu'on comprenait comment l'utiliser, il était trivial de montrer la connexité (ou non) d'un graphe donné, qu'il soit orienté ou non.

--
Jedaï

j'ai mal compris

[condor_01]

Je veux un algorithme qui:
- en entrée prend le nombre de noeuds
- en sortie me donne la matrice d'adjacence d'un graphe non orienté connexe.
Ce graphe sera généré d'une manière aléatoire.

J'ai pensé à ça:
On part d'un point A de coordonnés(0,0,0)
On ajoute un autre point distance aléatoire
puis on choisit aléatoirement un point parmi ces 2 points et on le lie à un troisième point
Et ainsi de suite jusqu'à atteindre le nombre de noeuds souhaité

[acacia]

Je veux un algorithme qui:
- en entrée prend le nombre de noeuds
- en sortie me donne la matrice d'adjacence d'un graphe non orienté connexe.
Ce graphe sera généré d'une manière aléatoire.

J'ai pensé à ça:
On part d'un point A de coordonnés(0,0,0)
On ajoute un autre point distance aléatoire
puis on choisit aléatoirement un point parmi ces 2 points et on le lie à un troisième point
Et ainsi de suite jusqu'à atteindre le nombre de noeuds souhaité

salut!

j'ai bien compris ce que tu veux faire

c'est justement la connexité qui pose problème

le programme pourra te construire aléatoirement un seul chemin

A-> B -> C -> D ............-> N

et te dire que c'est un graphe connexe