So implementieren Sie Suchalgorithmen für die Breite und Tiefe von Graphen in Python-Python-Tutorial-php.cn

Vorwort

Graph ist eine abstrakte Datenstruktur, die im Wesentlichen einer Baumstruktur entspricht.

Im Vergleich zu Bäumen sind Diagramme geschlossen. Die Baumstruktur kann als Vorgänger der Diagrammstruktur angesehen werden. Wenn Sie horizontale Verbindungen zwischen Geschwisterknoten oder untergeordneten Knoten auf eine Baumstruktur anwenden, können Sie eine Diagrammstruktur erstellen.

Tree eignet sich zur Beschreibung einer Eins-zu-Viele-Datenstruktur von oben nach unten, beispielsweise der Organisationsstruktur eines Unternehmens.

Grafiken eignen sich zur Beschreibung komplexerer Viele-zu-Viele-Datenstrukturen, wie beispielsweise komplexer sozialer Gruppenbeziehungen.

So implementieren Sie Suchalgorithmen für die Breite und Tiefe von Graphen in Python

1. Graphentheorie

Wenn Sie Computer zur Lösung von Problemen in der realen Welt verwenden, müssen Sie nicht nur Informationen in der realen Welt speichern, sondern auch die Beziehung zwischen den Informationen korrekt beschreiben.

Zum Beispiel ist es bei der Entwicklung eines Kartenprogramms notwendig, die Beziehungen zwischen Städten oder Straßen in der Stadt am Computer korrekt zu simulieren. Nur auf dieser Grundlage können Algorithmen den besten Weg von einer Stadt zur anderen oder von einem vorgegebenen Startpunkt zu einem Zielpunkt berechnen.

Ähnlich gibt es Flugroutenkarten, Zugroutenkarten und Karten für soziale Kommunikation.

Graphstrukturen können die oben beschriebenen komplexen Beziehungen zwischen Informationen in der realen Welt effektiv widerspiegeln. Mit diesem Algorithmus lässt sich ganz einfach der kürzeste Weg auf einer Flugstrecke, der beste Umsteigeplan auf einer Zugstrecke, wer mit wem im sozialen Umfeld die beste Beziehung hat und wer mit wem im Ehenetzwerk am besten verträglich ist. ..

1.1 Das Konzept des Graphen

Vertex: Vertex wird auch Knoten genannt, und ein Graph kann als eine Sammlung von Scheitelpunkten betrachtet werden. Die Scheitelpunkte selbst haben eine Datenbedeutung, daher tragen die Scheitelpunkte zusätzliche Informationen, die als „Nutzlast“ bezeichnet werden.

Scheitelpunkte können Städte, Ortsnamen, Stationsnamen, Menschen in der realen Welt sein ... Kanten können eine Richtung oder keine Richtung haben. Richtungskanten können in unidirektionale Kanten und bidirektionale Kanten unterteilt werden.

Wie in der Abbildung unten gezeigt, hat die Kante zwischen (Element 1) und (Scheitelpunkt 2) nur eine Richtung (der Pfeil zeigt die Richtung), So implementieren Sie Suchalgorithmen für die Breite und Tiefe von Graphen in Python wird als Einwegkante

bezeichnet. Ähnlich einer Einbahnstraße in der realen Welt. Die Kante zwischen

(Scheitelpunkt 1) und (Scheitelpunkt 2) hat zwei Richtungen (bidirektionale Pfeile), wird als bidirektionale Kante bezeichnet.

Die Beziehung zwischen Städten ist wechselseitig.

Gewicht: Wertinformationen können am Rand hinzugefügt werden, und der Mehrwert wird

Gewicht

genannt. Gewichtete Kanten beschreiben die Stärke einer Verbindung von einem Scheitelpunkt zum anderen. So implementieren Sie Suchalgorithmen für die Breite und Tiefe von Graphen in Python

In realen U-Bahn-Strecken können Gewichte beispielsweise die Zeitdauer, Kilometer und Fahrpreise zwischen zwei Stationen beschreiben ...

Kanten beschreiben die Beziehung zwischen Eckpunkten und Gewichte beschreiben den Unterschied in den Verbindungen.

Pfad:

So implementieren Sie Suchalgorithmen für die Breite und Tiefe von Graphen in Python Verstehen Sie zunächst das Konzept des Pfads in der realen Welt.

Zum Beispiel: Wenn Sie von einer Stadt in eine andere fahren, müssen Sie zuerst den Pfad bestimmen. Das heißt: Welche Städte müssen Sie vom Abfahrtsort bis zum Zielort durchqueren? Wie viele Meilen wird es dauern?

Wir können sagen, dass ein Pfad eine Folge von Eckpunkten ist, die durch Kanten verbunden sind. Da es mehr als einen Pfad gibt, bezieht sich die Pfadbeschreibung von einem Elementpunkt zu einem anderen Elementpunkt nicht auf einen Typ.

Wie berechnet man Pfade in Diagrammstrukturen?

Die Länge eines ungewichteten Pfades ist die Anzahl der Kanten auf dem Pfad.

Die Länge eines gewichteten Pfades ist die Summe der Gewichte der Kanten auf dem Pfad.

Wie in der obigen Abbildung gezeigt, beträgt die Pfadlänge von (Scheitelpunkt 1) bis (Scheitelpunkt 3) 8.
Schleife:
Vom Startpunkt aus und schließlich zurück zum Ausgangspunkt (der Endpunkt ist auch der Ausgangspunkt) bildet eine Schleife einen besonderen Weg. Wie oben ist

Arten von Diagrammen:

Zusammenfassend können Diagramme in die folgenden Kategorien unterteilt werden: (V1, V2, V3, V1)

Gerichtete Diagramme:

Ein Diagramm mit gerichteten Kanten wird als gerichtetes Diagramm bezeichnet.

Ungerichteter Graph: Ein Graph, dessen Kanten keine Richtung haben, wird als ungerichteter Graph bezeichnet.
Gewichteter Graph: Ein Graph mit Gewichtsinformationen an den Kanten wird als gewichteter Graph bezeichnet.
Azyklischer Graph: Ein Graph ohne Zyklen wird als azyklischer Graph bezeichnet.
Gerichteter azyklischer Graph: Ein gerichteter Graph ohne Zyklus, der als DAG bezeichnet wird.
1.2 Diagramm definieren
Entsprechend den Eigenschaften des Diagramms muss die Diagrammdatenstruktur mindestens zwei Arten von Informationen enthalten:

Alle Eckpunkte bilden einen Satz von Informationen, hier dargestellt durch V (in einem Kartenprogramm werden beispielsweise alle Städte in einem Eckpunktsatz gebildet).

Alle Kanten stellen Mengeninformationen dar, hier dargestellt durch E (Beschreibung der Beziehung zwischen Städten).

Wie beschreibt man Kanten?

Kanten werden verwendet, um die Beziehung zwischen Objektpunkten darzustellen. Eine Kante kann also 3 Metadaten enthalten (Startpunkt, Endpunkt, Gewicht). Natürlich können die Gewichte weggelassen werden, aber im Allgemeinen beziehen sie sich beim Studium von Diagrammen auf gewichtete Diagramme.

Wenn G zur Darstellung des Diagramms verwendet wird, dann ist G = (V, E). Jede Kante kann durch ein Tupel (fv, ev) oder ein Triplett (fv, ev, w) beschrieben werden. G 表示图，则 G = (V, E)。每一条边可以用二元组 (fv, ev) 也可以使用三元组 （fv,ev,w） 描述。

fv 表示起点，ev 表示终点。且 fv，ev 数据必须引用于 V 集合。

如上的图结构可以描述如下：
```
# 5 个顶点
V={A0,B1,C2,D3,E4}
# 7 条边
E={ (A0,B1,3),(B1,C2,4),(C2,D3,6),(C2,E4,1),(D3,E4,2),(A0,D3,5),(E4,B1,7)}
```
Nach dem Login kopieren
1.3 图的抽象数据结构
图的抽象数据描述中至少要有的方法：
- Graph ( ) ：用来创建一个新图。
- add_vertex( vert )：向图中添加一个新节点，参数应该是一个节点类型的对象。
- add_edge(fv，tv )：在 2 个项点之间建立起边关系。
- add_edge(fv，tv，w )：在 2 个项点之间建立起一条边并指定连接权重。
- find_vertex( key ): 根据关键字 key 在图中查找顶点。
- find_vertexs( )：查询所有顶点信息。
- find_path( fv,tv)：查找.从一个顶点到另一个顶点之间的路径。
2. 图的存储实现
图的存储实现主流有 2 种：邻接矩阵和链接表，本文主要介绍邻接矩阵。
2.1 邻接矩阵
使用二维矩阵（数组）存储顶点之间的关系。
如 graph[5][5] 可以存储 5 个顶点的关系数据，行号和列号表示顶点，第 v 行的第 w 列交叉的单元格中的值表示从顶点 v 到顶点 w 的边的权重，如 grap[2][3]=6 表示 C2 顶点和 D3 顶点的有连接（相邻），权重为 6
相邻矩阵的优点就是简单，可以清晰表示那些顶点是相连的。由于并非每对顶点之间都存在连接，因此矩阵中存在许多未被利用的空间，通常被称为“稀疏矩阵”。
只有当每一个顶点和其它顶点都有关系时，矩阵才会填满。如果图结构的关系不是太复杂，使用这种结构存储图数据会浪费大量的空间。
邻接矩阵适合表示关系复杂的图结构，如互联网上网页之间的链接、社交圈中人与人之间的社会关系……
2.2 编码实现邻接矩阵
因顶点本身有数据含义，需要先定义顶点类型。
顶点类：
```
"""
节（顶）点类
"""
class Vertex:
    def __init__(self, name, v_id=0):
        # 顶点的编号
        self.v_id = v_id
        # 顶点的名称
        self.v_name = name
        # 是否被访问过:False 没有 True:有
        self.visited = False

    # 自我显示
    def __str__(self):
        return &#39;[编号为 {0}，名称为 {1} ] 的顶点&#39;.format(self.v_id, self.v_name)
```
Nach dem Login kopieren
顶点类中 v_id 和 v_name 很好理解。为什么要添加一个 visited？
这个变量用来记录顶点在路径搜索过程中是否已经被搜索过，避免重复搜索计算。
图类：图类的方法较多，这里逐方法介绍。
初始化方法
```
class Graph:
    """
    nums:相邻矩阵的大小
    """

    def __init__(self, nums):
        # 一维列表，保存节点，最多只能有 nums 个节点
        self.vert_list = []
        # 二维列表，存储顶点及顶点间的关系(权重)
        # 初始权重为 0 ，表示节点与节点之间还没有建立起关系
        self.matrix = [[0] * nums for _ in range(nums)]
        # 顶点个数
        self.v_nums = 0
        # 使用队列模拟队列或栈，用于广度、深度优先搜索算法
        self.queue_stack = []
        # 保存搜索到的路径
        self.searchPath = []
        
    # 暂省略……
```
Nach dem Login kopieren
初始化方法用来初始化图中的数据类型：
一维列表 vert_list 保存所有顶点数据。
二维列表 matrix 保存顶点与顶点之间的关系数据。
queue_stack 使用列表模拟队列或栈，用于后续的广度搜索和深度搜索。
怎么使用列表模拟队列或栈？
列表有 append()、pop() 2 个很价值的方法。
append() 用来向列表中添加数据，且每次都是从列表最后面添加。
pop() 默认从列表最后面删除且弹出数据， pop(参数) 可以提供索引值用来从指定位置删除且弹出数据。
使用 append() 和 pop() 方法就能模拟栈，从同一个地方进出数据。
使用 append() 和 pop(0) 方法就能模拟队列，从后面添加数据，从最前面获取数据
searchPath
fv stellt den Startpunkt dar und ev stellt den Endpunkt dar. Und fv-, ev-Daten müssen in der V-Sammlung referenziert werden.

Die obige Diagrammstruktur kann wie folgt beschrieben werden: 🎜
```
    """
    添加新顶点
    """
    def add_vertex(self, vert):
        if vert in self.vert_list:
            # 已经存在
            return
        if self.v_nums >= len(self.matrix):
            # 超过相邻矩阵所能存储的节点上限
            return
        # 顶点的编号内部生成
        vert.v_id = self.v_nums
        self.vert_list.append(vert)
        # 数量增一
        self.v_nums += 1
```
Nach dem Login kopieren
Nach dem Login kopieren
1.3 Abstrakte Datenstruktur des Diagramms
🎜Zumindest die Methode, die in der abstrakten Datenbeschreibung des Diagramms enthalten sein muss: 🎜
- 🎜Graph ( ): Wird zum Erstellen eines neuen Diagramms verwendet. 🎜
- 🎜add_vertex( vert ): Fügen Sie dem Diagramm einen neuen Knoten hinzu. Der Parameter sollte ein Objekt vom Knotentyp sein. 🎜
- 🎜add_edge(fv, tv): Stellen Sie eine Kantenbeziehung zwischen 2 Elementpunkten her. 🎜
- 🎜add_edge(fv,tv,w): Legen Sie eine Kante zwischen 2 Elementpunkten fest und geben Sie das Verbindungsgewicht an. 🎜
- 🎜find_vertex( key): Scheitelpunkte im Diagramm basierend auf dem Schlüsselwort key finden. 🎜
- 🎜find_vertexs( ): Alle Scheitelpunktinformationen abfragen. 🎜
- 🎜find_path(fv,tv): Finden Sie den Pfad von einem Scheitelpunkt zu einem anderen Scheitelpunkt. 🎜
2. Diagrammspeicherimplementierung
🎜Es gibt zwei Haupttypen der Diagrammspeicherimplementierung: Adjazenzmatrix und Linkliste. In diesem Artikel wird hauptsächlich die Adjazenzmatrix vorgestellt. 🎜
2.1 Adjazenzmatrix
🎜Verwenden Sie eine zweidimensionale Matrix (Array), um die Beziehung zwischen Eckpunkten zu speichern. 🎜🎜Zum Beispiel kann graph[5][5] die relationalen Daten von 5 Scheitelpunkten speichern. Die Zeilennummer und die Spaltennummer stellen den Wert in der Zelle dar, die die v-te Zeile und das wth schneidet Die Spalte stellt den Startpunkt dar. Das Gewicht der Kante vom Scheitelpunkt v zum Scheitelpunkt w, z. B. grap[2][3]=6 bedeutet, dass der Scheitelpunkt C2 und der Scheitelpunkt D3 verbunden (angrenzend) sind. , und das Gewicht beträgt 6🎜🎜
```
  &#39;&#39;&#39;
    添加节点与节点之间的边，
    如果是无权重图，统一设定为 1 
    &#39;&#39;&#39;
    def add_edge(self, from_v, to_v):
        # 如果节点不存在
        if from_v not in self.vert_list:
            self.add_vertex(from_v)
        if to_v not in self.vert_list:
            self.add_vertex(to_v)
        # from_v 节点的编号为行号，to_v 节点的编号为列号
        self.matrix[from_v.v_id][to_v.v_id] = 1

    &#39;&#39;&#39;
    添加有权重的边
    &#39;&#39;&#39;
    def add_edge(self, from_v, to_v, weight):
        # 如果节点不存在
        if from_v not in self.vert_list:
            self.add_vertex(from_v)
        if to_v not in self.vert_list:
            self.add_vertex(to_v)
        # from_v 节点的编号为行号，to_v 节点的编号为列号
        self.matrix[from_v.v_id][to_v.v_id] = weight
```
Nach dem Login kopieren
Nach dem Login kopieren

上述方法注意一点，节点的编号由图内部逻辑提供，便于节点编号顺序的统一。

添加边信息的方法有 2 个，一个用来添加无权重边，一个用来添加有权重的边。

3. 搜索路径

在图中经常做的操作，就是查找从一个顶点到另一个顶点的路径。如怎么查找到 A0 到 E4 之间的路径长度：

在路径查找时，人的思维具有知识性和直观性特点，因此不存在所谓的尝试或碰壁问题。而计算机是试探性思维，就会出现这条路不通，再找另一条路的现象。

所以路径算法中常常会以错误为代价，在查找过程中会走一些弯路。常用的路径搜索算法有 2 种：

3.1 广度优先搜索

使用广度搜索到的路径与候选节点进入队列的先后顺序有关系。如第 1 步确定候选节点时 B1 和 D3 谁先进入队列，对于后面的查找也会有影响。

其实 {A0，B1，C2，E4} 也是一条有效路径，有可能搜索不出来，这里因为搜索到 B1 后不会马上搜索 C2，因为 B3 先于 C2 进入，广度优先搜索算法只能保证找到路径，而不能保存找到最佳路径。

广度优先搜索需要借助队列临时存储选节点，本文使用列表模拟队列。

广度优先搜索过程中，需要随时获取与当前节点相邻的节点，find_neighbor() 方法的作用就是用来把当前节点的相邻节点压入队列中。

3.2 深度优先搜索算法

深度优先搜索算法和广度优先搜索算法不同的地方在于：深度优先搜索算法将候选节点放在堆栈中。因栈是先进后出，所以，搜索到的节点顺序不一样。

递归实现时，不需要使用全局栈，只需要获到当前节点的相邻节点便可。

Das obige ist der detaillierte Inhalt vonSo implementieren Sie Suchalgorithmen für die Breite und Tiefe von Graphen in Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!