ALGORITHME KRUSKAL - PRODUIT DE MATRICE [Résolu]

Signaler
Messages postés
3
Date d'inscription
vendredi 26 mars 2021
Statut
Membre
Dernière intervention
27 mars 2021
-
Messages postés
15040
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
10 avril 2021
-
Bonjour,
Je suis étudiante et dans le cadre d'un projet d'informatique je dois implémenter l'abre couvrant minimal de Kruskal. Mais dans les questions préliminaires je dois calculer le produit de deux matrices représentant 2 graphes. J'ai une erreur d'index que je n'arrive pas a resoudre.
Quelqu'un pourrait m'aider s'il vous plaît?

Merci d'avance

5 réponses

Messages postés
15040
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
10 avril 2021
827
bonjour,
si je comprends bien, tu as créé un programme qui donne un message d'erreur ou ne donne pas le résultat attendu.
peux-tu partager ce programme?
merci de tenir compte de ceci: https://codes-sources.commentcamarche.net/faq/11288-les-balises-de-code
Messages postés
3
Date d'inscription
vendredi 26 mars 2021
Statut
Membre
Dernière intervention
27 mars 2021

Bonjour,
Oui je peux vous joindre mon code.

class Arete:
    def __init__(self, initial, final, cout):
        self.sommet_initial=initial
        self.sommet_final=final
        self.cout_arrete=cout
def saisie_arete():
    print("Veuillez saisir une arrête: ")
    si=int(input("Sommet initial: "))
    sf=int(input("Sommet final: "))
    cout=float(input("Cout: "))
    a = Arete (si,sf,cout)
    return a
class Graphe:
    def __init__(self,nbsommets,listearetes):
        self.nbsommets=nbsommets
        self.listearetes=listearetes
def saisie_graphe():
    listearetes=[]
    nbsommets=int(input("Nombre de sommets: "))
    nbaretes=int(input("Nombre d'aretes: "))
    for i in range(0, nbaretes):
        arete =[]
        print("Saisissez l'arete numero ", i+1)
        a=saisie_arete()
        arete.append(a.sommet_initial)
        arete.append(a.sommet_final)
        arete.append(a.cout_arrete)
        listearetes.append(arete)
    g = Graphe (nbsommets,listearetes)
    return g
def adjacence(g):
    mat = [[0 for i in range(g.nbsommets)]for i in range(g.nbsommets)]
    for i in range(len(g.listearetes)):
        mat[g.listearetes[i][0]][g.listearetes[i][1]] = g.listearetes[i][2]
        mat[g.listearetes[i][1]][g.listearetes[i][0]] = g.listearetes[i][2]
    return mat
g = saisie_graphe()
h= saisie_graphe()
print (adjacence(g))
print(adjacence(h))

M1=np.array(adjacence(g))
M2=np.array(adjacence(h))
def produit(M1,M2):
    M3=[0][0]
    if len(M1)==len(M1[0])==len(M2)==len(M2[0]):
        np.dot(M1,M2)
    else:
        print("Erreur de dimensions")
    return M3


1 Construction d'un graphe et de sa matrice d'adjacence
a) Ecrire une fonction qui permet de construire une arête à partir d'informations saisies au clavier def saisie_arete()
b) En déduire une fonction qui permet de construire un graphe à partir d'informations saisies au clavier def saisie_graphe()
c) Ecrire une fonction qui prend en entrée un graphe et qui renvoie sa matrice d'adjacence def adjacence(g)
d) Ecrire une fonction qui prend en entrée une matrice d'adjacence et qui l'affiche sous sa forme matricielle (affichage ligne par ligne) def affichermatrice(matrice)

Ecrire un programme principal permettant de tester les fonctions ci dessus

2 – Calcul de la puissance d'une matrice
a) Ecrire une fonction qui prend en entrée deux matrices M1 et M2 de réels et qui renvoie la matrice M1*M2 (ps : M1 et M2 sont supposées être des matrices carrées de mêmes dimensions) def produit (M1, M2)
b) Ecrire une fonction qui prend en entrée une matrice M et un entier n et qui renvoie la matrice Mn =M*M*...M def puissance (M, n)
c) En déduire une fonction qui prend en entrée une matrice M, un entier n, deux sommets i et j puis qui renvoie le nombre de chemins de longueur n entre i et j. def nbchemins( M, n, i, j)

Ecrire un programme principal permettant de tester les fonctions ci dessus

Voici le début de la partie commune aux sujets du projet. J'ai essayé de faire le début, jusqu'à la question 2 a).

Merci beaucoup.
Messages postés
15040
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
10 avril 2021
827
le programme se comporte bien?
as-tu une question?
Messages postés
3
Date d'inscription
vendredi 26 mars 2021
Statut
Membre
Dernière intervention
27 mars 2021
>
Messages postés
15040
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
10 avril 2021

Oui du coup, tout marche jusqu'à la fonction sur le produit matriciel, ou ca me donne une erreur " OUT OF RANGE"
Messages postés
15040
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
10 avril 2021
827 >
Messages postés
3
Date d'inscription
vendredi 26 mars 2021
Statut
Membre
Dernière intervention
27 mars 2021

as-tu expliqué quelles réponses donner pour obtenir l'erreur?
ne penses-tu pas qu'il serait préférable de partager un programme qui ne pose pas de question?
Messages postés
29703
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
8 avril 2021
7 066
Bonjour,

Vu que tu utilises numpy, pourquoi n'utilise-tu pas directement le produit matriciel de numpy ?
Sinon comme le dit yg_be, quand tu partages ton code le mieux serait d'enlever la partie interactive et de hardcoder les paramètres qui lèvent le problème.

Bonne chance
Bonjour, finalement j'ai réussi à faire la question avec un autre programme, qui fonctionne bien normalement.

def produit(M1, M2):
  M3 = []
  if len(M1[0]) != len(M2):
    print("Erreur de dimension")
    return False
  for i in range(len(M1)):
    ligne = []
    for j in range(len(M2[0])):
      element = 0
      for k in range(len(M1[0])):
        element = element + M1[i][k] * M2[k][j]
      ligne.append(element)
    M3.append(ligne)
  return M3
print("M1*M2 = ",produit(M1,M2))
Messages postés
29703
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
8 avril 2021
7 066
Pense bien à sélectionner le bout de code à mettre en forme avant de cliquer sur le bouton des balises de code, de sorte à ce que le code soit encadré par les balises insérées.

Sinon plus simplement :

import numpy as np
def produit(M1, M2):
  return np.matmul(M1, M2)


Est-ce que ton problème est résolu ?

Bonne chance
J'ai résussi à résoudre le problème.
Je vous remercie pour votre aide.
Messages postés
15040
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
10 avril 2021
827
peux-tu alors marquer la discussion comme résolue?