#include
#include
#include
using namespace std;
struct node //the data structure for the nodes that are being explored
{
int data;
struct node *next;
};
class stack //the data structure for the queue that is being used to store the nodes that are being searched through
{
private:
struct node *top;
public:
stack()
{
top = NULL;
}
void push(int indata) //pushes a node onto the top of the stack
{
node *p;
if((p=(node*)malloc(sizeof(node))) == NULL)
{
cout << "Memory Exhausted";
exit(0);
}
p = new node;
p->data = indata;
p->next = NULL;
if(top != NULL)
{
p->next = top;
}
top = p;
}
int pop() //pops a node from the top of the stack
{
struct node *temp;
int value;
if(top == NULL)
{
cout << "\nThe stack is Empty" << endl;
}
else
{
temp = top;
top = top->next;
value = temp->data;
delete temp;
}
return value;
}
bool isEmpty() //returns whether the stack is empty
{
return (top == NULL);
}
void display() //displays the nodes and their order in the stack
{
struct node *p = top;
if(top == NULL)
{
cout << "\nNothing to Display\n";
}
else
{
cout << "\n The contents of stack\n";
while(p != NULL)
{
cout << p->data << endl;
p = p->next;
}
}
}
};
class Graph //the data structure for the graph that contains the nodes and the edges between them
{
private:
int n;
int **A;
public:
Graph(int size) //allows for variable creation of graph size
{
int i, j;
if (size < 2)
n = 2;
else
n = size;
A = new int*[n];
for (i = 0; i < n; ++i)
A[i] = new int[n];
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
A[i][j] = 0;
}
~Graph()
{
for (int i = 0; i < n; ++i)
delete [] A[i];
delete [] A;
}
bool isConnected(int x, int y) //returns whether two nodes are connected to each other
{
return (A[x-1][y-1] == 1);
}
void addEdge(int x, int y) //adds an edge connecting the two given nodes
{
A[x-1][y-1] = A[y-1][x-1] = 1;
}
void DFS(int x, int g) //the function used for the Depth-First Search
{
stack s;
bool *explored = new bool[n+1]; //stores explored nodes
bool found = false; //denotes whether the goal node has been found
int i;
for(i = 0; i <= n; i++) //initializes all nodes as unexplored
explored[i] = false;
s.push(x); //adds the initial node to the top of the stack
explored[x] = true;
cout << "Depth first Search starting from vertex ";
cout << x << " : " << endl;
while(!s.isEmpty() && !found)
{
int k = s.pop();
cout << k << " ";
if(k == g) //stops the search after the goal is found
{
cout << "\n\nGoal found!";
found = true;
}
else
{
for (i = n; i >= 0 ; i--) //pushes the nodes that are connected to each other, in LIFO order
if(isConnected(k, i) && !explored[i])
{
s.push(i);
explored[i] = true;
}
}
}
cout << endl;
delete [] explored;
}
};
int main()
{
Graph g(8); //creates a graph with 8 nodes
g.addEdge(1, 2); //adds edges between nodes (this is modular and can be changed)
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 5);
g.addEdge(2, 6);
g.addEdge(4, 7);
g.addEdge(4, 8);
clock_t t1;
t1 = clock();
g.DFS(1, 4); //both the root5 node and the goal node can be adjusted
float diff = (double)(clock() - t1)/CLOCKS_PER_SEC; //keeps track of the time taken to execute the search
cout << endl << "Time taken for DFS: " << diff << endl;
return 0;
}