Python에서 그래프 너비와 깊이 우선 경로 검색 알고리즘을 구현하는 방법
- 王林앞으로
- 2023-06-02 23:42:011439검색
머리말
그래프는 추상적인 데이터 구조로, 본질적으로 트리 구조와 동일합니다.
트리에 비해 그래프는 닫혀 있습니다. 트리 구조는 그래프 구조의 전신이라고 볼 수 있습니다. 형제 노드나 자식 노드 사이의 수평 연결을 트리 구조에 적용하면 그래프 구조를 만들 수 있습니다.
Tree는 회사의 조직 구조와 같이 일대다 데이터 구조를 위에서 아래로 설명하는 데 적합합니다.
그래프는 복잡한 그룹 사회적 관계와 같이 보다 복잡한 다대다 데이터 구조를 설명하는 데 적합합니다.
1. 그래프 이론
컴퓨터를 사용하여 현실 세계의 문제를 해결할 때는 현실 세계에서 정보를 저장하는 것 외에도 정보 간의 관계를 올바르게 설명해야 합니다.
예를 들어 지도 프로그램을 개발할 때 도시 간의 관계나 도시 안의 도로를 컴퓨터에서 정확하게 시뮬레이션해야 합니다. 이를 토대로 한 도시에서 다른 도시로, 또는 지정된 출발지에서 목적지까지의 최적 경로를 계산하는 데 알고리즘을 사용할 수 있습니다.
비슷하게 항공 노선 지도, 기차 노선 지도, 소셜 커뮤니케이션 지도가 있습니다.
그래프 구조는 위에서 설명한 것처럼 현실 세계의 정보 간의 복잡한 관계를 효과적으로 반영할 수 있습니다. 이 알고리즘을 사용하면 비행 경로의 최단 경로, 기차 경로의 최상의 환승 계획, 사회적 관계에서 누구와 가장 좋은 관계를 맺고 있는지, 결혼 네트워크에서 누구와 가장 잘 맞는지 쉽게 계산할 수 있습니다. ..
1.1 그래프의 개념
정점: 정점은 노드라고도 하며, 그래프는 정점의 집합이라고 볼 수 있습니다. 정점 자체에는 데이터 의미가 있으므로 정점은 "페이로드"라는 추가 정보를 전달합니다.
정점은 도시, 장소 이름, 역 이름, 현실 세계의 사람들이 될 수 있습니다... 모서리에는 방향이 있을 수도 있고 방향이 없을 수도 있습니다. 방향 모서리는 단방향 모서리와 양방향 모서리로 나눌 수 있습니다.
아래 그림에 표시된 것처럼 (항목 1)과 (정점 2) 사이의 가장자리에는 한 방향만 있습니다(화살표는 방향을 나타냄). 
를 단방향 가장자리
(정점 1)과 (정점 2) 사이의 가장자리에는 두 방향(양방향 화살표)이 있으며, 를 양방향 가장자리라고 합니다.
도시 간의 관계는 양방향 우위입니다.
Weight: Edge에 값 정보를 추가할 수 있으며, 추가된 값을
weight라고 합니다. 가중치 가장자리는 한 정점에서 다른 정점으로의 연결 강도를 나타냅니다. 
가장자리는 정점 간의 관계를 나타내고 가중치는 연결의 차이를 나타냅니다.
경로:
먼저 현실 세계의 경로 개념을 이해하세요
예: 한 도시에서 다른 도시로 운전하려면 먼저 경로를 결정해야 합니다. 즉, 출발지에서 목적지까지 통과해야 하는 도시들이죠? 몇 마일 정도 걸릴까요?
경로는 가장자리로 연결된 일련의 정점이라고 말할 수 있습니다. 경로가 두 개 이상 있으므로 한 항목 지점에서 다른 항목 지점으로의 경로 설명은 한 유형을 참조하지 않습니다.
그래프 구조에서 경로를 계산하는 방법은 무엇입니까?
비가중 경로의 길이는 경로의 가장자리 수입니다.가중치 경로의 길이는 경로에 있는 가장자리 가중치의 합입니다.
- 위 그림과 같이 (꼭지점 1)에서 (꼭지점 3)까지의 경로 길이는 8입니다.
-
루프:
시작점에서 시작하여 최종적으로 시작점(끝점도 시작점임)으로 돌아오면 루프가 형성됩니다. 위와 같이 는 반지입니다.
요약하면 그래프는 다음 범주로 나눌 수 있습니다. (V1, V2, V3, V1)
유향 그래프:
방향 모서리가 있는 그래프를 유향 그래프라고 합니다.무방향 그래프: 변에 방향이 없는 그래프를 무방향 그래프라고 합니다.
가중 그래프: 모서리에 가중치 정보가 있는 그래프를 가중치 그래프라고 합니다.
비순환 그래프: 순환이 없는 그래프를 비순환 그래프라고 합니다.
방향성 비순환 그래프: DAG라고 하는 주기가 없는 방향성 그래프입니다.
- 1.2 그래프의 정의
그래프의 특성에 따라 그래프 데이터 구조에는 최소한 두 가지 유형의 정보가 포함되어야 합니다.
모든 꼭짓점은 여기에서 V로 표시되는 정보 집합을 형성합니다(예를 들어 지도 프로그램에서 모든 도시는 꼭짓점 집합으로 구성됩니다).
모든 모서리는 여기서 E(도시 간 관계 설명)로 표시되는 집합 정보로 구성됩니다.
가장자리를 어떻게 설명하나요?
가장자리는 아이템 포인트 간의 관계를 나타내는 데 사용됩니다. 따라서 가장자리에는 3개의 메타데이터(시작점, 끝점, 가중치)가 포함될 수 있습니다. 물론 가중치는 생략할 수 있지만, 일반적으로 그래프를 연구할 때 가중치 그래프를 가리킨다.
G를 사용하여 그래프를 표현하는 경우G = (V, E)입니다. 각 모서리는(fv, ev)튜플이나(fv, ev, w)삼중항으로 설명할 수 있습니다.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)}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 '[编号为 {0}，名称为 {1} ] 的顶点'.format(self.v_id, self.v_name)顶点类中
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 = [] # 暂省略……初始化方法用来初始化图中的数据类型：
一维列表
vert_list保存所有顶点数据。二维列表
matrix保存顶点与顶点之间的关系数据。queue_stack使用列表模拟队列或栈，用于后续的广度搜索和深度搜索。怎么使用列表模拟队列或栈？
列表有
append()、pop()2 个很价值的方法。append()用来向列表中添加数据，且每次都是从列表最后面添加。pop()默认从列表最后面删除且弹出数据，pop(参数)可以提供索引值用来从指定位置删除且弹出数据。使用 append() 和 pop() 方法就能模拟栈，从同一个地方进出数据。
使用 append() 和 pop(0) 方法就能模拟队列，从后面添加数据，从最前面获取数据
searchPathfv는 시작점을 나타내고,ev는 끝점을 나타냅니다. 그리고fv,ev데이터는V컬렉션에서 참조되어야 합니다.
위의 그래프 구조는 다음과 같이 설명할 수 있습니다. 🎜 """ 添加新顶点 """ 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 += 11.3 그래프의 추상 데이터 구조
🎜적어도 그래프의 추상 데이터 설명에 포함되어야 하는 메소드: 🎜- 🎜
그래프 ( ): 새 그래프를 만드는 데 사용됩니다. 🎜 - 🎜
add_vertex( vert ): 그래프에 새 노드를 추가합니다. 매개변수는 노드 유형의 개체여야 합니다. 🎜 - 🎜
add_edge(fv, tv): 2개의 항목 포인트 간의 가장자리 관계를 설정합니다. 🎜 - 🎜
add_edge(fv,tv,w): 두 항목 포인트 사이에 가장자리를 설정하고 연결 가중치를 지정합니다. 🎜 - 🎜
find_vertex( key): 키워드 키를 기준으로 그래프에서 정점을 찾습니다. 🎜 - 🎜
find_vertexs( ): 모든 정점 정보를 쿼리합니다. 🎜 - 🎜
find_path(fv,tv): 한 꼭지점에서 다른 꼭지점까지의 경로를 찾습니다. 🎜
2. 그래프 저장소 구현
🎜두 가지 주요 그래프 저장소 구현이 있습니다: 인접 행렬과 링크 목록. 이 기사에서는 주로 인접 행렬을 소개합니다. 🎜2.1 인접 행렬
🎜정점 간의 관계를 저장하려면 2차원 행렬(배열)을 사용하세요. 🎜🎜예를 들어graph[5][5]는 5개의 꼭지점의 관계형 데이터를 저장할 수 있습니다. 행 번호와 열 번호는 v번째 행과 wth가 교차하는 셀의 값을 나타냅니다. 열은 시작점을 나타냅니다.grap[2][3]=6과 같이 정점 v에서 정점 w까지의 가장자리 가중치는 C2 정점과 D3 정점이 연결되어 있음을 의미합니다. , 가중치는 6🎜🎜🎜🎜인접 행렬의 장점 간단하고 해당 정점이 연결되어 있음을 명확하게 나타낼 수 있습니다. 모든 정점 쌍이 연결되어 있는 것은 아니기 때문에 행렬에는 종종 "희소 행렬"이라고 불리는 사용되지 않는 공간이 많이 있습니다. 🎜🎜행렬은 모든 정점이 다른 정점과 관계가 있을 때만 채워집니다. 그래프 구조 간의 관계가 너무 복잡하지 않은 경우 이 구조를 사용하여 그래프 데이터를 저장하면 많은 공간이 낭비됩니다. 🎜🎜인접행렬은 인터넷상의 웹페이지 간의 링크, 사회계 사람들 간의 사회적 관계 등 복잡한 관계를 갖는 그래프 구조를 표현하는데 적합합니다...🎜2.2 인접행렬 구현을 위한 인코딩
🎜 정점 자체가 데이터 의미를 갖기 때문에 정점 유형을 먼저 정의해야 합니다. 🎜🎜🎜Vertex 클래스: 🎜🎜''' 添加节点与节点之间的边， 如果是无权重图，统一设定为 1 ''' 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 ''' 添加有权重的边 ''' 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🎜vertex 클래스에서v_id와v_name은 이해하기 쉽습니다.방문함을 추가하는 이유는 무엇입니까? 🎜🎜이 변수는 반복 검색 계산을 피하기 위해 경로 검색 과정에서 정점 검색 여부를 기록하는 데 사용됩니다. 🎜🎜🎜그래프 클래스: 🎜그래프 클래스에는 다양한 메서드가 있는데 여기서는 하나씩 소개하겠습니다. 🎜🎜🎜초기화 방법🎜🎜''' 根据节点编号返回节点 ''' def find_vertex(self, v_id): if v_id >= 0 or v_id <= self.v_nums: # 节点编号必须存在 return [tmp_v for tmp_v in self.vert_list if tmp_v.v_id == v_id][0]🎜초기화 방법은 그래프의 데이터 유형을 초기화하는 데 사용됩니다. 🎜🎜1차원 목록vert_list는 모든 정점 데이터를 저장합니다. 🎜🎜2차원 목록행렬은 정점 간의 관계 데이터를 저장합니다. 🎜🎜queue_stack목록을 사용하여 후속 폭 및 깊이 검색을 위한 대기열 또는 스택을 시뮬레이션합니다. 🎜🎜🎜목록을 사용하여 대기열이나 스택을 시뮬레이션하는 방법은 무엇입니까? 🎜🎜🎜이 목록에는append()및pop()이라는 두 가지 중요한 메서드가 있습니다. 🎜🎜append()는 목록에 데이터를 추가하는 데 사용되며, 매번 목록의 끝에서부터 추가됩니다. 🎜🎜pop()은 기본적으로 목록 끝에서 데이터를 삭제하고 팝합니다.pop(매개변수)는 지정된 위치에서 데이터를 삭제하고 팝하는 인덱스 값을 제공할 수 있습니다. . 🎜🎜append() 및 pop() 메서드를 사용하여 스택을 시뮬레이션하고 동일한 위치에서 데이터를 입력하고 종료합니다. 🎜🎜append() 및 pop(0) 메서드를 사용하여 대기열을 시뮬레이션하고, 뒤에서 데이터를 추가하고, 앞에서 데이터를 가져옵니다.🎜🎜searchPath: 너비 또는 너비에 사용되는 데이터를 저장하는 데 사용됩니다. 깊이 우선 경로 검색 결과입니다. 🎜🎜🎜새 섹션(상단) 지점을 추가하는 방법: 🎜🎜""" 添加新顶点 """ 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上述方法注意一点，节点的编号由图内部逻辑提供，便于节点编号顺序的统一。
添加边方法
此方法是邻接矩阵表示法的核心逻辑。
''' 添加节点与节点之间的边， 如果是无权重图，统一设定为 1 ''' 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 ''' 添加有权重的边 ''' 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添加边信息的方法有 2 个，一个用来添加无权重边，一个用来添加有权重的边。
查找某节点
使用线性查找法从节点集合中查找某一个节点。
''' 根据节点编号返回节点 ''' def find_vertex(self, v_id): if v_id >= 0 or v_id <= self.v_nums: # 节点编号必须存在 return [tmp_v for tmp_v in self.vert_list if tmp_v.v_id == v_id][0]查询所有节点
''' 输出所有顶点信息 ''' def find_only_vertexes(self): for tmp_v in self.vert_list: print(tmp_v)此方法仅为了查询方便。
查询节点之间的关系
''' 迭代节点与节点之间的关系（边） ''' def find_vertexes(self): for tmp_v in self.vert_list: edges = self.matrix[tmp_v.v_id] for col in range(len(edges)): w = edges[col] if w != 0: print(tmp_v, '和', self.vert_list[col], '的权重为：', w)测试代码：
if __name__ == "__main__": # 初始化图对象 g = Graph(5) # 添加顶点 for _ in range(len(g.matrix)): v_name = input("顶点的名称（ q 为退出）：") if v_name == 'q': break v = Vertex(v_name) g.add_vertex(v) # 节点之间的关系 infos = [(0, 1, 3), (0, 3, 5), (1, 2, 4), (2, 3, 6), (2, 4, 1), (3, 4, 2), (4, 1, 7)] for i in infos: v = g.find_vertex(i[0]) v1 = g.find_vertex(i[1]) g.add_edge(v, v1, i[2]) # 输出顶点及边a print("-----------顶点与顶点关系--------------") g.find_vertexes() ''' 输出结果： 顶点的名称（ q 为退出）：A 顶点的名称（ q 为退出）：B 顶点的名称（ q 为退出）：C 顶点的名称（ q 为退出）：D 顶点的名称（ q 为退出）：E [编号为 0，名称为 A ] 的顶点 和 [编号为 1，名称为 B ] 的顶点 的权重为： 3 [编号为 0，名称为 A ] 的顶点 和 [编号为 3，名称为 D ] 的顶点 的权重为： 5 [编号为 1，名称为 B ] 的顶点 和 [编号为 2，名称为 C ] 的顶点 的权重为： 4 [编号为 2，名称为 C ] 的顶点 和 [编号为 3，名称为 D ] 的顶点 的权重为： 6 [编号为 2，名称为 C ] 的顶点 和 [编号为 4，名称为 E ] 的顶点 的权重为： 1 [编号为 3，名称为 D ] 的顶点 和 [编号为 4，名称为 E ] 的顶点 的权重为： 2 [编号为 4，名称为 E ] 的顶点 和 [编号为 1，名称为 B ] 的顶点 的权重为： 7 '''3. 搜索路径
在图中经常做的操作，就是查找从一个顶点到另一个顶点的路径。如怎么查找到 A0 到 E4 之间的路径长度：
从人的直观思维角度查找一下，可以找到如下路径：
{A0，B1，C2，E4}路径长度为 8。{A0，D3，E4}路径长度为 7。{A0，B1，C2，D3，E4}路径长度为 15。
在路径查找时，人的思维具有知识性和直观性特点，因此不存在所谓的尝试或碰壁问题。而计算机是试探性思维，就会出现这条路不通，再找另一条路的现象。
所以路径算法中常常会以错误为代价，在查找过程中会走一些弯路。常用的路径搜索算法有 2 种：
广度优先搜索
深度优先搜索
3.1 广度优先搜索
先看一下广度优先搜索的示意图：
广度优先搜索的基本思路：
确定出发点，本案例是 A0 顶点。
以出发点相邻的顶点为候选点，并存储至队列。
从队列中每拿出一个顶点后，再把与此顶点相邻的其它顶点做为候选点存储于队列。
不停重复上述过程，至到找到目标顶点或队列为空。
使用广度搜索到的路径与候选节点进入队列的先后顺序有关系。如第 1 步确定候选节点时
B1和D3谁先进入队列，对于后面的查找也会有影响。上图使用广度搜索可找到
A0~E4路径是：{A0，B1，D3，C2，E4}其实
{A0，B1，C2，E4}也是一条有效路径，有可能搜索不出来，这里因为搜索到B1后不会马上搜索C2，因为B3先于C2进入，广度优先搜索算法只能保证找到路径，而不能保存找到最佳路径。编码实现广度优先搜索：
广度优先搜索需要借助队列临时存储选节点，本文使用列表模拟队列。
在图类中实现广度优先搜索算法的方法：
class Graph(): # 省略其它代码 ''' 广度优先搜索算法 ''' def bfs(self, from_v, to_v): # 查找与 fv 相邻的节点 self.find_neighbor(from_v) # 临时路径 lst_path = [from_v] # 重复条件：队列不为空 while len(self.queue_stack) != 0: # 从队列中一个节点（模拟队列） tmp_v = self.queue_stack.pop(0) # 添加到列表中 lst_path.append(tmp_v) # 是不是目标节点 if tmp_v.v_id == to_v.v_id: self.searchPath.append(lst_path) print('找到一条路径', [v_.v_id for v_ in lst_path]) lst_path.pop() else: self.find_neighbor(tmp_v) ''' 查找某一节点的相邻节点，并添加到队列（栈）中 ''' def find_neighbor(self, find_v): if find_v.visited: return find_v.visited = True # 找到保存 find_v 节点相邻节点的列表 lst = self.matrix[find_v.v_id] for idx in range(len(lst)): if lst[idx] != 0: # 权重不为 0 ，可判断相邻 self.queue_stack.append(self.vert_list[idx])广度优先搜索过程中，需要随时获取与当前节点相邻的节点，
find_neighbor()方法的作用就是用来把当前节点的相邻节点压入队列中。测试广度优先搜索算法：
if __name__ == "__main__": # 初始化图对象 g = Graph(5) # 添加顶点 for _ in range(len(g.matrix)): v_name = input("顶点的名称（ q 为退出）：") if v_name == 'q': break v = Vertex(v_name) g.add_vertex(v) # 节点之间的关系 infos = [(0, 1, 3), (0, 3, 5), (1, 2, 4), (2, 3, 6), (2, 4, 1), (3, 4, 2), (4, 1, 7)] for i in infos: v = g.find_vertex(i[0]) v1 = g.find_vertex(i[1]) g.add_edge(v, v1, i[2]) print("----------- 广度优先路径搜索--------------") f_v = g.find_vertex(0) t_v = g.find_vertex(4) g.bfs(f_v,t_v) ''' 输出结果 顶点的名称（ q 为退出）：A 顶点的名称（ q 为退出）：B 顶点的名称（ q 为退出）：C 顶点的名称（ q 为退出）：D 顶点的名称（ q 为退出）：E ----------- 广度优先路径搜索-------------- 找到一条路径 [0, 1, 3, 2, 4] 找到一条路径 [0, 1, 3, 2, 3, 4] '''使用递归实现广度优先搜索算法：
''' 递归方式实现广度搜索 ''' def bfs_dg(self, from_v, to_v): self.searchPath.append(from_v) if from_v.v_id != to_v.v_id: self.find_neighbor(from_v) if len(self.queue_stack) != 0: self.bfs_dg(self.queue_stack.pop(0), to_v)3.2 深度优先搜索算法
先看一下深度优先算法的示意图。
深度优先搜索算法和广度优先搜索算法不同的地方在于：深度优先搜索算法将候选节点放在堆栈中。因栈是先进后出，所以，搜索到的节点顺序不一样。
使用循环实现深度优先搜索算法：
深度优先搜索算法需要用到栈，本文使用列表模拟。
''' 深度优先搜索算法 使用栈存储下一个需要查找的节点 ''' def dfs(self, from_v, to_v): # 查找与 from_v 相邻的节点 self.find_neighbor(from_v) # 临时路径 lst_path = [from_v] # 重复条件：栈不为空 while len(self.queue_stack) != 0: # 从栈中取一个节点（模拟栈） tmp_v = self.queue_stack.pop() # 添加到列表中 lst_path.append(tmp_v) # 是不是目标节点 if tmp_v.v_id == to_v.v_id: self.searchPath.append(lst_path) print('找到一条路径:', [v_.v_id for v_ in lst_path]) lst_path.pop() else: self.find_neighbor(tmp_v)测试：
if __name__ == "__main__": # 初始化图对象 g = Graph(5) # 添加顶点 for _ in range(len(g.matrix)): v_name = input("顶点的名称（ q 为退出）：") if v_name == 'q': break v = Vertex(v_name) g.add_vertex(v) # 节点之间的关系 infos = [(0, 1, 3), (0, 3, 5), (1, 2, 4), (2, 3, 6), (2, 4, 1), (3, 4, 2), (4, 1, 7)] for i in infos: v = g.find_vertex(i[0]) v1 = g.find_vertex(i[1]) g.add_edge(v, v1, i[2]) # 输出顶点及边a print("-----------顶点与顶点关系--------------") g.find_vertexes() print("----------- 深度优先路径搜索--------------") f_v = g.find_vertex(0) t_v = g.find_vertex(4) g.dfs(f_v, t_v) ''' 输出结果 顶点的名称（ q 为退出）：A 顶点的名称（ q 为退出）：B 顶点的名称（ q 为退出）：C 顶点的名称（ q 为退出）：D 顶点的名称（ q 为退出）：E -----------顶点与顶点关系-------------- [编号为 0，名称为 A ] 的顶点 和 [编号为 1，名称为 B ] 的顶点 的权重为： 3 [编号为 0，名称为 A ] 的顶点 和 [编号为 3，名称为 D ] 的顶点 的权重为： 5 [编号为 1，名称为 B ] 的顶点 和 [编号为 2，名称为 C ] 的顶点 的权重为： 4 [编号为 2，名称为 C ] 的顶点 和 [编号为 3，名称为 D ] 的顶点 的权重为： 6 [编号为 2，名称为 C ] 的顶点 和 [编号为 4，名称为 E ] 的顶点 的权重为： 1 [编号为 3，名称为 D ] 的顶点 和 [编号为 4，名称为 E ] 的顶点 的权重为： 2 [编号为 4，名称为 E ] 的顶点 和 [编号为 1，名称为 B ] 的顶点 的权重为： 7 ----------- 深度优先路径搜索-------------- 找到一条路径: [0, 3, 4] 找到一条路径: [0, 3, 1, 2, 4] '''使用递归实现深度优先搜索算法：
''' 递归实现深度搜索算法 ''' def def_dg(self, from_v, to_v): self.searchPath.append(from_v) if from_v.v_id != to_v.v_id: # 查找与 from_v 节点相连的子节点 lst = self.find_neighbor_(from_v) if lst is not None: for tmp_v in lst[::-1]: self.def_dg(tmp_v, to_v) """ 查找某一节点的相邻节点，以列表方式返回 """ def find_neighbor_(self, find_v): if find_v.visited: return find_v.visited = True # 查找与 find_v 节点相邻的节点 lst = self.matrix[find_v.v_id] return [self.vert_list[idx] for idx in range(len(lst)) if lst[idx] != 0]递归实现时，不需要使用全局栈，只需要获到当前节点的相邻节点便可。
위 내용은 Python에서 그래프 너비와 깊이 우선 경로 검색 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!