SciPy-Graphstruktur

Graphstruktur ist eines der mächtigsten Frameworks in der Algorithmik.

Ein Graph ist eine Sammlung von Knoten und Kanten verschiedener Beziehungen. Knoten sind Eckpunkte, die Objekten entsprechen, und Kanten sind Verbindungen zwischen Objekten.

SciPy stellt das Modul scipy.sparse.csgraph bereit, um Graphstrukturen zu verarbeiten.

Adjazenzmatrix

Eine Adjazenzmatrix ist eine Matrix, die die Adjazenzbeziehungen zwischen Knoten darstellt.

Die logische Struktur einer Adjazenzmatrix ist in zwei Teile unterteilt: die Mengen V und E, wobei V für Knoten und E für Kanten steht. Kanten haben manchmal Gewichte, die die Verbindungsstärke zwischen Knoten darstellen.

Ein eindimensionales Array wird verwendet, um alle Knotendaten im Graphen zu speichern, und ein zweidimensionales Array wird verwendet, um die Daten der Beziehungen zwischen Knoten (Kanten oder Bögen) zu speichern. Dieses zweidimensionale Array wird Adjazenzmatrix genannt.

Betrachten Sie das folgende Beispiel:

Die Knoten sind A, B, C, und die Kantengewichte sind 1 und 2.

A und B sind mit Gewicht 1 verbunden.

A und C sind mit Gewicht 2 verbunden.

C und B sind nicht verbunden.

Diese Adjazenzmatrix kann als das folgende zweidimensionale Array dargestellt werden:
     A B C
   A:[0 1 2]  
   B:[1 0 0]
   C:[2 0 0]

Adjazenzmatrizen werden weiter in Adjazenzmatrizen für gerichtete Graphen und Adjazenzmatrizen für ungerichtete Graphen unterteilt.

Ein ungerichteter Graph ist eine bidirektionale Beziehung, und Kanten haben keine Richtung:

Die Kanten eines gerichteten Graphen haben eine Richtung und sind unidirektionale Beziehungen:

Hinweis:Der Knoten D in den beiden obigen Abbildungen ist eine Selbstschleife. Eine Selbstschleife bedeutet, dass beide Enden einer Kante derselbe Knoten sind.

Zusammenhangskomponenten

Verwenden Sie die Methode connected_components(), um alle Zusammenhangskomponenten anzuzeigen.

Beispiel

import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(connected_components(newarr))

Die Ausgabe des obigen Codes ist:

(1, array([0, 0, 0], dtype=int32))

Dijkstra -- Algorithmus für kürzeste Wege

Dijkstras Algorithmus für kürzeste Wege wird verwendet, um die kürzesten Wege von einem Knoten zu allen anderen Knoten zu berechnen.

SciPy verwendet die Methode dijkstra(), um den kürzesten Weg von einem Element zu anderen Elementen zu berechnen.

Mit der Methode dijkstra() können die folgenden Parameter festgelegt werden:
  1. return_predecessors:Ein boolescher Wert. Setzen Sie ihn auf True, um alle Pfade zu durchlaufen; wenn Sie nicht alle Pfade durchlaufen möchten, setzen Sie ihn auf False.
  2. indices:Der Index des Elements, der alle Pfade von diesem Element zurückgibt.
  3. limit:Das maximale Gewicht der Pfade.

Beispiel

Finden Sie den kürzesten Pfad von Element 1 zu Element 2:

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(dijkstra(newarr, return_predecessors=True, indices=0))

Die Ausgabe des obigen Codes ist:

(array([ 0.,  1.,  2.]), array([-9999,     0,     0], dtype=int32))

Floyd Warshall -- Floyds Algorithmus

Floyds Algorithmus ist ein Algorithmus zur Lösung des kürzesten Pfads zwischen zwei beliebigen Punkten.

SciPy verwendet die Methode floyd_warshall(), um den kürzesten Pfad zwischen allen Elementpaaren zu finden.

Beispiel

Finden Sie die kürzesten Pfade zwischen allen Elementpaaren:

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(floyd_warshall(newarr, return_predecessors=True))

Die Ausgabe des obigen Codes ist:

(array([[ 0.,  1.,  2.],
       [ 1.,  0.,  3.],
       [ 2.,  3.,  0.]]), array([[-9999,     0,     0],
       [    1, -9999,     0],
       [    2,     0, -9999]], dtype=int32))

Bellman Ford -- Bellman-Ford-Algorithmus

Der Bellman-Ford-Algorithmus ist ein Algorithmus zur Bestimmung des kürzesten Pfads zwischen zwei beliebigen Punkten.

SciPy verwendet die Methode bellman_ford(), um den kürzesten Pfad zwischen allen Paaren von Elementen zu finden. Sie kann im Allgemeinen in jedem Graphen verwendet werden, einschließlich gerichteter Graphen und Graphen mit negativ gewichteten Kanten.

Beispiel

Verwenden Sie einen Graphen mit negativ gewichteten Kanten, um den kürzesten Pfad von Element 1 zu Element 2 zu finden:

import numpy as np
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix

arr = np.array([
  [0, -1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(bellman_ford(newarr, return_predecessors=True, indices=0))

Die Ausgabe des obigen Codes ist:

(array([ 0., -1.,  2.]), array([-9999,     0,     0], dtype=int32))

Tiefensuche-Reihenfolge

Die Methode depth_first_order() gibt die Reihenfolge des Tiefendurchlaufs von einem Knoten zurück.

Sie kann die folgenden Parameter akzeptieren:

  • Graph
  • Das Element, von dem aus der Graphdurchlauf beginnt

Beispiel

Geben Sie bei gegebener Adjazenzmatrix die Reihenfolge des Tiefendurchlaufs zurück:

import numpy as np
from scipy.sparse.csgraph import depth_first_order
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 0, 1],
  [1, 1, 1, 1],
  [2, 1, 1, 0],
  [0, 1, 0, 1]
])

newarr = csr_matrix(arr)

print(depth_first_order(newarr, 1))

Die Ausgabe des obigen Codes ist:

(array([1, 0, 3, 2], dtype=int32), array([    1, -9999,     1,     0], dtype=int32))

Breitensuche-Reihenfolge

Die Methode breadth_first_order() gibt die Breitensuche-Traversierungsreihenfolge von einem Knoten zurück.

Sie kann die folgenden Parameter akzeptieren:

  • Graph
  • Das Element, von dem aus der Graphdurchlauf beginnt

Beispiel

Geben Sie für eine Adjazenzmatrix die Breitensuche-Traversierungsreihenfolge zurück:

import numpy as np
from scipy.sparse.csgraph import breadth_first_order
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 0, 1],
  [1, 1, 1, 1],
  [2, 1, 1, 0],
  [0, 1, 0, 1]
])

newarr = csr_matrix(arr)

print(breadth_first_order(newarr, 1))

Die Ausgabe des obigen Codes ist:

(array([1, 0, 2, 3], dtype=int32), array([    1, -9999,     1,     1], dtype=int32))
Andere Erweiterungen