Project 6

Write a C++ program that inputs a graph and executes one of the following functions:

a)Using Depth First Search, it finds the number of connected components and a cycle (the graph must contain at least a cycle) of the graph.

b)Given a weighted graph (assign weights to the edges) find the shortest distance between two vertices (using Dijkstras shortest path algorithm).

In order to accomplish this task, you must declare a class Graph as defined in class and implement a function Creates ( ) that creates the link-list of the graph (see lectures notes). Also the nodes must be labeled from 0 to n-1 (n is the number of nodes). In the class function Creates, a pair of nodes is input (example: 0, 1 - representing the edge (0,1)) for each edge and also the weight of the edge (for example: 12 ).

It is recommended to implement the function Creates first.