Show the d and π values that result from running breadth-first search on the directed graph of Figure 22.2(a), using vertex 3 as the source.
Show the d and π values that result from running breadth-first search on the undirected graph of Figure 22.3, using vertex u as the source.
What is the running time of BFS if its input graph is represented by an adjacency matrix and the algorithm is modified to handle this form of input?
用邻接矩阵表示的话,遍历所有的边的时间由O(E)变为O(V^2),因此总运行时间是O(V+V^2)
If the graph is represented by adjancency matrix, then the time of iterating all the edge becomes O(V^2), so the running time is O(V+V^2).
Argue that in a breadth-first search, the value d[u] assigned to a vertex u is independent of the order in which the vertices in each adjacency list are given. Using Figure 22.3 as an example, show that the breadth-first tree computed by BFS can depend on the ordering within adjacency lists.
While traversing adjacency list of a vertex, all the neighbour of the vertex is going to be in the same level, That's why d[u] of any vertex u is independent of the order of the adjacency list.
Suppose that vertex A and B are in same level and vertex C is reachable from both A and B. Then in the BFS tree, whether there will be an edge from A to C or B to C depends on the order of A and B.
Give an example of a directed graph G = (V, E), a source vertex s in V , and a set of tree edges Eπ in E such that for each vertex v in V,the unique path in the graph(V,Eπ) from s to v is a shortest path in G, yet the set of edges Eπ cannot be produced by running BFS on G, no matter how the vertices are ordered in each adjacency list.
Following is the example, the bold edges are in Eπ. Then can not be produced by BFS.
There are two types of professional wrestlers: "good guys" and "bad guys." Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and we have a list of r pairs of wrestlers for which there are rivalries. Give an O(n + r)-time algorithm that determines whether it is possible to designate some of the wrestlers as good guys and the remainder as bad guys such that each rivalry is between a good guy and a bad guy. If is it possible to perform such a designation, your algorithm should produce it.
Bipartite Graph problem.
Run DFS or BFS, the start node we could mark as white. Each time, we encounter a node, if it is not currently colored, we should mark it as the opposite color of current node. Else, check the color with current node. If same, then it is not bipartite graph.
The diameter of a tree T =(V, E) is given by
max d(u,v)that is, the diameter is the largest of all shortest-path distances in the tree. Give an efficient algorithm to compute the diameter of a tree, and analyze the running time of your algorithm.
For all node v, run BFS each, choose the longest shortest path. Or use floyd algorithm to calculate all p-p shortest path.
BFS running time = O(V*(V+E))
floyd running time = O(V^3)
Run BFS twice. For the first time, arbitrarily choose a vertex as the source. The second time, let the vertex with largest d[] be the source.
The diameter of a tree can computed in a bottom-up fashion using a recursive solution. If x is a node with a depth d(x) in the tree then the diameter D(x) must be:
D(x) = max{maxi{D(x.childi)}, maxij{d(x.childi) + d(x.childj)} + 2}, if x is an internal node
0 , if x is a leafSince the diameter must be in one of the subtrees or pass through the root and the longest path from the root must be the depth. The depth can easily be computed at the same time. Using dynamic programming we obtain a linear solution.
Actually, the problem can also be solved by computing the longest shortest path from an arbi- trary node. The node farthest away will be the endpoint of a diameter and we can thus compute the longest shortest path from this node to obtain the diameter. See relevant litterature for a proof of this.
Let G = (V, E) be a connected, undirected graph. Give an O(V + E)-time algorithm to compute a path in G that traverses each edge in E exactly once in each direction. Describe how you can find your way out of a maze if you are given a large supply of pennies.
We can perform a DFS like procedure where each edge has a state among the following: never visited, visited once, visited twice. We never visit an edge that has been visited twice. To ensure we explore all edges we will prioritize edges that have never been traversed over edges that have been traversed once. This way, we will explore edges the second time during backtracking phase of DFS.
Every time we visit an unexplored edge(u, v) we add (u, v) to our path. Every time we backtrack from vertex v to vertex u we add (v, u) to our path.
Given a large supply of pennies, we will use pennies to mark state of an edge as suggested above. We put a penny down on each edge every time we travel it and we will never travel an edge with already two pennies placed. Alternatively we can use absence of penny, head face up, tail face up for keeping track of edges that haven't been explored, explored once and explored twice respectively.
Follow @louis1992 on github to help finish this task.