quiz 4 Flashcards
In every iteration, Kruskal’s Algorithm adds a ___ to the partiall constructed MST
New Edge
Which algorithm is/are used to find MST
Kruskals and Prim’s algorithm
If the weighted connected graph has n vertices and m edges,then the minimum spanning tree has
exactly n-1 edges
A minimum spanning tree has _____ cycles?
Zero
A tree which contains all the vertices of the graph is called as
Spanning Tree
In every iteration, Prims Algorithms adds _____ to partially constructed MST
New Vertex
The spanning tree with the minimum sum of weights is called as
Minimum Spanning Tree
A weighted graph can have ____ minimum spanning tree
more than one
Which algorithm uses the minimum priortiy queue
Prims & Huffman
In order to find the least expensive way to connect a set of cities, terminals,computers,which of the following is useful?
Minimum Spanning Tree
In ____ we start with a vertex and then the group all the vertices adjiacent to it. Then we go alphabeticalty or in numeric order to construct a path
BFS
Which graph can have a topological order
Directed, acyclic
Which graph traversal technique is similar to level order traversal
BFS
A vertex having degree 1 is called as
Pendant Vertex
A simple algorithm to find a ____ is to find out any vertex with indegree zero, that is a vertex without any predeccot. we can then add this vertex in an ordering set and remove it along with its edge from the graph. Then we repeat the same strategy on hte remaining graph until it is empty
Toplogical Order
____ is an ordering of vertices of a graph, such that, if there is a path from u to v in the graph then u appears before v in the ordering
Topological order
Which graph traversal is similar to preorder traversal
DFS
Which graph traversal technique picks one of hte adjacent vertex and proceeds
DFS
Which graph traversal technique considers all of the adjacent vertices and proceeds
BFS
Every graph has
Zero or more topological order
A graph in which there is an edge between wevery pair of vertices is called as
Complete
A graph which does not have self loops or parallel edges is called
Simple graph
A graph in which there is a path between every pair od vertices is called as
Connected
Adjacency matrix representation of graph is preferred when
the graph is dense
Adjacency List representation of graph is preferred when
the graph is sparse
Which linear data structure is used by DFS
Stack
Output of BSF
Is always a tree
Which linear data structure is used by BFSF
FIFO queue
A tree is an example of
connected, acyclic graph
Output of DFS
May be a forest
