Analysis of Algorithm chapter 9 : Algorithm on Graph

Which ones are the types of graph representation

• Adjacency Matrix

• Adjacency List

• Edge List

• Vertex List

Which statements about Graph Traversal are TRUE ?

• Stack is usually applied on implementing Depth-First Search

• Stack is usually applied on implementing Breadth-First Search

• Priority Queue is usually applied on implementing Breadth-First Search

• Kahn's Algorithm uses DFS to find the topological sorting

Which one is not Topological sorting of this graph

• D-B-A-C-E

• D-A-B-C-E

• A-B-C-D-E

• B-C-D-A-E

Which statements about Topological sorting are true?

• Kahn's algorithm starts on the node with zero in-degree

• The order of removing in-degree comes from the queue

• Sorting from DFS and Kahn's are usually same.

• Kahn's algorithm is a Greedy algorithm

• It is possible to find alternative sorting if some preferences in algorithm is changed

Based on Prim's algorithm, if the current spanning tree consists of node a and e, which edge will be added to the spanning tree next ?

• ab

• df

• ef

• af

which ones are the correct initializations of Dijkstra's algorithm if the starting node is X

• D[i] = 0 for all node i except X

• D[X] = 0

• prev[X] = 0

• visited[i] = FALSE for all node[i]

To find the shortest path start from node s on the graph with n nodes, which statement are True

• There are n rounds for Dijkstra's algorithm

• The maximum number of round for Bellman-Ford algorithm is n - 1

• The minimum number of round for Bellman-Ford algorithm is 1

• The relaxation occurs when d[i] < d[s] + w[s, i]

This is a distance matrix of graph during step 4 of Floyd-Warshal algorithm. How many relaxations will there be in this step?

(a)  

A* algorithm is used to find the optimal path from the starting point to the finish by calculating the function f(x) = g(x) + h(x). Which statements are True?

• h(x) is defined by the distance from the point x to the finish

• g(x) is defined by the cost of travelling the starting point to the point x

• At each step, the points with the highest f(x) will be chosen for the next step.

• If there are multiple best f(x), the one among these best f(x) with the lowest h(x) will be chosen