QuestionQuestion

Transcribed TextTranscribed Text

Instructions Implement a basic graph data structure using either an adjacency list or adjacency matrix. Perform either a Depth-First-Search (DFS) or Breadth-Pirst-Search (BFS) algorithm on the graph structure you created. Recall that BFS is more appropriate for an undirected graph and DFS is more appropriate for a directed graph. You do not have to write them yourself, you may take them from some source, but you must reference your source. Utilize the following examples listed below to complete your assignment. 1 should be used as the start node. 1 2 6 4 5 3 1 5 4 3 2 You are to submit a paper written with Microsoft Word that discusses the results of your analysis. It should include the following: A brief introduction of the algorithm(s) that you have selected and how the algorithm(s) compare, if any A discussion of the critical operation that you chose to count with an explanation of why you selected it A Big-o analysis of the algorithm(s) used. Make sure that critical operation count is included with this discussion. Comprehensive Documentation containing Approach, Lessons Learned, and Possible Improvements sub-sections A conclusion that summarizes the important observations of your study

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

Brief Introduction of the Used Algorithm

The selected algorithm that was implemented and analyzed in this project is DFS (stands for Depth-First Search).
The starting point for the implementation was the following reference:
http://shashank7s.blogspot.ro/2011/03/wap-for-dfs-bfs-in-graph.html
It is an iterative version implemented with Stack as data structure for holding the vertices of the graph.
As methodology, DFS starts from a root node (in this case was node 1) and explores the graph as far as possible in all branches before starting to backtrack.


Discussion of Critical Operations

For studying the behavior of the selected algorithm on the graphs provided as examples, were set two parameters that can be considered critical. As usually, one of these represents the actual running time of the algorithm, while the second is the counter of how many times it is called the method getUnvisitedChildNode(). Unvisited child nodes are considered those vertices that are adjacent to an already visited node (with the condition to exist an edge between the already visited node and the children, of course). At a large scale, the number of times the method is appealed offers a clear indication about the amount of basic operations that are executed. At the same time, the number of calls is dependent on the form of the graph as well....
$30.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats