Untitled
unknown
plain_text
a year ago
2.6 kB
6
Indexable
class Graph: def __init__(self): self.graph = {} def add_edge(self, u, v): if u not in self.graph: self.graph[u] = [] self.graph[u].append(v) def dfs(self, start): visited = set() self._dfs_helper(start, visited) def _dfs_helper(self, vertex, visited): visited.add(vertex) print(vertex, end=' ') if vertex in self.graph: for neighbor in self.graph[vertex]: if neighbor not in visited: self._dfs_helper(neighbor, visited) # Example usage if __name__ == "__main__": g = Graph() g.add_edge('A', 'B') g.add_edge('A', 'C') g.add_edge('B', 'D') g.add_edge('B', 'E') g.add_edge('C', 'F') g.add_edge('C', 'G') print("Depth First Traversal starting from vertex 'A':") g.dfs('A') water jug problem from collections import deque # Define the state of the jugs class State: def __init__(self, jug1, jug2): self.jug1 = jug1 self.jug2 = jug2 def __eq__(self, other): return self.jug1 == other.jug1 and self.jug2 == other.jug2 def __hash__(self): return hash((self.jug1, self.jug2)) # Define the actions possible def actions(state, max_jug1, max_jug2): jug1, jug2 = state.jug1, state.jug2 return [(max(0, jug1 - (max_jug2 - jug2)), min(max_jug2, jug2 + jug1)), (min(max_jug1, jug1 + jug2), max(0, jug2 - (max_jug1 - jug1))), (max_jug1, jug2), (jug1, max_jug2), (0, jug2), (jug1, 0)] # Solve def water_jug(start_state, target, max_jug1, max_jug2): visited = set() queue = deque([(start_state, [])]) while queue: current_state, path = queue.popleft() if current_state == target: return path + [target] visited.add(current_state) for action in actions(current_state, max_jug1, max_jug2): new_state = State(*action) if new_state not in visited: queue.append((new_state, path + [current_state])) visited.add(new_state) return None # Example max_jug1 = 4 max_jug2 = 3 start_state = State(0, 0) target_state = State(2, 0) solution = water_jug(start_state, target_state, max_jug1, max_jug2) if solution: print("Solution found:") for state in solution: print(f"Jug 1: {state.jug1}, Jug 2: {state.jug2}") else: print("No solution found.")
Editor is loading...
Leave a Comment