19cse212-F-GraphsADT
Submit solution
C++, Python
Points:
20
Time limit:
10.0s
Memory limit:
64M
Author:
Problem types
Allowed languages
You are required the 4 basic functions for graph ADT. The graph G <V,E> will be already given. Along with this the first input to the code is the 'N' number of operations to be performed. The second line takes as input the value for the functions to be implemented as under:
- A - Adjacency Matrix
- B S - Calculates the BFS traversal with S as the starting vertex. Front and back edges are also printed.
- D S - Calculates the DFS traversal with S as the starting vertex. Cross edges are also printed.
- M - It calculates and prints the MST generated using Kruskal's Algorithm
Sample Input:
3
A
B 3
D 3
Sample Output:
( 0 , 4 )
( 0 , 3 )
( 0 , 2 )
( 0 , 1 )
( 1 , 2 )
( 2 , 3 )
( 3 , 4 )
( 3 , 1 )
( 4 , 6 )
...........
...........
...........
Adjacency matrix
0 2 5 16 15 0 0 0 0 0 0
0 0 19 0 0 0 0 0 0 0 0
0 0 0 4 0 0 0 0 0 0 0
0 17 0 0 30 0 0 0 0 0 0
0 0 0 0 0 18 11 0 0 0 0
10 8 22 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 6 0 0 23
Bfs: [5, 1, 0, 2, 4, 3, 6, 10, 7, 9, 8]
Cross edge: [[1, 2], [0, 2], [0, 1], [2, 3], [4, 5], [3, 4], [3, 1], [7, 10], [9, 6], [8, 7]]
Front edges: [[5, 1], [1, 2], [2, 3], [3, 4], [4, 6], [6, 10], [10, 9], [9, 8], [8, 7], [5, 0]]
Back edges: [[7, 10], [9, 6], [6, 7], [4, 5], [3, 1], [0, 4], [0, 3], [0, 2], [0, 1], [5, 2]]
dfs: [5, 1, 2, 3, 4, 6, 10, 9, 8, 7, 0]
Comments