Data Structures

For this assignment you are to create a C++ class that implements a graph using either an adjacency list or an adjacency matrix. Your class is to implement the following functions

DFS

BFS

DFS Spanning Tree

BFS Spanning Tree

Each function should take the node to start at as its parameter

Your program will take in 2 files. One called dat.txt and one called cmd.txt. dat.txt contains the list of nodes that are to be added to the graph and cmd.txt contains the commands to be run against your program.

File Format

dat.txt

<0 or 1 | directed undirected>

Example file

7

1

1 3

1 4

1 2

2 4

2 5

3 4

3 6

4 5

4 6

4 7

5 7

6 7

cmd.txt

<0 or 1 arguments>

Commands

1 bfs

2 dfs

3 bfs spanning

4 dfs spanning

Example File

1 1

2 1

3 1

4 1

Expectations

You should not use any already implemented code such as a library for your linked list

Your code should be well formatted with proper spacing and proper naming

Your code should have well named variables. No as bs or cs as names unless it is for something like a loop counter