Q2: What is
graph ? Discuss various terminologies used in graph.

Q3: Discuss the
various types of representation of graph.

Q4: Explain
adjacency multi lists.

Q5: Write a
short note on graph traversal.

*Q6: Write and
Explain DFS graph traversal algorithm.

 

                                                OR

Write DFS
algorithm to traverse a graph. Apply same algorithm for the graph given in Fig.
by considering node 1 as starting node.

*Q7: Implement
BFS algorithm to find the shortest path form node A to J.

                                                OR

Explain in
detail about the graph traversal techniques with suitable example.

Q8: Illustrate
the importance of various traversing techniques in graph along with its
applications.

Q9: Define
connected component and strongly connected component. Write an  algorithm to find strongly connected components.

Q10: What do you
mean by spanning tree and minimum spanning tree ?

Q11: Write down
Prim’s algorithm to find out minimal spanning tree.

*Q12: Define
minimum spanning tree. Find the minimal spanning tree for the following graph
using Prim’s algorithm.

Q13: Write
Kruskal’s algorithm to find minimum spanning tree.

Q14: Considering
the following undirected graph.

          a. Find the adjacency list
representation of the graph.

          b. Find the minimum cost spanning tree
by Kruskal’s algorithm.

*Q14: Find the
minimum spanning tree for the following graph using
Prim’s and Kruskal’s algorithm.

*Q15: Discuss
Prim’s and Kruskal’s algorithm. Construct minimum spanning tree for the below given graph using Prim’s   algorithm. (Source node =a)

Q16: Explain
transitive closure.

Q17: Write down
Warshall’s algorithm for finding all pair shortest path.

*Q18: Write the
Floyd Warshall algorithm to compute the all pair   shortest path. Apply the algorithm on following graph.

Q19: Write and
explain Dijkstra’s algorithm for finding shortest path.

                                                OR

          Write and explain an algorithm for
finding shortest path between
any nodes of a given graph.

*Q20: Find out
the shortest path from node 1 to 4 in a given graph using Dijkstra shortest path algorithm.

Q21: Describe
Dijkstra’s algorithm for finding shortest path. Describe its working for the graph given below.

                                                OR

          Describe Dijkstra algorithm with
suitable example.

*Q22: By considering vertex ‘1’ as source vertex, find the shortest paths to all other vertices in the
following graph using Dijkstra’s
algorithm. Show all the steps.