IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Est ce que quelqu'un a travaillé sur les graphes ?


Sujet :

Algorithmes et structures de données

  1. #1
    Membre habitué Avatar de condor_01
    Étudiant
    Inscrit en
    Avril 2006
    Messages
    294
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2006
    Messages : 294
    Points : 133
    Points
    133
    Par défaut Est ce que quelqu'un a travaillé sur les graphes ?
    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.

  2. #2
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut
    Citation Envoyé par condor_01 Voir le message
    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 ?
    Je ne répondrai à aucune question technique en privé

  3. #3
    Membre habitué Avatar de condor_01
    Étudiant
    Inscrit en
    Avril 2006
    Messages
    294
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2006
    Messages : 294
    Points : 133
    Points
    133
    Par défaut
    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.

  4. #4
    Membre confirmé Avatar de rvfranck
    Profil pro
    Étudiant
    Inscrit en
    Novembre 2004
    Messages
    746
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Novembre 2004
    Messages : 746
    Points : 534
    Points
    534
    Par défaut
    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

  5. #5
    Membre éprouvé Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 53

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Points : 1 213
    Points
    1 213
    Par défaut
    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

  6. #6
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    Par défaut
    Citation Envoyé par Nemerle Voir le message
    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.
    "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

  7. #7
    Membre éprouvé Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 53

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Points : 1 213
    Points
    1 213
    Par défaut
    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

  8. #8
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    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.

  9. #9
    En attente de confirmation mail
    Étudiant
    Inscrit en
    Août 2007
    Messages
    419
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2007
    Messages : 419
    Points : 263
    Points
    263
    Par défaut
    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

  10. #10
    Membre confirmé Avatar de rvfranck
    Profil pro
    Étudiant
    Inscrit en
    Novembre 2004
    Messages
    746
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Novembre 2004
    Messages : 746
    Points : 534
    Points
    534
    Par défaut
    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

    Citation Envoyé par acacia Voir le message
    Bonjour,

    empiler le numéro d'un noeud dans p

    tant qu'il y a un noeud dans la pile faire

    n <-- depiler p
    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

  11. #11
    En attente de confirmation mail
    Étudiant
    Inscrit en
    Août 2007
    Messages
    419
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2007
    Messages : 419
    Points : 263
    Points
    263
    Par défaut
    Citation Envoyé par rvfranck Voir le message
    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ù?
    la boucle tant que se termine à n noeud c'est à dire quand tout les noeuds du graphes ont été empilés

  12. #12
    Membre confirmé Avatar de rvfranck
    Profil pro
    Étudiant
    Inscrit en
    Novembre 2004
    Messages
    746
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Novembre 2004
    Messages : 746
    Points : 534
    Points
    534
    Par défaut

    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
    ici?
    "Celui qui reconnaît consciemment ses limites est le plus proche de la perfection." Johann Wolfgang

  13. #13
    En attente de confirmation mail
    Étudiant
    Inscrit en
    Août 2007
    Messages
    419
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2007
    Messages : 419
    Points : 263
    Points
    263
    Par défaut
    Citation Envoyé par rvfranck Voir le message
    ici?
    oui, d'après l'idée de l'algorithme

  14. #14
    Membre habitué Avatar de condor_01
    Étudiant
    Inscrit en
    Avril 2006
    Messages
    294
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2006
    Messages : 294
    Points : 133
    Points
    133
    Par défaut
    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.

  15. #15
    En attente de confirmation mail
    Étudiant
    Inscrit en
    Août 2007
    Messages
    419
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2007
    Messages : 419
    Points : 263
    Points
    263
    Par défaut
    Citation Envoyé par condor_01 Voir le message
    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é.
    Bon courage

  16. #16
    En attente de confirmation mail
    Étudiant
    Inscrit en
    Août 2007
    Messages
    419
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2007
    Messages : 419
    Points : 263
    Points
    263
    Par défaut
    Citation Envoyé par condor_01 Voir le message
    J'ai une autre petite question
    Comment peut on générer aléatoirement un graphe non orienté connexe.
    Càd qu'on spécifie le nombre de noeuds et notre programme génère un graphe connexe.
    le programme ne sait rien en cette représentation graphique du graphe, c'est à dire que tout se fait avec les matrices et les vecteurs

  17. #17
    Membre habitué Avatar de condor_01
    Étudiant
    Inscrit en
    Avril 2006
    Messages
    294
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2006
    Messages : 294
    Points : 133
    Points
    133
    Par défaut
    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.

  18. #18
    En attente de confirmation mail
    Étudiant
    Inscrit en
    Août 2007
    Messages
    419
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2007
    Messages : 419
    Points : 263
    Points
    263
    Par défaut
    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

  19. #19
    Membre habitué Avatar de condor_01
    Étudiant
    Inscrit en
    Avril 2006
    Messages
    294
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2006
    Messages : 294
    Points : 133
    Points
    133
    Par défaut
    Citation Envoyé par acacia Voir le message
    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.

  20. #20
    En attente de confirmation mail
    Étudiant
    Inscrit en
    Août 2007
    Messages
    419
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2007
    Messages : 419
    Points : 263
    Points
    263
    Par défaut
    Citation Envoyé par condor_01 Voir le message
    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
    oui ça, c'est ce que tu veux faire

    exemple tu entre n=5 (5 noeuds)

    et ton programme te génère un graphe connexe de 5 noeuds

    c'est bien ça?

    et c'est quoi la question?

+ Répondre à la discussion
Cette discussion est résolue.
Page 1 sur 3 123 DernièreDernière

Discussions similaires

  1. Réponses: 11
    Dernier message: 16/02/2015, 17h32
  2. Réponses: 4
    Dernier message: 01/02/2007, 21h55
  3. [MySQL] Probleme de requete est ce que quelqu"un pourrait m'aider
    Par sephirothmana dans le forum PHP & Base de données
    Réponses: 7
    Dernier message: 20/06/2006, 18h39
  4. est ce que postgresql peut s'installer sur un FAT32 ??
    Par mehdi_swatch dans le forum PostgreSQL
    Réponses: 1
    Dernier message: 31/03/2006, 10h57
  5. Est ce que cette ram peut aller sur mon pc?
    Par Death83 dans le forum Composants
    Réponses: 3
    Dernier message: 29/09/2005, 12h58

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo