무방향 그래프에서 깊이 우선 탐색을 사용하여 연결된 모든 구성 요소를 찾아야 하는 경우 값을 초기화하고, 깊이 우선 탐색을 수행하고, 연결된 구성 요소를 찾고, 그래프에 노드를 추가하는 등의 메서드가 포함된 클래스가 정의됩니다. 클래스의 인스턴스를 생성하고 메서드에 액세스하고 작업을 수행할 수 있습니다.
아래는 동일한 데모입니다 -
예시
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'라는 메서드가 정의되어 있습니다.
-
클래스의 인스턴스가 생성되고 메서드가 호출됩니다.
-
노드가 콘솔에 표시됩니다.
-
연결된 구성 요소는 콘솔에 출력으로 표시됩니다.