数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究使用深度优先搜索 (DFS) 查找无向图中所有连通分量的 Python 程序
当需要使用深度优先搜索在无向图中查找所有连通分量时，定义一个包含初始化值、执行深度优先搜索遍历、查找连通分量、向图中添加节点等方法的类。可以创建类的实例，访问其方法，并在其上执行操作。
下面是相同内容的演示 -
示例
class Graph_struct:
def __init__(self, V):
self.V = V
self.adj = [[] for i in range(V)]
def DFS_Utililty(self, temp, v, visited):
visited[v] = True
temp.append(v)
for i in self.adj[v]:
if visited[i] == False:
temp = self.DFS_Utililty(temp, i, visited)
return temp
def add_edge(self, v, w):
self.adj[v].append(w)
self.adj[w].append(v)
def connected_components(self):
visited = []
conn_compnent = []
for i in range(self.V):
visited.append(False)
for v in range(self.V):
if visited[v] == False:
temp = []
conn_compnent.append(self.DFS_Utililty(temp, v, visited))
return conn_compnent
my_instance = Graph_struct(5)
my_instance.add_edge(1, 0)
my_instance.add_edge(2, 3)
my_instance.add_edge(3, 0)
print("1-->0")
print("2-->3")
print("3-->0")
conn_comp = my_instance.connected_components()
print("The connected components are :")
print(conn_comp)输出
1-->0 2-->3 3-->0 The connected components are : [[0, 1, 3, 2], [4]]
解释
定义了一个名为“Graph_struct”的类。
定义了一个名为“add_edge”的方法，该方法有助于向树中添加元素。
定义了“DFS_Utility”方法，该方法有助于使用深度优先搜索方法遍历树。
定义了一个名为“connected_components”的方法，该方法有助于确定相互连接的节点。
创建类的实例，并在其上调用方法。
节点显示在控制台上。
连通分量显示为控制台上的输出。
更新于：2021年4月17日
1K+ 次浏览
广告