Week 10: Exercises

1. Adjacency Matrix to Adjacency List

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

2. Adjacency List to Adjacency Matrix

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

3. Highest Degree

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.

4. Reverse the Direction

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.

5. Connected Graph

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.

6. Mutually Reachable

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 searches.

7. Connected Components

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 searches.

8. On the Path

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 search.

9. Directed Acyclic Graph

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