Struktur der Graphentheorie

In der Informatik werden Graphen häufig verwendet, um soziale Netzwerke (Benutzer sind Knoten, Freundschaften sind Kanten), Weblinks (Webseiten sind Knoten, Hyperlinks sind Kanten), Kommunikationsnetzwerke und sogar Probleme der Routenplanung zu modellieren.

GraphEs ist wie ein Beziehungsgraph eines sozialen Netzwerks:

  • Knoten (Vertex): Jede Person im sozialen Netzwerk
  • Kante: Beziehungen zwischen Personen (Freunde, Folgebeziehungen usw.)
  • Gewicht: Stärke der Beziehung (Nähe, Interaktionshäufigkeit usw.)

Stellen Sie sich das Verkehrsnetz in Ihrer Stadt vor: verschiedene Orte (wie Zuhause, Schule, Einkaufszentrum) sindPunkt, die Straßen, die diese Orte verbinden, sindLinie. Ein Graph (Graph) ist die mathematische Abstraktion der Beziehung zwischen Punkten und Linien; er wird verwendet, umKomplexe Beziehungen zwischen Entitäteneine Datenstruktur.

Praxisbeispiele:

  • Karte: Städte sind Knoten, Straßen sind Kanten, Entfernungen sind Gewichte
  • Schaltkreis: Komponenten sind Knoten, Drähte sind Kanten, der Widerstand ist das Gewicht
  • Internet: Websites sind Knoten, Links sind Kanten, Datenverkehr ist das Gewicht
  • Verkehrsnetz: Stationen sind Knoten, Routen sind Kanten, Fahrpreise sind Gewichte
Szenarien Andere Strukturen Graphstruktur
Soziale Beziehungen Schwierig, komplexe Beziehungen auszudrücken Drückt Viele-zu-viele-Beziehungen natürlich aus
Pfadplanung Erfordert komplexe Datenstrukturen Stellt Netzwerke und Pfade intuitiv dar
Abhängigkeitsbeziehungen Schwierig, zirkuläre Abhängigkeiten darzustellen Verarbeitet komplexe Abhängigkeiten mühelos
Netzwerkanalyse Kann Netzwerktopologie nicht ausdrücken Beschreibt die Netzwerkstruktur perfekt

Grundlegende Terminologie von Graphen

Begriff Definition Alltagsanalogie Symbolische Darstellung
Knoten Grundeinheit in einem Graphen Personen in sozialen Netzwerken V, u, v
Edge Eine Linie, die zwei Knoten verbindet Beziehung zwischen zwei Personen E, (u,v)
Grad Anzahl der mit einem Knoten verbundenen Kanten Anzahl der Freunde einer Person deg(v)
Pfad Knotenfolge Route von A nach B v₁→v₂→…→vₙ
Zyklus Ein Weg mit demselben Start- und Endpunkt Von zu Hause starten und schließlich nach Hause zurückkehren v₁→v₂→…→v₁
Zusammenhängender Graph Es gibt einen Pfad zwischen zwei beliebigen Punkten Jeder kann sich mit jedem anderen verbinden
Gewicht Numerische Eigenschaft einer Kante Entfernung zwischen zwei Städten w(u,v)

Klassifizierung von Graphen

Klassifizierungskriterien Type Funktionen Anwendungsszenarien
Gerichtetheit Ungerichteter Graph Kanten haben keine Richtung Freundschaftsbeziehungen, Straßennetze
Gerichteter Graph Kanten haben eine Richtung Follower-Beziehungen, Workflows
Gewicht Ungewichteter Graph Alle Kanten haben dasselbe Gewicht Beziehungen in sozialen Netzwerken
Gewichteter Graph Kanten haben unterschiedliche Gewichte Entfernungen auf Karten, Netzwerkverkehr
Konnektivität Zusammenhängender Graph Je zwei Punkte sind erreichbar Verkehrsnetz
Unzusammenhängender Graph Es gibt isolierte Knoten Soziale Gruppen
Zyklus Azyklischer Graph Keine Zyklen Aufgabenabhängigkeiten, Familienstammbäume
Zyklischer Graph Enthält Zyklen Straßennetz

Methoden zur Graphdarstellung

Adjazenzmatrix

Funktionen Beschreibung Zeitkomplexität Speicherkomplexität
Speichermethode zweidimensionale Matrix
Kantenexistenz prüfen matrix[i][j] != 0 O(1)
Kante hinzufügen matrix[i][j] = weight O(1)
Kante löschen matrix[i][j] = 0 O(1)
benachbarte Knoten durchlaufen eine Zeile/Spalte durchsuchen O(V)
Speicherbedarf V×V-Matrix O(V²)

Adjazenzliste

Funktionen Beschreibung Zeitkomplexität Speicherkomplexität
Speichermethode Array + verkettete Liste
Kantenexistenz prüfen Suchen in einer verketteten Liste O(deg(v))
Kante hinzufügen Hinzufügen in einer verketteten Liste O(1)
Kante löschen Löschen in einer verketteten Liste O(deg(v))
benachbarte Knoten durchlaufen verkettete Liste durchlaufen O(deg(v))
Speicherbedarf Knotenarray + verkettete Kantenliste O(V+E)

Grundlegende Konzepte von Graphen

ein GraphGBesteht aus zwei Mengen:

  • Knotenmenge V (Vertex Set): Die Menge aller Knoten im Graphen.
  • Kantenmenge E (Edge Set): die Menge der Linien, die diese Punkte verbinden. Eine Kante wird durch die beiden Knoten definiert, die sie verbindet(u, v)Repräsentiert.

Beispiel

# Ein einfaches Graphbeispiel: Verwendung eines Wörterbuchs zur Darstellung von Freundschaftsbeziehungen in sozialen Netzwerken
# Knoten: Alice, Bob, Charlie, Diana
# Kanten: repräsentieren die Freundschaftsbeziehungen zwischen ihnen

social_graph = {
    'Alice': ['Bob', 'Charlie'],   # Alice ist mit Bob und Charlie befreundet
    'Bob': ['Alice', 'Charlie', 'Diana'],
    'Charlie': ['Alice', 'Bob'],
    'Diana': ['Bob']
}

print(fKnoten (Benutzer): {list(social_graph.keys())})
print(fFreunde von Alice (Kanten): {social_graph['Alice']})

Ausgabe:

顶点（用户）: ['Alice', 'Bob', 'Charlie', 'Diana']
Alice 的好友（边）: ['Bob', 'Charlie']

Klassifizierung von Graphen und wichtige Konzepte

Graphen können anhand der Eigenschaften ihrer Kanten in mehrere Typen unterteilt werden; das Verständnis dieser ist die Grundlage für die Beherrschung der Graphentheorie.

Ungerichteter Graph vs gerichteter Graph

Type Eigenschaften von Kanten (Edge) Alltagsanalogie Beispiel
Ungerichteter Graph Kanten haben keine Richtung,(A, B)Stellt dar, dass A und B gegenseitig verbunden sind. bidirektionale Freundschaft: Wenn Alice mit Bob befreundet ist, muss Bob auch mit Alice befreundet sein. Freundschaften in sozialen Netzwerken, Verbindungen in Schaltkreisen.
Gerichteter Graph Kanten haben eine Richtung,A -> BStellt eine Einbahnverbindung von A nach B dar. Weibo-Folgen: Du kannst jemandem folgen, aber die andere Person folgt dir möglicherweise nicht zurück. Web-Hyperlinks, Aufgabenabhängigkeiten, Einbahnstraßen.

gewichteter Graph

In einem gewichteten Graphen wird jeder Kante ein numerischer Wert (Gewicht) zugewiesen, der Entfernung, Kosten, Zeit oder Beziehungsstärke darstellen kann.

Beispiel

# Ein gewichteter Graph, der Entfernungen zwischen Städten darstellt (Adjazenzlistenform)
weighted_graph = {
    'Beijing': {('Shanghai', 1200), ('Tianjin', 100)},  # Entfernung von Beijing nach Shanghai beträgt 1200, nach Tianjin 100
    'Schanghai': {('Peking', 1200), ('Hangzhou', 200)},
    'Tianjin': {('Peking', 100)},
    'Hangzhou': {('Schanghai', 200)}
}

Schlüsselbegriffe

  • Grad (Degree): die Anzahl der mit einem Knoten verbundenen Kanten. In einem gerichteten Graphen wird er unterteilt inEingangsgrad(Anzahl der Kanten, die auf den Knoten zeigen) undAusgangsgrad(Anzahl der Kanten, die vom Knoten wegzeigen).
  • Pfad (Path): eine Folge von Kanten, die von einem Knoten zu einem anderen durchlaufen werden. Zum Beispiel,A -> B -> C。
  • Zyklus/Kreis (Cycle): ein Pfad, dessen Start- und Endpunkt derselbe Knoten sind.
  • Zusammenhängender Graph: In einem ungerichteten Graphen existiert zwischen je zwei Knoten ein Pfad.
  • Stark zusammenhängender Graph: In einem gerichteten Graphen gibt es zwischen je zwei Knoten einen Pfad.bidirektionalerPfad.

Methoden zur Graphspeicherung

Wie stellt man einen Graphen in einem Computer dar? Es gibt hauptsächlich zwei gängige Methoden.

Adjazenzmatrix

Ein zweidimensionales Array (Matrix) verwendenmatrixzur Darstellung des Graphen.matrix[i][j]Der Wert repräsentiert den Knotenizum KnotenjDie Situation der Kanten.

  • Für ungerichtete Graphen ist die Matrix symmetrisch.
  • Bei einem gewichteten Graphen speichern die Matrixeinträge Gewichte (unter Verwendung spezieller Werte wie0oder∞steht für keine Kante).
  • Vorteile: Die Prüfung, ob es eine Kante zwischen zwei beliebigen Knoten gibt, ist sehr schnell (O(1)）。
  • Nachteile: Benötigt viel Platz (O(V^2)), verschwendet aber Platz für "dünn besetzte Graphen" mit wenigen Kanten.

Beispiel

# Eine Adjazenzmatrix verwenden, um einen ungerichteten Graphen darzustellen
# Knoten: 0-A, 1-B, 2-C
# Kanten: A-B, A-C

V = 3  # Anzahl der Knoten
adj_matrix = [[0] * V for _ in range(V)]

# Kante A-B hinzufügen (0-1)
adj_matrix[0][1] = 1
adj_matrix[1][0] = 1  # Bei einem ungerichteten Graphen müssen symmetrische Positionen gesetzt werden
# Kante A-C hinzufügen (0-2)
adj_matrix[0][2] = 1
adj_matrix[2][0] = 1

print("Adjazenzmatrix:")
for row in adj_matrix:
    print(row)
# Output:
# [0, 1, 1]
# [1, 0, 0]
# [1, 0, 0]

Adjazenzliste

Für jeden Knoten eine Liste (verkettete Liste, Array usw.) pflegen, die alle direkt mit ihm verbundenen Knoten (und Gewichte) aufzeichnet.

  • Vorteile: Hohe Speichereffizienz (O(V + E)), besonders geeignet für dünn besetzte Graphen. Sie kann schnell alle Nachbarn eines Knotens finden.
  • Nachteile: Die Prüfung, ob eine Kante zwischen zwei beliebigen Knoten existiert, ist langsamer (O(degree(V))）。

Beispiel

# Verwende eine Adjazenzliste (Dictionary + Liste), um denselben ungerichteten Graphen darzustellen
adj_list = {
    'A': ['B', 'C'],  # A ist mit B und C verbunden
    'B': ['A'],       # B ist mit A verbunden
    'C': ['A']        # C ist mit A verbunden
}

print("Adjazenzliste:")
for vertex, neighbors in adj_list.items():
    print(f"{vertex}: {neighbors}")

Graph-Traversierungsalgorithmen

Traversierung ist die Grundlage von Graphalgorithmen; sie bedeutet, jeden Knoten im Graphen systematisch zu besuchen.

Es gibt hauptsächlich zwei Strategien:

Breitensuche

Die Breitensuche (BFS) ist wie „Wasserwellenausbreitung“: Ausgehend vom Startpunkt besucht sie zuerst alle direkten Nachbarn, dann die Nachbarn der Nachbarn und so weiter. Sie verwendetWarteschlangezur Implementierung.

Algorithmusschritte：

  1. Füge den Startpunkt in eine Warteschlange ein und markiere ihn als besucht.
  2. Wenn die Warteschlange nicht leer ist: a. Entferne den vordersten Knoten aus der Warteschlangev. b. Besuchevalle unbesuchten Nachbarn davon, füge sie in die Warteschlange ein und markiere sie als besucht.
  3. Wiederhole Schritt 2.

Beispiel

from collections import deque

def bfs(graph, start):
    """Verwende BFS, um den Graphen zu durchlaufen, und gib die Besuchsreihenfolge zurück"""
    visited = set([start])  # Besuchte Knoten aufzeichnen
    queue = deque([start])  # Warteschlange initialisieren
    result = []             # Besuchsreihenfolge speichern

    while queue:
        vertex = queue.popleft()
        result.append(vertex)
        # Nachbarn des aktuellen Knotens durchlaufen
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return result

# Testdaten
test_graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("BFS-Durchlaufreihenfolge (beginnend bei A):", bfs(test_graph, 'A'))
# Ausgabe könnte sein: ['A', 'B', 'C', 'D', 'E', 'F']

Tiefensuche

Die Tiefensuche (DFS) ist wie "durch ein Labyrinth zu gehen": Sie wählt einen Pfad, geht bis zum Ende, kehrt dann zurück und nimmt einen anderen Pfad. Sie verwendetStack(oder Rekursion) zur Implementierung.

Schritte des rekursiven Algorithmus：

  1. vom KnotenvStart, als besucht markieren.
  2. forvjeden unbesuchten Nachbarn vonu: a. Rekursiver AufrufDFS(u)。

Beispiel

def dfs_recursive(graph, vertex, visited=None, result=None):
    """DFS mit Rekursion implementieren"""
    if visited is None:
        visited = set()
    if result is None:
        result = []

    visited.add(vertex)
    result.append(vertex)

    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, result)
    return result

print("DFS-Traversierungsreihenfolge (beginnend bei A):", dfs_recursive(test_graph, 'A'))
# Die Ausgabe könnte sein: ['A', 'B', 'D', 'E', 'F', 'C']

Vergleich von Algorithmen zur Graphendurchquerung:

Klassische Anwendungsszenarien und Einführung in die Algorithmen

Sobald Sie die Graphdarstellung und -durchquerung beherrschen, können Sie viele klassische Probleme erkunden:

  1. Kürzeste-Wege-Problem: in der Kartennavigation die kürzeste Fahrstrecke zwischen zwei Punkten finden.

    • Algorithmus von Dijkstra: gilt fürnicht-negativ gewichteteGraphen.
    • Algorithmus von Floyd: die kürzesten Pfade zwischen allen Knotenpaaren berechnen.

  2. Minimaler Spannbaum: unter der Voraussetzung, dass alle Knoten verbunden bleiben, die Kantenmenge mit dem kleinsten Gesamtgewicht auswählen (zum Beispiel das Verlegen des kostengünstigsten Glasfasernetzes für mehrere Dörfer).

    • Prim-Algorithmus
    • Kruskal-Algorithmus

  3. Topologische Sortierung: die Knoten eines gerichteten azyklischen Graphen (DAG) linear anordnen, sodass für jede gerichtete Kanteu->v，uBeim Sortieren sind alle eingereihtvvor (zum Beispiel die Lernreihenfolge von Kursen festlegen).

Weitere Erweiterungen