ALGORITHME KRUSKAL - PRODUIT DE MATRICE Résolu/Fermé

Question

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

yg_be · Answer

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

yasminelk · Answer

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.

mamiemando · Answer

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

yasminelk · Answer

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))

yasminelk · Answer

J'ai résussi à résoudre le problème.
Je vous remercie pour votre aide.

ALGORITHME KRUSKAL - PRODUIT DE MATRICE

5 réponses

Discussions similaires