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
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
The great glory is not in never falling but in rising every time we fall.
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
The great glory is not in never falling but in rising every time we fall.
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+
"Celui qui reconnaît consciemment ses limites est le plus proche de la perfection." Johann Wolfgang
Il y a un thread... 7 lignes en dessous du tien http://www.developpez.net/forums/sho...d.php?t=423641
Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre
"La haine seule fait des choix" - Koan Zen
"Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
"Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
Faites du Prolog, ça vous changera les idées !
Ma page Prolog
Mes codes sources commentés
Mon avatar : La Madeleine à la veilleuse de Georges de La Tour
j'avais pas vu! C'est pas très bien monsieur Condor de laisser un thread vierge de tout retour pour en récréer un autre
Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre
Ah non. Ce n'est pas exactement le meme PO, sinon j'aurais utilisé mes super-pouvoirs pour fusionner les 2 posts.
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
Bonjour,
pour tester la conexité dans un graphe non orienté on commence par représenter le graphe par une matrice d'adjacence n*n où n est le nombre de noeuds et noter 1 là ou il y a une arrête, 0 ou il y en a pas.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 une pile p pour empiler et depiler les numéro des noeuds un vecteur v d'indice i initialisé à 0 empiler le numéro d'un noeud dans p tant qu'il y a un noeud dans la pile faire n <-- depiler p v[n] = 1 pour i allant de 0 à n faire si m[n,i]==1 alors si v[i]==0 alors empiler i dans p v[i] = 1 fin si fin si fin pour pour i allant de 0 à n faire lire v[i] si v[i] == 0 alors le graphe n'est pas connexe sinon le graphe est connexe
Salut et merci,
Moi aussi je suis intéressé. On a donc:
Matrice m[1..n 1..n] avec :
m[i,j] = 1 si du noeud i au noeud j il y'a une arete
sinon m[i,j]=0
V: vecteur initialisé à 0
après l'algo v[i] = 1 si le noeud i est relié à tous les autres noeuds
sinon v[i] = 0
On empile n'importe quel noeud? La boucle tant que se termine où?
"Celui qui reconnaît consciemment ses limites est le plus proche de la perfection." Johann Wolfgang
ici?
tant qu'il y a un noeud dans la pile faire
n <-- depiler p
v[n] = 1
pour i allant de 0 à n faire
si m[n,i]==1 alors
si v[i]==0 alors
empiler i dans p
v[i] = 1
fin si
fin si
fin pour
fin tant que
"Celui qui reconnaît consciemment ses limites est le plus proche de la perfection." Johann Wolfgang
Bonjour
Je suis désolé pour mon absence
Je vous remercie pour l'intérêt que vous avez porté à ce sujet.
Je vais commencer tout de suite à développer ce test de connexité.
J'ai déjà développé la création de la matrice d'adjacence à partir du fichier de spécification du graphe.
Et là je vais travailler sur le test de connexité.
The great glory is not in never falling but in rising every time we fall.
oui c'est ce que je veux dire
A partir du nombre de noeuds, le programme doit générer une matrice d'adjacence d'un graphe non orienté connexe.
The great glory is not in never falling but in rising every time we fall.
la matrice d'adjacence n*n et n est le nombre de noeuds
mais si tu veux tester la connexité d'un graphe c'est donc à toi d'introduire la matrice d'adjacence associée à ton graphe
Vous m'avez mal compris.
J'ai à faire 2 programmes
Le premier teste la connexité d'un graphe qui est déjà spécifié(dans un fichier texte).
Le deuxième programme doit me générer aléatoirement une matrice d'un grpahe connexe. Je donne en entrée le nombre de noeuds du graphe. Le programme tourne et me donne une matrice d'un graphe connexe.
En partant d'un point je dois générer N noeuds aléatoirement mais à condition qu'ils soient connexes
The great glory is not in never falling but in rising every time we fall.
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager