#include <iostream>
#include <iomanip>
#include <stack>
#include <queue>
#include <vector>
#include <fstream>
using namespace std;
class graph
{
public:
graph();
graph(int);
//graph(int, int);
void setEdge(int src, int dst);
void printGraph();//print graph
void bfs(int);//Breadth First Search
void dfs(int);//Depth First Search
void bfsSpan(int);//Breadth First Search Spanning Tree
void dfsSpan(int);//DepthFirt Search Spanning Tree
private:
//internal struct to represent the node of the adjecency list
struct node
{
int val;
node *next;
};
int nodeCount;
int edgeCount;
//pointer to dynamically allocate an array of nodes
node* list;
};
graph::graph()
{
nodeCount = 0;
edgeCount = 0;
list = NULL;
}
graph::graph(int nodes)
{
int i;
nodeCount = nodes + 1;
//allocate the array portion of the adjecnecy list
//notice each node has a next pointer that will be use for
//the linked list of adjacent nodes
list = new node[nodeCount];
//init the pointer of each index, notice we dont init the variable on the index
for (i = 0; i<nodeCount; i++)
{
//give the value of the array index either some dummy val or the val of the node
//we can choose either because in this interpretation our arrayy index is the val
//of the node
list[i].val = -1;
list[i].next = NULL;
}
}
void graph::setEdge(int source, int destination)
{
node *temp;
temp = new node;
temp->val = destination;
//add to the front of the list
temp->next = list[source].next;
list[source].next = temp;
//increment edgecount
edgeCount++;
}
void graph::bfs(int startVal)
{
queue<int> q;
vector<bool> visited;
node * tmp;
int i = 0;
int node;
for (i = 0; i<nodeCount; i++)
{
visited.push_back(false);
}
q.push(startVal);
while (!q.empty())
{
node = q.front();
q.pop();
if (!visited[node])
{
cout << setw(3) << node;
visited[node] = true;
tmp = list[node].next;
while (tmp != NULL)
{
if (!visited[tmp->val])
{
q.push(tmp->val);
}
tmp = tmp->next;
}
}
}cout << endl;
}
void graph::dfs(int startVal)
{
stack<int> s;
vector<bool> visited;
node * tmp;
int i = 0;
int node;
for (i = 0; i<nodeCount; i++)
{
visited.push_back(false);
}
s.push(startVal);
while (!s.empty())
{
node = s.top();
s.pop();
if (!visited[node])
{
cout << setw(3) << node;
visited[node] = true;
tmp = list[node].next;
while (tmp != NULL)
{
if (!visited[tmp->val])
{
s.push(tmp->val);
}
tmp = tmp->next;
}
}
}cout << endl;
}
void graph::bfsSpan(int startVal)
{
queue<int> q;
vector<bool> visited;
vector<int> tree;
node * tmp;
int i = 0;
int node;
for (i = 0; i<nodeCount; i++)
{
visited.push_back(false);
tree.push_back(-1);
}
q.push(startVal);
while (!q.empty())
{
node = q.front();
q.pop();
if (!visited[node])
{
if (tree[node] != -1)
cout << "(" << tree[node] << ", " << node << ")";
visited[node] = true;
tmp = list[node].next;
while (tmp != NULL)
{
if (!visited[tmp->val])
{
q.push(tmp->val);
if (tree[tmp->val] == -1)
tree[tmp->val] = node;
}
tmp = tmp->next;
}
}
}cout << endl;
}
void graph::dfsSpan(int startVal)
{
stack<int> s;
vector<bool> visited;
vector<int> tree;
node * tmp;
int i = 0;
int node;
for (i = 0; i<nodeCount; i++)
{
visited.push_back(false);
tree.push_back(-1);
}
s.push(startVal);
while (!s.empty())
{
node = s.top();
s.pop();
if (!visited[node])
{
if (tree[node] != -1)
cout << "(" << tree[node] << ", " << node << ")";
visited[node] = true;
tmp = list[node].next;
while (tmp != NULL)
{
if (!visited[tmp->val])
{
s.push(tmp->val);
tree[tmp->val] = node;
}
tmp = tmp->next;
}
}
}cout << endl;
}
void graph::printGraph()
{
int i;
node *tmp;
cout << "Adjacency List" << endl;
for (i = 0; i<nodeCount; i++)
{
cout << i << " | ";
//get the font of the list for the index
tmp = list[i].next;
//walk the list and print off its values
while (tmp != NULL)
{
cout << " ->" << setw(2) << tmp->val;
tmp = tmp->next;
}
cout << " -> NULL" << endl;
}
}
int main()//main
{
graph *g1;
int command;
int numNodes;
int numEdges;
int sourceNode;
int destinationNode;
int directed;
int start;
ifstream myFile;
myFile.open("dat.txt");//open dat.txt
//get the number of nodes from the file
myFile >> numNodes;
//see whether the graph is directed or undirected
//0 directed 1 undirected
myFile >> directed;
//init graph
g1 = new graph(numNodes);
while (myFile >> sourceNode)
{
myFile >> destinationNode;
if (directed == 0)
{
//graph is directed
g1->setEdge(sourceNode, destinationNode);
}
else
{
//graph is undirected
g1->setEdge(sourceNode, destinationNode);
g1->setEdge(destinationNode, sourceNode);
}
}
//should be done with the first file so close it
myFile.close();
//open the command file
myFile.open("cmd.txt");
if (myFile)//if the command file opened successfully, process it.
{
while (myFile >> command)
{
if (command == 1)
{
myFile >> start;
cout << "BFS Start: " << start << endl;
g1->bfs(start);
}
else if (command == 2)
{
myFile >> start;
cout << "DFS Start: " << start << endl;
g1->dfs(start);
}
else if (command == 3)
{
myFile >> start;
cout << "BFS Span Tree Start: " << start << endl;
g1->bfsSpan(start);
}
else if (command == 4)
{
myFile >> start;
cout << "DFS Span Tree Start: " << start << endl;
g1->dfsSpan(start);
}
else
{
cout << "Error processing command. " << endl;
}
}
}
else//Display an error message
{
cout << "Error opening file. " << endl;
}
myFile.close();//close the file
return 0;
}//end of main
dat.txt
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
1 1
2 1
3 1
4 1
Having some trouble getting the right output here.
For BFS i am getting 1,2,4,5,7,6 Should i be getting 1,2,3,4,5,6?
Also for DFS i am getting 1,3,4,2,5,7,6 should i be getting 1,4,7,6,3,5,2?
if those two are wrong then my spanning trees are wrong.
Can someone point me in the right direction here
Thanks
