트리의 모든 노드의 합을 구해야 할 때 클래스를 생성하고 루트 노드를 설정하고 트리에 요소를 추가하고 특정 요소를 검색하고 트리의 요소를 추가하는 메소드를 포함합니다. 합계 등을 찾습니다. 이러한 메서드에 액세스하고 사용하기 위해 클래스의 인스턴스를 만들 수 있습니다.
아래는 동일한 데모입니다 -
예
from collections import deque
def add_edge(adj: list, u, v):
adj[u].append(v)
adj[v].append(u)
def detect_cycle(adj: list, s, V, visited: list):
parent = [-1] * V
q = deque()
visited[s] = True
q.append(s)
while q != []:
u = q.pop()
for v in adj[u]:
if not visited[v]:
visited[v] = True
q.append(v)
parent[v] = u
elif parent[u] != v:
return True
return False
def cycle_disconnected(adj: list, V):
visited = [False] * V
for i in range(V):
if not visited[i] and detect_cycle(adj, i, V, visited):
return True
return False
if __name__ == "__main__":
V = 5
adj = [[] for i in range(V)]
add_edge(adj, 0, 1)
add_edge(adj, 1, 2)
add_edge(adj, 2, 0)
add_edge(adj, 2, 3)
add_edge(adj, 2, 1)
if cycle_disconnected(adj, V):
print("There are 5 vertices in the graph")
print("0-->1")
print("1-->2")
print("2-->0")
print("2-->3")
print("2-->1")
print("Is there a cycle ?")
print("Yes")
else:
print("There are 5 vertices in the graph")
print("0-->1")
print("1-->2")
print("2-->0")
print("2-->3")
print("2-->1")
print("Is there a cycle ?")
print("Yes")
print("No") 출력
There are 5 vertices in the graph 0-->1 1-->2 2-->0 2-->3 2-->1 Is there a cycle ? Yes
설명
-
필요한 패키지를 가져옵니다.
-
그래프에 노드를 추가하는 데 도움이 되는 'add_edge'라는 또 다른 메서드가 정의되어 있습니다.
-
그래프의 구성 요소가 연결될 때 사이클이 형성되는지 여부를 판단하는 데 도움이 되는 'detect_cycle'이라는 메서드가 정의되어 있습니다.
-
'cycle_disconnected'라는 또 다른 메서드가 정의되어 사이클이 연결된 사이클인지 여부를 판단하는 데 도움이 됩니다.
-
요소는 'add_edge' 메소드를 사용하여 그래프에 추가됩니다.
-
콘솔에 표시됩니다.
-
'cycle_disconnected' 메소드가 호출되고 콘솔에 출력이 표시됩니다.