Q1: What are the
applications of graph ?

Q2: Write down
the applications of  DFS.

Q3: Write down
the applications of BFS.

Q4: Define
connected and strongly connected graph.

Q5: What are the
advantages of DFS over BFS?

Q6: How the
graph can be represented in memory ? Explain with suitable example.

                                      OR

          List the different types of
representation of graphs.

Q7: Discuss the
disadvantages of Dijkstra’s algorithm.

Q8: How many
ways are there to implement Kruskal’s algorithm ?

Q9: How Prim’s
Algorithm is similar to Dijkstra’s algorithm ?

Q10: Prove that
the number of odd degree vertices in a connected graph should be even.

Q11: Number of
nodes  in a complete tree is 10000. Find
it’s depth.

Q12: What is a
graph ? Discuss various types of graphs. Briefly explain few applications of
graph.

                                                OR

 What is graph ? Discuss various terminologies
used in graph.

Q13: Discuss the
various types of representation of graph.

Q14: Write a
short note on graph traversal.

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

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

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

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

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

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

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

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

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

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

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

Q15: Explain
transitive closure.

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

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

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

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

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

                                                OR

          Describe Dijkstra algorithm with
suitable example.

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