ALGORITHME KRUSKAL - PRODUIT DE MATRICE
Résolu
yasminelk
Messages postés
3
Date d'inscription
Statut
Membre
Dernière intervention
-
yg_be Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention -
yg_be Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention -
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
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
A voir également:
- Produit matriciel python
- Clé de produit windows 10 gratuit - Guide
- Citizen code python avis - Accueil - Outils
- Historique prix produit - Guide
- Python pix ✓ - Forum Python
- Mot secret python pix ✓ - Forum Python
5 réponses
yg_be
Messages postés
23541
Date d'inscription
Statut
Contributeur
Dernière intervention
Ambassadeur
1 584
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
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
Bonjour,
Oui je peux vous joindre mon code.
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.
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.
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
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))
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 :
Est-ce que ton problème est résolu ?
Bonne chance
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
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question