Determine whether there exists a path in graph G of length L.
Determine whether there exists a path in graph G of length L.
Solution:
If the graph has a cycle, then the graph has a path of any length L.
If the graph does not have a cycle , then we are finding a simple path of length L.
We will use DFS with some modification to find simple path of length L.
For this with every node n, we will maintain a value named maxPath (other than start_time and end_time) which determines path of Maximum value.
We will initialize each nodes of G with maxPath = 0;
So, the steps to find simple path of Lengh L is :
1. Run modified DFS-visit()
2. check each node for the maxPath value.
DFS-visit(u) {
time = time + 1
u.start = time;
for each v <em>belongs-to</em> adj[u]
if ( v.color = WHITE ) {
DFS-visit(v)
if (u.maxPath < v.maxPath + 1 )
u.maxPath = v.maxPath + 1;
}
u.endtime = time + 1;
u.color = BLACK
Consider the problem of determining whether a given undirected graph G=(V,E) contains a trinagle or cycle of length 3
Consider the problem of determining whether a given undirected graph G=(V,E) contains a trinagle or cycle of length 3.
Give o(v^3) algorithm for it.
Solution:
step 1: Run DFS on the given as it is.
step 2: In the DFS-visit of vertice ( say u ) run a modified BFS ( say BFS2).
The algorithm for BFS2 is as following:
BFS2(u) {
foreach v1 belongs to adj[u]
foreach v2 belongs to [adj[v1] - u] { // because we know u must be adjacent of v1. that's why we will not let u create massacre here.
if ( v2 and u are adjacent to each other )
Report ( u,v1,v2) as a cycle or length 3 .
}
}
This problem appears in algorithm design manual by skiena as following
5-17. Consider the problem of determining whether a given undirected graph G = (V,E) contains a triangleor cycle of length 3.
- Give an O( | V | 3) to find a triangle if one exists.
The complexity id v3 because for each vertices BFS2 will run for with v^2 complexity.
Find the node of a graph from which all nodes are reachable
If we have a graph G=(V,E) and all vertices are reachable from vertex s, then our problem is to find such a vertex s.
Solution: Solution to this problem is in DFS of the graph. Before going to the algorithm, we need to consider the following properties of DFS.
i) DFS tree produced by the DFS algorithm is always a tree ( it means that it must be acyclic, whatever the graph is)
Here is the algorithm that reports if a given graph has a vertex from which all other vertex are reachable.
DFS-Visit(u)
time = time + 1;
u.start_time = time;
child= 0;
Color = GRAY;
for each v belongs to adj[u] {
if ( v.color == WHITE ) {
DFS-visit(v);
child = (v.finish_time - v.start_time + 1 ) / 2;
}
}
u.finish_time = time + 1;
u.color = BLACK;
u.child = child + 1; // child include number of nodes this node visits including itself.
if ( u.child == |V| )
## Report u as source vertex ##
In fact, this is the solution for the following problem
5-26. A mother vertex in a directed graph G = (V,E) is a vertex v such that all other vertices G can be reached by a directed path from v.
- Give an O(n + m) algorithm to test whether a given vertex v is a mother of G, where n = | V | and m = | E | .
- Give an O(n + m) algorithm to test whether graph G contains a mother vertex.
Sorting of Pairwise sum
In this problem, we have two list X & Y. we have to take any element x of X and y of Y to make a pair. The problem is to sort the sum of the pair in the ascending order.
if X = {100,110,130} Y = {50,75,125} the sorted pair sum would be
150, 160,175,180,185,205,225.
The code below does this :
class pairwisesum {
public static void main(String [] s) {
int [] X = {100,110,130};
int [] Y = {50,75,125};
int [] index = {0,0,0};
int sum ,next;
for ( int k=0; k<X.length*Y.length; k++) {
sum = 99999;
next = 0;
for (int i=0; i<X.length; i++) {
//System.out.println(index[i]);
if ( X[i] + Y[index[i]] < sum ){
sum = X[i] + Y[index[i]];
next = i;
}
}
index[next] ++;
System.out.println( “” + sum + “::” + next );
}
}
}
ancestor reporting in a tree
S Dasgupta- 3.18 :You are given a binary tree T = (V;E) (in adjacency list format), along with a designated root node r belongs to V . Recall that u is said to be an ancestor of v in the rooted tree, if the path from r to v in T passes through u. You wish to preprocess the tree so that queries of the form “is u an ancestor of v?” can be answered in constant time. The preprocessing itself should take linear time. How can this be done?
Solution:
Let Ancestor[n][n] be an two dimentional array. If there is a query “is u an ancestor of v” our program will answer “yes” if A[u][v] is true otherwise it will report “no”.
Algorithm:
DFS-visit ( u , list){
Process_ancestor();
time = time + 1
u.color = GRAY;
foreach v belongs to adj[u] {
append(list,v);
DFS-visit (v,list);
remove_last_element(); // which will remove v from the end of the list.
}
}
Process_parent ( list ) {
if ( list.size > 1 ) {
for ( i=1; i<=list.size; i++) {
for ( j=i+1; j<=list.size; j++)
ancestor[list[i]][list[j]] = true; // list[i] is a ancestor of list[j]
}
}
}
Process_query( u,v) { // This will answer our question.
if ( ancestor[u][v] == true ) return yes;
return false;
}
Determine cycle in undirected graph in O(v) time.
Observation says, an undirected graph G = ( V,E) will have at most |v-1| edges for it to be acyclic. So, in any undirected graph, if we find more than |v-1| edges we can say that it has a cycle.
So, the solution is :
1. Run DFS on the graph G .
2. It it finds more than |v-1| edges stop the algorithm and assert a cycle.
Modified Dijkstra
Modify Dijkstra algorithm such that if there is more than one shortest path between node u and v ,dijkstra would select the shortest path with minimum nodes. For example if we can reach from u to v in cost S in two different path ( for example u-p-q-r-v and u-a-v both with same cost S) then our modified algorithm should select path u-a-v because it has minimum path weight as well as minimum node in between u and v.
Solution:
We would only modify the RELAX(u,v,w) function in the original Dijkstra algorithm.
Here nc[V] means the smallest count of nodes between source (S) and corresponding node (V). We will initialize nc[s] = 0 for the algorithm.
Modified_relax(u,v,w)
if d[v] < d[u] + w(u,v) {
d[v] = d[u] + w(u,v)
nc[v] = nc[u] + 1
}
else if ( d[v] == d[u] + w(u,v) )
if ( nc[v] < nc[u] + 1 ) { // nc means node count
nc[v] = nc[u] + 1;
}
