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.
Write a function that takes a directed graph in adjacency list representation and two integer vertex ids v and w, and returns the length of the shortest path from v to w. If there is no path from v to w, the function should return None.
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.
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.
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.