Lekcja – Drzewa
mission_control = { 'FC' : ['Engine','Weather','Crew'], 'Engine': ['Engine Temp','Fuel'], 'Engine Temp': [], 'Fuel' : [], 'Weather' : ['Wind', 'Air Temp', 'Clouds'], 'Wind' : [], 'Air Temp' : [], 'Clouds':[], 'Crew': ['Health','Communication'], 'Communication': [], 'Health': [] } status = { 'Engine Temp': True, 'Fuel': True, 'Wind': True, 'Air Temp': True, 'Clouds': True, 'Communication': True, 'Health': True } def can_start(graph, status, start_node): if graph[start_node]: for node in graph[start_node]: if not can_start(graph, status, node): print(f'{start_node} - False') return False print(f'{start_node} - True') return True else: print(f'{start_node} {status[start_node]}') return status[start_node] print(f'Can we start? {can_start(mission_control, status, "FC")}')
Lab
names = ['1 CEO', '2 Cognitive', '2 Systems', '2 Operations','3 Healthcare', '3 Cloud', '3 Research', '3Security', '3 Storage'] structure1 = [ [0,1,1,1,0,0,0,0,0], [0,0,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,1,1], [0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0] ] structure2 = [ [0,1,1,1,0,0,0,0,0], [0,0,0,0,1,1,1,0,0], [0,1,0,0,0,0,0,1,1], [0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0] ] structure3 = [ [0,1,1,0,0,0,0,0,0], [0,0,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,1,1], [0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0] ] # only one starting node def get_root(structure): the_root = None #review all columns for c in range(len(structure)): #chek how many parents the node has number_of_parents = 0 for r in range(len(structure)): number_of_parents += structure[r][c] #if the node hasn't parents, it is the root if number_of_parents == 0: the_root = c break #return found root or none return the_root def is_tree(structure): # get the root, if there is no root, it is not a tree the_root = get_root(structure) if the_root == None: return False #visit all nodes, each node should be visited exactly one time list_visited = [] list_to_visit = [the_root] while list_to_visit: current = list_to_visit.pop(0) #if the node was already visited it is not a tree if current in list_visited: return False list_visited.append(current) #add neighbours of current node for x in range(len(structure)): if structure[current][x] == 1: list_to_visit.append(x) #if we visited all nodes it is a tree return len(list_visited) == len(structure) print('Structure 1:', is_tree(structure1)) print('Structure 2:', is_tree(structure2)) print('Structure 3:', is_tree(structure3))