Please create code in C++ based on the following instructions. The code must implement all 3 graph algorithms! (Breadth First Search, Depth First Search, and Topological Sort). Also the input must be read from a file, which accounts for one white space between each number (Look at example input).

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 of infinity.

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. A few comments: Look carefully at the sample input and output files and follow the same format. When you look through vertices, visit them in increasing order.

Example input (Breadth First Search, theres a white space between each number):

1 2 3 4 2 1 3 1 4 1

Expected Output:

1 0 2 1 3 1 4 1

Example input (Depth First Search, theres a white space between each number):

1 3 4 5 2 3 3 1 2 4 4 1 3 5 1 6 7

Expected Output:

1 1 10 3 2 7 2 3 4 4 5 6 5 8 9 6 11 12 7 13 14

Example Input (Topological Sort, theres a white space between each number):

1 2 4 5 6 2 6 3 2 5 4 5 6

Expected Output:

3 1 5 4 2 6