Apply DFS algorithm to find a spanning tree of the following graph. Also find all the fundamental cycles of the spanning tree.
We first interpret the graph (vertices are labeled ( {1,2,3,4,6,7,8,9} ); there is no vertex 5). Edges present in the graph (from the figure): Left part [ (1,2), (1,3), (2,3), (2,4), (3,4) ] Middle–right part [ (4,6), (6,7), (7,9), (6,9), (6,8), (8,9), (4,8) ] --- ## 1. DFS Spanning Tree Assume: * Start vertex = 1 * _____ ___ ______ __________ ________ ____ ____ ___ __________.
____ ____ _______ ________ ______.
____ _________ _________ ________ ______ _____.
_________ ___ __________ ________ ________ __________ _____ ______ _____ ____ _________ _______.
____ _____ ______ ______ __________ ____ ______ ______.
_________ _____ __________ _________ ___.
______ _______ ____ ____ __________.
______ ______ _________ _____ _________.
_______ __________ ________ ___ ___ ______ ________ _____.
__________ _______ ______ ____ __________ ____ _____ ____ _____.
_______ _____ ____ _________ _____ _________ ___.
_____ _______ _________ ___ ____ ________ ________ __________ ____ ________ _______ _______.
___ _______ ________ _________ ________ _________.
_________ _____ _______ _____ _____ ____ _____.
___ _____ ______ _________ ____ ________ __________ _________ ________ _______ _______ ___.
___ __________ ____ _____ __________ _______ _________ ________ _______.
________ _________ _______ ___ __________ _______ __________ __________ ____.
__________ _______ _____ _______ _____ __________ ________ ______ _____ ___.
_______ _________ ___ ________ _____ ___ ____.
____ ______ __________ _____ ________ _______ ____ _____ _______ ____ _____ _____.
________ _________ _____ _______ _____ ____ _________.
_____ _____ ______ __________ _____ __________ __________ __________ _____ _________ __________.
_________ _______ ______ ________ ____ ____.
___ ____ _________ __________ _______.
____ ___ ______ _________ ___ ____ _________ __________ ________ _______ _______ ____.
___ _____ _____ _____ ___ ______ _______ ____ _______.
______ ____ ___ _________ _____ _____ _____ _________.
________ ___ _____ _____ _________ _________ ________.
Get Full Answer on WhatsApp
Apply DFS algorithm to find a spanning tree of the following graph. Also find all the fundamental cycles of the spanning tree.
Use Kruskal's algorithm to find a minimal spanning tree in the graph given below
With the help of an example, explain the following:
i) Algorithm,
ii) Input and output for an algorithm
iii) Running time of an algorithm (5)
b) Illustrate the operations of partition in quick sort on the array
.
Write an algorithm to find the first two largest numbers in an in array of integers. For example, given the input ,2 ,3 ,7 − ,4 ,1,5 the algorithm should output ,7 .5 State precisely a loop invariant for you algorithm. Prove that your loop invariant holds and hence conclude that your algorithm works.
Construct a MAXHEAP tree on the following list of numbers
15, 22, 7, 10, 43, 52 13, 16,
Taking v1 as the root, find a spanning tree of the following graph using the breadth first search (BFS) algorithm.
Determine an LCS of (1, 1, 1, 1, 0, 1, 1, 0, 1, 0) and (1, 1, 1, 0, 0, 1, 1, 0, 1, 0).