# Untitled

unknown
plain_text
2 months ago
2.6 kB
2
Indexable
Never
```class Graph:
def __init__(self):
self.graph = {}

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):
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()

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]

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]))

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.")
```