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:
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....