19cse212-F-GraphsADT


Submit solution

Points: 20
Time limit: 10.0s
Memory limit: 64M

Author:
Problem types
Allowed languages
C++, Python

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

There are no comments at the moment.