DST Unit 4 – Graph and Tree questions
Topic : Graph & Graph Traversal (Key Note and Questions)
Key Note:
- A Graph is a non-linear data structure that consist nodes and edges.
- Two nodes are connected with the help of single edge.
- Graph data structure can be represented using Adjacency Matrix and Adjacency List.
- BFS stands for Breadth First Search is a Graph traversal Algorithm.
- DFS stands for Depth First Search is also a Graph traversal algorithm.
Questions
- Q1). What is a graph? Describe various types of graph. Briefly explain few applications of graph.
- Q2). Discuss the various types of representation of graph.
- Q3). Write a note on graph traversal.
- Q4). Explain BFS graph traversal with example.
- Q5). Explain DFS graph traversal with example.
- Q6). Write the difference between BFS and DFS graph traversal.
- Q7). Illustrate the importance of various traversing techniques in graph along with its application.
Topic : Spanning Tree (Key Note and Questions)
Key Note:
- A spanning tree is a subset of any Graph G that contains all vertices minimum possible number of edges.
- Spanning tree does not have any cycle as well as it is not disconnected.
- Minimum spanning tree is a subset of graph that contains all vertices and the sum of edge weight that are connecting to vertices is minimum.
- Prim’s and Kruskal Algorithm is used to find minimum spanning tree.
Questions
- Q1). Write a note on spanning tree and minimum spanning tree.
- Q2). Write the Prim's algorithm to find the minimal spanning tree.
- Q3). Define spanning tree. Find the minimal spanning tree for the following graph using Prim's algorithm.
- Q4). Write the Kruskal's algorithm to find minimum spanning tree.
- Q5). Explain the time complexity of Prim's and Kruskal algorithm.
- Q6). Write a note on path matrix.
- Q7). How path matrix can be determined ? Explain the method.
- Q8). Write and explain Dijkstra's algorithm for finding shortest path.
- Q9). Write down Warshall's algorithm for finding shortest path . Give example.
- Q10). Write a note on activity network.
Latest Uploads on Website
- AVL Tree with explanation
- Radix sort algorithm explanation with example
- Quick Sort Algorithm with explanation
- Bubble sorting algorithm with Bubble sort program in C
- Insertion sort algorithm and program in C
- Selection Sort Algorithm and Program in C
- Linear probing technique explanation with example
- Collision in Hashing and Collision resolution technique
- Hashing in data structure with its types
- Binary search tree operations with Program
- Binary search tree in data structure
- Binary search algorithm in data structure with explanation
- linear search in data structure with Algo and Program