Graphs
This chapter explores the graph data structure and its applications in computer science. It covers the definition of graphs, types of graphs, graph representations, graph traversals, and common graph algorithms.
Questions And Solutions.
2079 Chaitra
Define minimum spanning tree. Create a minimum spanning tree for the following graph using Kruskal's algorithm.
Solution
A Minimum Spanning Tree (MST) of a connected, undirected, and weighted graph is a spanning tree that includes all the vertices of the graph using exactly V−1 edges (where V is the number of vertices), with no cycles and the total weight of the edges is minimized. The MST ensures connectivity with the minimum possible cost, forming a tree structure without any closed loops (cycles).
Edges of the graph sorted in increasing order of their weight.
2079 Ashwin
Determine the breadth first and depth first topological sorting for the following graph.
Breadth First Topological Sorting
Depth First Topological Sorting
2078 Poush
Differentiate between breadth first and depth first search algorithms.Create a minimum spanning tree for the following graph using Kruskal's algorithm.
Solution
| BFS (Breadth-First Search) | DFS (Depth-First Search) |
|---|---|
| It explores all neighbors of a node level by level before moving deeper | It explores all adjacent vertices of a node one by one, diving deep into each vertex's reachable nodes before backtracking. |
| BFS uses a Queue (FIFO). | DFS uses a Stack (explicit or recursion). |
| BFS is more suitable for searching vertices closer to the given source. | DFS is more suitable when there are solutions away from source. |
Edges of the graph sorted in increasing order of their weight.
2078 Baisakh
Define minimum spanning tree with suitable example. Show step by step solution to find the minimum spanning tree of the graph below using Prim's Algorithm.
Solution
A Minimum Spanning Tree (MST) of a connected, undirected, and weighted graph is a spanning tree that includes all the vertices of the graph using exactly V−1 edges (where V is the number of vertices), with no cycles and the total weight of the edges is minimized. The MST ensures connectivity with the minimum possible cost, forming a tree structure without any closed loops (cycles).
Example
Minimum Spanning Tree of the given graph.
2077 Chaitra
Define depth first and breadth first traversal. Construct the minimum spanning tree(MST) for the given graph using Krushkal's algorithm.
Solution
Depth First Search (DFS) is a graph traversal algorithm that explores all adjacent vertices of a node one by one, diving deep into each vertex's reachable nodes before backtracking.
Breadth First Search (BFS) is a graph traversal algorithm that explores all neighbors of a node level by level before moving deeper. It uses a queue to process nodes in the order they are discovered.
Edges of the graph sorted in increasing order of their weight.
2071 Bhadra
a. Define graph with its different representation techniques.
Solution
A Graph is a non-linear data structure used to represent a set of objects (nodes or vertices) and their connections (edges). Graphs are widely used to model relationships in networks, such as social networks, transportation systems, web page links, and more.
Graph Representation Techniques:
- Adjacency Matrix
An Adjacency Matrix is a representation of a graph using a 2D matrix, where the rows and columns correspond to the vertices (nodes) of the graph. Adjacency Matrix Ag of a graph G=(V,E) is a nxn matrix where,
Ag = [Aij] = 1 if there is an edge between i and j,
0 if there is no edge between i and j
n is the number vertices.
Example:
- Adjacency List An Adjacency list is representation of a graph, where each vertex is associated with a list of its neighboring vertices.In this representation, we store a graph as a linked structure.
Example:
b. Discuss Dijkstra's shortest path algorithm. Find the shortest paths for given graph with sourcee node 'F' using Dijkstra's algorithm.
Solution
Dijkstra Algorithm is a graph-based shortest path algorithm used to solve the single-source shortest path problem for a graph with non-negative edge weights.It uses a priority queue (often implemented with a min-heap) to always expand the least costly node first, ensuring optimality. The algorithm is widely used in network routing, GPS navigation, and various optimization problems. Its time complexity is O((V + E) log V) using a priority queue and an adjacency list.
