[10/10][AIDE] Exos Graphes algos
J'ai été 410 into ban
Les culs pour vous motiver, vous pouvez Up le topic si vous voulez.
Concevoir un algorithme qui, étant donné un graphe orienté G et un sommet v de G, calcule le degré entrant de v.
Idem pour le degré sortant
Je connais la définition mais je sais pas l'implémenter dans un algorithme...
Il suffit de calculer la somme de la colonne du sommet v. Mais je comprends pas pourquoi on prend la colonne ?
Mais bordel le pire c'est que j'étais en train de te répondre
DU COUP
Est-ce que tu sais que les prédécesseurs d'un sommet, on peut les avoir en regardant les colonnes de la matrice d'adjacence ??
Le 09 février 2021 à 18:47:37 Moulusk a écrit :
Mais bordel le pire c'est que j'étais en train de te répondreDU COUP
Est-ce que tu sais que les prédécesseurs d'un sommet, on peut les avoir en regardant les colonnes de la matrice d'adjacence ??
Non je savais pas, tu viens de me l'apprendre !
Dans mon cours on nous dit juste :
M[i][j] = 1 ssi (i,j) est un arc (arête) de G
Le 09 février 2021 à 18:50:31 EncoreBanni482 a écrit :
Dans mon cours on nous dit juste :M[i][j] = 1 ssi (i,j) est un arc (arête) de G
Oui c'est ça, ça veut globalement dire que le sommet de la LIGNE "i" pointe vers le sommet de la COLONNE "j"
Le 09 février 2021 à 18:50:51 Moulusk a écrit :
J'arrive pas à trouver de bon exemples sur internet, du coup est-ce que tu penses pouvoir faire ton algo en ayant compris ça ??
Fonction degreEntrant(G : Matrice, n : entier, v : Sommet)
deg <- 0
Pour i de 0 à n-1
Si v = c
deg <- deg +1
Retourner deg
deg : degré
c : colonne
Tout simplement ça du coup ?
Le 09 février 2021 à 18:51:33 REVillage a écrit :
l'op t'es au lycée ?
Non du tout, pourquoi ?
Le 09 février 2021 à 18:51:46 Moulusk a écrit :
Le 09 février 2021 à 18:50:31 EncoreBanni482 a écrit :
Dans mon cours on nous dit juste :M[i][j] = 1 ssi (i,j) est un arc (arête) de G
Oui c'est ça, ça veut globalement dire que le sommet de la LIGNE "i" pointe vers le sommet de la COLONNE "j"
Ah bah mon algo est bon du coup ? !
Le 09 février 2021 à 18:55:10 Moulusk a écrit :
C'est pour faire quoi la variable "n" ??
La taille de la matrice G,
On parcout la matrice G quoi
Avec la matrice d'adjacence l'exo est trivial.
Ce que j'avais fais en php :
def predecesseurs(M: list, x: int) -> list:
result = []
for i in range(np.shape(M)[0]):
if M[i][x] == 1:
result.append(i)
return result
Il faudrait juste que tu passes ça mais avec un seul entier je suppose, puisque ton exo a pas l'air d'attendre un tableau de degré sortant
Le 09 février 2021 à 18:56:40 CauchySchwartz a écrit :
T'es en L1 l'auteur ?
Avec la matrice d'adjacence l'exo est trivial.
Oui je pense avoir compris comment faire désormais
Données du topic
- Auteur
- EncoreBanni482
- Date de création
- 9 février 2021 à 18:45:50
- Nb. messages archivés
- 22
- Nb. messages JVC
- 22