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
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
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+
Il y a un thread... 7 lignes en dessous du tien http://www.developpez.net/forums/sho...d.php?t=423641
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
Ah non. Ce n'est pas exactement le meme PO, sinon j'aurais utilisé mes super-pouvoirs pour fusionner les 2 posts.
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ù?
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
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é.
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.
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
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