Python - Algoritmi grafici

I grafici sono strutture dati molto utili per risolvere molte importanti sfide matematiche. Ad esempio la topologia di una rete di computer o l'analisi di strutture molecolari di composti chimici. Sono utilizzati anche nel traffico cittadino o nella pianificazione del percorso e persino nelle lingue umane e nella loro grammatica. Tutte queste applicazioni hanno la sfida comune di attraversare il grafico utilizzando i loro bordi e garantire che tutti i nodi dei grafici vengano visitati. Esistono due metodi comuni stabiliti per eseguire questo attraversamento, descritti di seguito.

Profondità prima traversata:

Chiamato anche depth first search (DFS), questo algoritmo attraversa un grafico in un movimento di reparto di profondità e utilizza uno stack per ricordare di ottenere il vertice successivo per avviare una ricerca, quando si verifica un vicolo cieco in qualsiasi iterazione. Implementiamo DFS per un grafico in python utilizzando i tipi di dati impostati in quanto forniscono le funzionalità richieste per tenere traccia dei nodi visitati e non visitati.

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

Quando il codice sopra viene eseguito, produce il seguente risultato:

a b d e c

Larghezza prima traversata

Chiamato anche breadth first search (BFS), questo algoritmo attraversa un movimento di ampiezza del grafico e utilizza una coda per ricordare di ottenere il vertice successivo per avviare una ricerca, quando si verifica un vicolo cieco in qualsiasi iterazione. Visitare questo collegamento nel nostro sito Web per comprendere i dettagli dei passaggi BFS per un grafico.

Implementiamo BFS per un grafico in Python utilizzando la struttura dei dati della coda discussa in precedenza. Quando continuiamo a visitare i nodi adiacenti non visitati e continuiamo ad aggiungerlo alla coda. Quindi iniziamo a rimuovere dalla coda solo il nodo che è rimasto senza nodi non visitati. Interrompiamo il programma quando non c'è un prossimo nodo adiacente da visitare.

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

Quando il codice sopra viene eseguito, produce il seguente risultato:

a c b d e