Consider the following case: The FBI recently arrested a famous criminal of name

Question

Consider the following case: The FBI recently arrested a famous criminal of name John. In their investigations, they found out that John transferred the "dirty money" to someone called Lucy, in Switzerland, where she safely concealed the dirty money far from the reach of the American investigators. The FBI can only recover John's criminal money if they can prove that the money deposited by Lucy came in fact from John. The problem however, is that John used a network of N accomplices (to make very hard for the FBI to track his relationship with Lucy).

The FBI manages to crack down the network of John's accomplices (see below). The easy part in tracking John-Lucy transfer is that each individual in the network could only transfer money to a "close friend" OR a "friend of a close friend" (like indicated by the edges in the graph below).

Because time is short to recover the money (before it is withdrawn from Switzerland), the FBI needs to know how many paths the money could have followed between John and Lucy (so it can start a formal crack down on the individual bank accounts). The FBI requests your help.

They ask you to design an algorithm (pseudocode or succinct verbal description) that calculates the TOTAL NUMBER OF PATHS between John and Lucy, given that each of the N individual in the network of accomplices could only have transferred the money to a friend or a friend of a friend (For example, John could transfer to Mary or Bill; Mary can transfer to Bill or Jane, and so on...).
*Tip: One path may be {John, Mary, Bill, Jane, ...., Lucy}. Another may be {John, Bill, ..., Lucy}. Yet another may be {John, Mary, Jane, ...., Lucy}. So far, I listed 3 paths between John-Lucy (of course, abstracting the possible many individuals represented by the ellipsis (...)).

Explanation / Answer

Here we can use graph path. we need to fine out all path that connect the edges of John and Lucy.

So there is two algorithm for this.

1. BFS (Breadth First Search)

2.DFS(Depth First Search)

So we will disucss DFS here.

Start the traversal from source. Keep storing the visited vertices in an array say ‘path[]’. If we reach the destination vertex, print contents of path[]. The important thing is to mark current vertices in path[] as visited also, so that the traversal doesn’t go in a cycle.

Algorithm:

//V is total numbe of people in Reacket
// Prints all paths from john to Lucy
void Graph::printAllPaths(john, Lucy)
{
// Take a boolean array visited of V lenght and Mark all the vertices as not visited

// Create an array path to store paths of names
   // Initialize path[] as empty ad take a path_index to 0

// Call the recursive helper function to print all paths
   printAllPathsUtil(john, Lucy, visited, path, path_index);
}

// A recursive function to print all paths from "john" to "Lucy".
// visited[] keeps track of vertices in current path.
// path[] stores actual vertices and path_index is current
// index in path[]
void Graph::printAllPathsUtil(String Souecr, String destination, bool visited[],String path[], int &path_index)
{
// Mark the current node as visited and store it in path array
   //increse the size of path_index by 1

// If current vertex is same as destination, then print
// current path[]

else // If current vertex is not destination
{
// Recur for all the vertices adjacent to current vertex
list<String>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
if (!visited[*i])
printAllPathsUtil(*i, "Lucy", visited, path, path_index);
}

// Remove current vertex from path[] and mark it as unvisited and decrese the path_index by 1

}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.