Skip to content

Instantly share code, notes, and snippets.

@calmhandtitan
Created September 13, 2013 20:16
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save calmhandtitan/6555531 to your computer and use it in GitHub Desktop.
Save calmhandtitan/6555531 to your computer and use it in GitHub Desktop.
class graph with built-in dfs function using Stack(as a class)
#include "stdio.h"
#include "string.h"
#define MAX 1000
class stack
{
int arr[MAX];
int idx;
public:
stack()
{
idx = -1;
}
void push(int x)
{
arr[++idx] = x;
}
int top()
{
return arr[idx];
}
void pop()
{
idx--;
}
bool empty()
{
if(idx == -1)
return true;
else
return false;
}
};
class Graph //graph on adjacency matrix
{
int arr[MAX][MAX];
public:
Graph(int x)
{
memset(arr, x, sizeof(arr));
}
void set(int x[][3],int n)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
arr[i][j] = x[i][j];
}
}
}
void dfs(int src,int n) //working
{
int visited[n];
memset(visited, 0, sizeof(visited));
visited[src] = 1;
stack S;
S.push(src);
printf("doing dfs for %d -> ",src );
int current;
while(!S.empty())
{
current = S.top();
S.pop();
for (int i = 0; i < n; ++i)
{
if(visited[i] == 0 && arr[current][i])
{
printf("%d -> ",i );
visited[i] = 1;
S.push(i);
}
}
}
printf("\n");
}
};
int main()
{
Graph G(0);
int matrix[3][3] = {
0,1,1,
0,0,0,
0,1,0
};
G.set(matrix, 3);
int src;
printf("Enter source vertex to do dfs>>");
scanf("%d",&src);
G.dfs(src,3);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment