Write a function that takes a undirected graph in adjacency matrix representation, and returns the same graph in adjacency list representation. Assume that the graph's vertices are numbered from 0 to (V – 1).
Write a function that takes a undirected graph in adjacency list representation, and returns the same graph in adjacency matrix representation. Assume that the graph's vertices are numbered from 0 to (V – 1).
Write a function that takes an undirected graph in adjacency matrix representation, with integer vertex ids. The function should returns the highest degree of any vertex.
Write a functon that takes a directed graph G in adjacency list representation, with integer vertex ids. The function should return a graph that is like G, but in which all edges point in the opposite direction.
Write a function that takes an undirected graph in adjacency matrix representation, with integer vertex ids. The function should return True if the graph is connected, i.e. there is some path between every pair of vertices.
Write a function that takes a directed graph in adjacency list representation and two integer vertex ids v and w.The function should return True if v and w are mutually reachable, i.e. there is some path from v to w and also from w to v. Use one or more depth-first or breadth-first searches.
We may divide any graph into a set of connected components, which are connected subgraphs such that there is no path between any two of them.
Write a function that takes an undirected graph in adjacency list representation and returns the number of connected components in the graph. Use a series of depth-first or breadth-first searches.
Write a function that takes a graph that is a tree, i.e. a connected, undirected, acyclic graph. The function should also take three vertex ids v, w, and x. The function should return true if w is between v and x, i.e. on the (unique) path that leads from v to x. Use a depth-first or breadth-first search.
Suppose that we run a depth-first search on a directed acyclic graph, i.e. a directed graph with no cycles. And suppose that we omit the visited set from our implementation. It might look like this:
def dfs(graph, start):
def visit(v):
print('visiting', v)
for w in graph[v]:
visit(w)
visit(start)Is the search guaranteed to terminate, or might it go into an infinite loop? If it will terminate, is the search guaranteed to run in O(V + E)?
In the lecture, we wrote a function that performs a breadth-first search of a graph, searching for a shortest path from a given start vertex to some goal vertex. It returns a list of all vertices on the path. Our function worked by using a dictionary that maps each vertex to its predecessor.
Modify this function so that each queue element is a Node object holding a vertex ID plus a link to a parent Node. When the function finds the goal, it can construct the path by following links between Node objects. With this modification, the predecessor dictionary will no longer be necessary.
Write a program that reads a rectangular maze from standard input in the following format, where '#' represents a wall:
######## # # # # # # # # # # ## ## # ########
The maze will be surrounded by walls.
The program should print True if the maze is connected, i.e. every two empty squares in the maze are connected by some path. Otherwise print False.
Write a function that takes a 2-dimensional array of booleans representing a maze. There will be no wall in the upper-left or lower-right corner.
The procedure should print out the maze, indicating the shortest path from the upper-left corner to the lower-right corner. For example, the output might look like this:
..###### #.# # #.# # # #...# # ## ....# ######..
If no such path exists, print the maze without any path.
Consider a limping knight on a chessboard. On odd moves (including the first move), it moves like a pawn, i.e. one square forward (or stays in place if it is at the top of the board). On even moves, it moves like a normal knight in chess. Write a function limping_dist(start, end) that returns the smallest number of moves that the knight must make to go from a given starting square to a given ending square. Assume that squares are pairs of coordinates, i.e. (1, 1) is the upper-left corner of the chessboard and (8, 8) is the lower-right corner.
Write a function solve(start, goal, f) that can search any state space. solve() should take three arguments: a start state, a goal state, and a function f that computes the neighbors of any state. solve() should find the shortest possible path from the start state to the goal state, and should print out the sequence of states along this path, with one state per line. If no solution is possible, it should print 'no path'.
We have three jugs with capacity 8, 5, and 3 liters. Initially the first jug is full of water, and the others are empty.
We can pour water between the jugs, but they have no markings of any sort, so we can pour between two jars only until one of them becomes full or empty.
What sequence of moves can we make so that the jugs will hold 4, 4, and 0 liters of water, respectively?
Write a program that can find the shortest possible sequence.
Three missionaries and three cannibals are on the west bank of a river. They have a canoe that can hold two people, and they all must cross to the east bank of the river. There may never be more cannibals than missionaries on either side of the river, or the cannibals will eat the missionaries. Further, the canoe must have at least one person on board to cross the river. Write a program to find and print a sequence of crossings that will take the party safely across.