# Unit 4 Long answer Important Questions of Data Structure

graph ? Discuss various types of graphs. Briefly explain few applications of

graph.

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.