Python - Graph Algorithmen

Diagramme sind sehr nützliche Datenstrukturen zur Lösung vieler wichtiger mathematischer Herausforderungen. Zum Beispiel Computernetzwerktopologie oder Analyse molekularer Strukturen chemischer Verbindungen. Sie werden auch im Stadtverkehr oder in der Routenplanung und sogar in menschlichen Sprachen und ihrer Grammatik verwendet. Alle diese Anwendungen haben die gemeinsame Herausforderung, das Diagramm anhand ihrer Kanten zu durchlaufen und sicherzustellen, dass alle Knoten der Diagramme besucht werden. Es gibt zwei allgemein etablierte Methoden, um diese Durchquerung durchzuführen, die nachstehend beschrieben wird.

Tiefe erste Durchquerung:

Dieser Algorithmus, auch als DFS (Depth First Search) bezeichnet, durchläuft einen Graphen in einer Tiefenbewegung und verwendet einen Stapel, um sich daran zu erinnern, den nächsten Scheitelpunkt zum Starten einer Suche zu erhalten, wenn in einer Iteration eine Sackgasse auftritt. Wir implementieren DFS für ein Diagramm in Python unter Verwendung der festgelegten Datentypen, da diese die erforderlichen Funktionen bereitstellen, um besuchte und nicht besuchte Knoten zu verfolgen.

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

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

a b d e c

Breite erste Durchquerung

Dieser Algorithmus wird auch als Bread-First-Search (BFS) bezeichnet. Er durchläuft eine Bewegung der Graphbreite und verwendet eine Warteschlange, um sich daran zu erinnern, den nächsten Scheitelpunkt zum Starten einer Suche zu erhalten, wenn in einer Iteration eine Sackgasse auftritt. Bitte besuchen Sie diesen Link auf unserer Website, um die Details der BFS-Schritte für ein Diagramm zu verstehen.

Wir implementieren BFS für ein Diagramm in Python unter Verwendung der zuvor diskutierten Warteschlangendatenstruktur. Wenn wir die benachbarten nicht besuchten Knoten weiterhin besuchen und sie der Warteschlange hinzufügen. Dann beginnen wir, nur den Knoten aus der Warteschlange zu entfernen, der keine nicht besuchten Knoten mehr hat. Wir stoppen das Programm, wenn kein nächster benachbarter Knoten besucht werden soll.

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

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

a c b d e