Include a brief README file explaining what you did. In this assignment you will
ID: 3817198 • Letter: I
Question
Include a brief README file explaining what you did.
In this assignment you will implement three basic graph algorithms: breadth-first search, depth-first search and topological sort. We are not providing any code template, but you must follow the input and output formats specified below. Read carefully what you are required to do to receive full credit, and attempt the extra credit tasks only after you are done with the requirements.
First, implement a graph data structure using adjacency lists. Your code must read graphs of arbitrary size from a file (as long as there is enough memory available, your code must work: do not assume a maximum number of vertices). The input format is as follows: one line per vertex, the first element is the vertex id and the following numbers are the adjacent vertices. The input file will always be a bunch of integers and white space. For example,
1 3 4
2
3 1 4
4 1 3
is a graph with four vertices, and three undirected edges: (1, 3), (1,4) and (3,4). Note that the first number in each line is redundant because it is the line number, but the input file will still include it.
Then, implement three algorithms:
• Breadth-first search. Calculate the distance from vertex 1 to all other vertices using BFS. Then, print all the vertices sorted by distance from vertex 1. Note that if the graph is unconnected, some nodes may have distance .
• Depth-first search. Calculate discovery and finish times using DFS. Then, print all the vertices sorted by discovery time.
• Topological sort. Print the topological sort of the graph.
C or c++. C is preferred.
please mention the specific compiling g way.
if possible, I need this before midnight.
Explanation / Answer
#include<iostream>
#include<list>
using namespace std;
// Graph class represents a directed graph using adjacency list representation
class Graph
{
int V; // No. of vertices
list<int> *adj; // Pointer to an array containing adjacency lists
void DFSUtil(int v, bool visited[]); // A function used by DFS
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
void DFS(int v); // DFS traversal of the vertices reachable from v
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
cout << v << " ";
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
// DFS traversal of the vertices reachable from v.
// It uses recursive DFSUtil()
void Graph::DFS(int v)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Call the recursive helper function to print DFS traversal
DFSUtil(v, visited);
}
int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Following is Depth First Traversal (starting from vertex 2) ";
g.DFS(2);
return 0;
}