Homework answers / question archive / what is to be the running time of the depth-first search algorithm, as a function of the number of nodes ?? ? |??| and edges ?? ? |??|, if the input graph is represented by an adjacency matrix instead of an adjacency list? 2

what is to be the running time of the depth-first search algorithm, as a function of the number of nodes ?? ? |??| and edges ?? ? |??|, if the input graph is represented by an adjacency matrix instead of an adjacency list? 2

Writing

Share With

what is to be the running time of the depth-first search algorithm, as a function of the number of nodes ?? ? |??| and edges ?? ? |??|, if the input graph is represented by an adjacency matrix instead of an adjacency list? 2. After starting your first programming position your colleague asks you for advice on which algorithm they should choose. While your colleague studied programming until SIT232, they did not do SIT221 because they thought it would be too hard, therefore they have no idea how to decide on which algorithm to use. Because you are generous you decide to offer some advice. Their problem requires them to find the shortest path from where a user is currently located to each of the major tourist locations in the city. To solve this your colleague had googled for an algorithm and came across two: Dijkstra’s algorithm, which will solve it in ????? ? ?? ?????? ???, and Floyd’s algorithm, which will take ???????, where |??| ? |??| ?. While you recall studying Dijkstra’s algorithm during your SIT221 unit you have never heard of Floyd’s algorithm. Regardless because your colleague’s Google search had also given the time complexity you feel equipped to provide advice. Discuss what factors your colleague should consider when deciding between the two algorithms and in which circumstances, they should choose one over the other. 3. Given the following graph draw both the Depth-first and Breadth-first search trees that will result if you start at Node A. Note: when selecting between nodes you should use alphabetical order