Python - Algorithmes de graphes

Les graphiques sont des structures de données très utiles pour résoudre de nombreux défis mathématiques importants. Par exemple, la topologie de réseau informatique ou l'analyse des structures moléculaires de composés chimiques. Ils sont également utilisés dans le trafic urbain ou la planification d'itinéraire et même dans les langues humaines et leur grammaire. Toutes ces applications ont le défi commun de parcourir le graphe en utilisant leurs arêtes et de s'assurer que tous les nœuds des graphes sont visités. Il existe deux méthodes établies communes pour effectuer cette traversée qui est décrite ci-dessous.

Profondeur première traversée:

Également appelé recherche en profondeur (DFS), cet algorithme parcourt un graphe dans un mouvement de profondeur et utilise une pile pour se souvenir d'obtenir le sommet suivant pour démarrer une recherche, lorsqu'une impasse se produit dans une itération. Nous implémentons DFS pour un graphique en python en utilisant les types de données définis car ils fournissent les fonctionnalités requises pour garder une trace des nœuds visités et non visités.

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

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

a b d e c

Largeur première traversée

Également appelé recherche en largeur (BFS), cet algorithme parcourt un mouvement de largeur de graphe et utilise une file d'attente pour se souvenir d'obtenir le sommet suivant pour démarrer une recherche, lorsqu'une impasse se produit dans une itération. Veuillez visiter ce lien sur notre site Web pour comprendre les détails des étapes BFS pour un graphique.

Nous implémentons BFS pour un graphique en python en utilisant la structure de données de file d'attente évoquée précédemment. Lorsque nous continuons à visiter les nœuds non visités adjacents et que nous les ajoutons à la file d'attente. Ensuite, nous commençons à retirer la file d'attente uniquement du nœud qui n'a pas de nœuds non visités. Nous arrêtons le programme lorsqu'il n'y a pas de prochain nœud adjacent à visiter.

import collections
class graph:
    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict

def bfs(graph, startnode):
# Track the visited and unvisited nodes using queue
        seen, queue = set([startnode]), collections.deque([startnode])
        while queue:
            vertex = queue.popleft()
            marked(vertex)
            for node in graph[vertex]:
                if node not in seen:
                    seen.add(node)
                    queue.append(node)

def marked(n):
    print(n)

# The graph dictionary
gdict = { "a" : set(["b","c"]),
                "b" : set(["a", "d"]),
                "c" : set(["a", "d"]),
                "d" : set(["e"]),
                "e" : set(["a"])
                }

bfs(gdict, "a")

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

a c b d e