Connaître les bases est ce qui distingue les grands codeurs des intermédiaires.
En d'autres termes, un moyen simple et efficace de développer vos compétences est d'apprendre les bases de l'informatique.
Algorithme Python Pathfinder
Dans ce didacticiel, vous découvrirez l'algorithme Pathfinder qui détermine de manière récursive s'il existe un chemin direct ou indirect entre deux sommets du graphique.
Par exemple, dans le graphique, y a-t-il un chemin du sommet 4 au sommet 1 ? Qu'en est-il d'un chemin du sommet 3 au sommet 4 ?
Voici le code qui résout le problème de pathfinder en Python :
# The graph represented as adjancy matrix
# See https://en.wikipedia.org/wiki/Adjacency_matrix
G = [[1,1,0,0,0],
[0,1,0,0,0],
[0,0,1,0,0],
[0,1,1,1,0],
[1,0,0,1,1]]
n = len(G) # The number of vertices in the graph
# Is there a path from vertex i to vertex j?
def find_path(i, j, path_length):
# The maximal length of a path without a cycle is n
# (traverse each vertex once)
if path_length>n:
return False
# Is there a direct path from i to j?
if G[i][j]==1:
return True
# Is there an indirect path from i to j over i's neighbor k?
for k in range(n):
if G[i][k]==1: # Vertex k is a neighbor of i
if find_path(k, j, path_length+1):
return True
# We have not found any path
return False
# Path from vertex 1 to vertex 1?
print(find_path(1, 1, 0))
# Path from vertex 4 to vertex 1?
print(find_path(4, 1, 0))
Découvrez… quel est le résultat de cet extrait de code ?
Un domaine fondamental de l'informatique est la théorie des graphes .
Bien sûr, vous pouvez résoudre l'extrait de code sans même connaître la théorie des graphes.
Après tout, c'est ce que fait votre ordinateur lors de l'exécution de ce code. Mais l'ordinateur n'a pas à coder, les gens le font.
Plongeons-nous donc dans la théorie des graphes via un cours intensif ultra rapide.
Qu'est-ce qu'un graphique ?
Qu'est-ce donc qu'un graphique ?
Un graphe est une structure de données complexe telle qu'une liste, un ensemble ou un dictionnaire. La structure de données est complexe non pas parce que vous ne pouvez pas la comprendre, mais parce qu'elle se compose d'autres structures de données.
Vous utilisez la structure de données graphique si vous souhaitez représenter des relations entre des éléments de données.
Nous désignons les relations par arêtes et les éléments de données comme sommets .
Un exemple est le graphe social de Facebook. Facebook représente les utilisateurs comme des sommets et les relations d'amitié comme des arêtes. Deux utilisateurs sont connectés via une arête dans le graphique s'ils sont amis (Facebook).
Matrice de contiguïté
À quoi ressemble la structure des données ?
Dans le puzzle, nous utilisons une matrice d'adjacence comme structure de données graphique G. Chaque ligne i dans la matrice stocke les voisins sortants du sommet i . Chaque colonne j stocke les voisins du sommet j .
Ainsi, si nous voulons savoir s'il existe une arête à partir du sommet i au sommet j , nous vérifions si G[i][j]==1 .
Explication de l'algorithme Pathfinder
Comment vérifier s'il existe un chemin entre deux sommets ?
La fonction findPath(i, j, pathLength) vérifie s'il existe un chemin direct ou indirect entre deux sommets i et j .
Nous savons qu'il existe un chemin direct entre les sommets i et j s'ils sont déjà voisins, c'est-à-dire G[i][j]==1 . Pour déterminer s'il existe un chemin indirect, l'idée est d'utiliser une approche récursive. Il existe un chemin indirect, si un sommet k existe tel qu'il existe un chemin i --> ... --> k --> ... --> j .
La variable pathLength stocke la longueur du chemin actuel. Nous l'incrémentons à chaque niveau de récursivité lorsque la longueur du chemin actuel augmente de un.
Notez que tous les chemins de longueur >n composé de plus de n sommets. En d'autres termes, au moins un sommet est visité deux fois et un cycle existe dans cette instance de récursivité.
Par conséquent, nous sautons la récursivité pour les chemins dont la longueur est supérieure au nombre de sommets dans le graphe.
Ce puzzle demande s'il existe un chemin entre 3 et 0.
Si vous comprenez ce que fait le code, il suffit de regarder la matrice d'adjacence G. Il existe un chemin direct du sommet 3 aux sommets 1 et 2 (et à lui-même).
Mais les deux sommets 1 et 2 n'ont pas de voisins sortants. Par conséquent, il n'y a pas de chemin de ce type entre 3 et tout autre sommet (hormis les sommets 1 et 2).
Vidéo associée
Coque interactive Python Pathfinder
Vous pouvez essayer l'algorithme vous-même dans notre shell de code interactif :
Exercice :Modifiez la matrice d'adjacence afin qu'il existe un chemin indirect du sommet 0 au sommet 4 !
Cours de l'Académie - Maîtriser les 10 meilleurs algorithmes de graphes
Si vous souhaitez améliorer vos compétences fondamentales en informatique, il n'y a rien de plus efficace que l'étude des algorithmes .
Pour vous aider à maîtriser les algorithmes de graphe les plus importants , nous venons de lancer le cours "Top 10 Algorithms" à la Finxter Computer Science Academy. Cet excellent cours de Finxter Star Creator Matija ⭐ vous enseigne les algorithmes graphiques les plus importants tels que BFS, DFS, A* et Dijkstra.
Comprendre ces algorithmes fera non seulement de vous un meilleur codeur, mais cela posera également une base solide sur laquelle vous pourrez bâtir toute votre carrière d'informaticien.
Cliquez sur la capture d'écran pour en savoir plus :
