Algorithmes graphiques

Les graphes sont des structures de données très utiles pour résoudre de nombreux défis mathématiques importants. Par exemple, la topologie des réseaux informatiques ou l'analyse des structures moléculaires des composés chimiques. Ils sont également utilisés dans la circulation urbaine ou la planification des itinéraires et même dans les langues humaines et leur grammaire. Toutes ces applications ont un défi commun : traverser le graphe en utilisant ses bords et s'assurer que tous les nœuds du graphe sont visités. Il existe deux méthodes courantes établies pour effectuer cette traversée, décrite ci-dessous.

Depth First Traversal

Le depth first search (DFS) est un algorithme qui parcourt un graphe en profondeur et utilise une pile pour se souvenir du prochain sommet à rechercher, lorsqu'une impasse se produit dans une itération. Nous implémentons DFS pour un graphe en Python en utilisant les types de données set car ils fournissent les fonctionnalités nécessaires pour garder la trace des nœuds visités et non visités.

Exemple

class graph:
    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict
    # Check for the visisted and unvisited nodes
    def dfs(graph, start, visited = None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

gdict = { 
    "a" : set(["b","c"]),
    "b" : set(["a", "d"]),
    "c" : set(["a", "d"]),
    "d" : set(["e"]),
    "e" : set(["a"])
}
dfs(gdict, 'a')

Réponse