[Solved] METCS526 Module6- Run the DFS

Problem 1 ( Run the DFS on the following graph beginning at node G and show the sequence of nodes generated by the search. When you have two or more choices as the next node to visit, choose them in the alphabetical order.

After completing the DFS, classify each edge as a tree edge, a forward edge, a back edge, or a cross edge.

Problem 2 . Run the BFS on the following graph beginning at node I and show the sequence of nodes generated by the search. When you have two or more choices as the next node to visit, choose them in the alphabetical order.

Problem 3 . Run the Dijkstras algorithm on the following graph beginning at node

Problem 3-. After each iteration, show the D values of all nodes (initial D values are shown above each node in red).

Problem 3- Show the shortest path from S to every other node generated by the algorithm

Problem 4Run the Prim-Jarnik algorithm on the following graph beginning at node a

Problem 4-. Show the sequence of nodes in the order they are brought into the cloud. Problem 4-(2). Show the minimum spanning tree T, generated by the algorithm, as a set of edges.

Problem 5 A friend relationship is a binary relation defined for two persons denoted f(p1, p2), where p1 and p2 are two persons. The meaning is that p1 is a friend of p2. Properties of the friend relationship are:

• If f(p1, p2), then f(p2, p1): If p1 is a friend of p2, then p2 is a friend of p
• If f(p1, p2) and f(p2, p3), then f(p1, p3): If p1 is a friend of p2 and p2 is a friend of p3, then p1 is a friend of p

You must write a program named Hw6_P5.java that implements the following requirements.

• Your program must read friend relationships among people from an input file named txt. The format of an input file is shown below:

John, Isobel

Nathan, John

Rebecka, Yorst

Maria, Yorst

Doloris, Maria

Yorst, Doloris

• Your program must store the friend relationships in a (simplified) adjacency matrix, which is a two-dimensional matrix. For example, given the above friend relationships, the corresponding adjacency matrix should be:

Note that in the matrix above, names of persons are shown instead of array indexes for easy illustration.

• Your program must print the adjacency matrix on the screen (to show that the adjacency matrix was correctly constructed), like the one shown above.
• Then, your program must display the following main menu:

Main Menu

Search options:

1. Friends of a person 2. Friend or not?
2. Exit

Enter option number:

• Your program must read an option a user enters and perform the following:
• If the option entered is smaller than 1 or greater than 3, then your program must issue an appropriate error message and redisplay the main menu.
• If the option entered is 1, then your program must prompt the user to enter the name of a person and perform the following o If the name does not exist in the adjacency matrix, then issue an appropriate error message and redisplay the main menu.
  • If the name exists, then display all friends of the person.
  • Redisplay the main menu.
• If the option entered is 2, then your program must prompt the user to enter names of two persons separated by a space and perform the following o If any of the two names does not exist in the adjacency matrix, then issue an appropriate error message and redisplay the main menu.
  • If both names exist, then display Yes if they are friends and No
  • Redisplay the main menu
• If the option entered is 3, then your program must display an appropriate parting message on the screen and terminate the program.

Note that this program can be implemented using many data structures. However, for this assignment, you must use an adjacency matrix to store friend relationships and you may use other additional data structures if you want.

Deliverables

You must submit the following files:

You need to submit the following files:

• pdf: This file must include:
• Answers to problems 1 through 5.
• Discussion/observation of Problem 6: This part must include what you observed and learned from this experiment and it must be substantive.
• java
• Other files, if any.

Combine all files into a single archive file and name it LastName_FirstName_hw6.EXT, where EXT is an appropriate archive file extension, such as zip or rar.