Untitled
unknown
plain_text
4 years ago
1.1 kB
7
Indexable
graph = [[1], [2, 3], [1, 4, 5], [1, 6], [2], [2], [3, 7, 8], [1, 6], [6]] # Використовує DFS для пошуку циклу в графі (19-21) def dfs(graph, start_vertex): visited = [False for x in graph] distances = [0 for x in graph] vertex_to_visit_queue = [start_vertex] while vertex_to_visit_queue: current_vertex = vertex_to_visit_queue.pop() for neighbour in graph[current_vertex]: if not visited[neighbour]: vertex_to_visit_queue.append(neighbour) distances[neighbour] = distances[current_vertex] + 1 # Перевірка чи вертекси не є сусідами, бо # якщо граф не направлений і ти вернувся від сина до # батька, то це не цикл elif current_vertex not in graph[neighbour]: print('Loop found') return visited[current_vertex] = True return distances print(dfs(graph, 0))
Editor is loading...