Scribd
Upload
4 views1 page

Assignment11 Graphs

Uploaded by

shouryapratikofficial
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views1 page

Assignment11 Graphs

Uploaded by

shouryapratikofficial
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Assignment 11: Graphs

1. Write a program that performs a breadth-first traversal of a given graph.


Ensure that your program can handle graphs with cycles, identifying and
marking any cycles encountered during traversal.
2. Write a program that performs a depth-first traversal of a given graph.
Additionally, implement functionality to detect and highlight back edges to
verify if the graph contains cycles.
3. Implement Prim's algorithm to find the minimum spanning tree (MST) of a
given weighted graph.
4. Implement Kruskal's algorithm to find the MST of a given graph, adding a
constraint that disallows specific edges (selected by the user at runtime). Your
algorithm should handle edge constraints, adjust the MST accordingly, and
output the cost difference compared to an unconstrained MST.
5. Implement the adjacency list representation of a graph with 𝑚 vertices and 𝑛
edges. Extend this functionality to check if a path of exactly k edges exists
between any given pair of vertices.

You might also like