CSE2135 - Data Structure¶

Graphs and Their Applications¶

Q6(a) [4]: Define the following term with necessary example: (i) Graph, (ii) Multigraph and (iii) Directed Graph.

Q6(a) [4]: Write down the Depth-First Search algorithm of graph.
Q6(b) [4]: Find BFS for the following graph using 'A' as the starting node and 'G' is the destination.

Q6(c) [4]: Construct an adjacent matrix and adjacent list for the following directed graph.

Q6(a) [1+2]: What is graph? List the real-world applications of graphs.
Q6(b) [4]: Demonstrate the adjacency matrix and linked list representation of the following graph:

Q6(c) [3+4]: What is BFS and DFS? Find all the possible path which is reachable from E for following graph [use DFS algorithm].

Q6(a) [3]: Explain Depth First Search and Breadth First Search algorithm with example.
Q6(b) [3]: Construct an adjacent matrix and adjacent list for the following directed graph.

Q6(c) [5]: Find all the possible path which is reachable from A for following graph [use DFS algorithm].

Q6(a) [2]: Which of the multigraphs in figure are (i) connected, (ii) loop-free, and (iii) graphs.

Q6(b) [7]: Suppose the graph G represents the daily flights between cities of some airlines, and, suppose we want to fly from city A to city J with the minimum number of stops. Find out the minimum path P from A to J using breadth first search (BFS) algorithm.

Q6(c) [2+2]: How are graphs represented in memory of a computer? Give relative merits and demerits of these representation schemes.
Q6(d) [1x4]: Define the following terminologies with example: (i) Digraph; (ii) Weighted Graph; (iii) Self loop; (iv) Parallel edges.
Q7(a) [3+2]: Write an algorithm to perform breadth first search (BFS). Compare the BFS and DFS search technique.
Q7(c) [2+3]: What is graph traversal? Write an appropriate algorithm for graph traversal.