#include<iostream>
using namespace std;

struct vert
{
	char neighbour[20];
	int nn;
	char name;
	int color;
	int d;
	char pi;
};

void bfs(char start);
void dfs(char start);
int vi = 0;
vert vertex[20];

int findi(char a)
{
	int i;
	for(i = 0; i < vi; i++)
		if(vertex[i].name == a)
			return i;
	return 0;
}

int  main()
{
	char b, a,start;
	int c, d, i, u;

	cout << "Enter the edges\n0 to stop:\n ";
	while(1)
	{
		cin >> a;
		if(a == '0')
			break;
		cin >> b;
		c = 0,d = 0;
		for(i = 0 ; i < vi; i++)
		{
			if(a == vertex[i].name)
			{
				vertex[i].neighbour[vertex[i].nn++] = b;
				c++;
			}
			if(b == vertex[i].name)
			{
				vertex[i].neighbour[vertex[i].nn++] = a;
				d++;
			}
		}
		if(c == 0)
		{
			vertex[vi].name = a;
			vertex[vi].nn = 0;
			vertex[vi++].neighbour[vertex[vi].nn++] = b;
		}
		if(d == 0)
		{
			vertex[vi].name = b;
			vertex[vi].nn = 0;
			vertex[vi++].neighbour[vertex[vi].nn++] = a;
		}
	}
	cout << "Enter the starting vertex: ";
	cin >> start;
	bfs(start);
	cout << endl;
	dfs(start);
}

void bfs(char start)
{
	int i;
	int front = 0, back = 0, u;
	int queue[50];
	for(i = 0; i < vi; i++)
	{
		if(vertex[i].name == start)
		{
			vertex[i].color = 1;
			vertex[i].d = 0;
			vertex[i].pi = 0;
			queue[back++] = i;
		}
		else
		{
			vertex[i].color = 0;
			vertex[i].d = -1;
			vertex[i].pi = 0;
		}
	}
	while(front < back)
	{
		u = queue[front++];
		cout << vertex[u].name <<"\t";
		for(i = 0; i<vertex[u].nn; i++)
		{
			if(vertex[findi(vertex[u].neighbour[i])].color == 0)
			   {
				vertex[findi(vertex[u].neighbour[i])].color = 1;
				vertex[findi(vertex[u].neighbour[i])].d = vertex[u].d+1;
				vertex[findi(vertex[u].neighbour[i])].pi = vertex[u].pi;
				queue[back++] = findi(vertex[u].neighbour[i]);
			   }
		}
		vertex[u].color = 2;
	}
}

void dfs(char start)
{
	int i;
	int top = 0,u;
	int stack[50];
	for(i = 0;i < vi; i++)
	{
		if(vertex[i].name == start)
		{
			vertex[i].color = 1;
			vertex[i].d = 0;
			vertex[i].pi = 0;
			stack[top++] = i;
		}
		else
		{
			vertex[i].color = 0;
			vertex[i].d = -1;
			vertex[i].pi = 0;
		}
	}
	while(top > 0)
	{
		u = stack[--top];
		cout << vertex[u].name << "\t";
		for(i = 0;i < vertex[u].nn; i++)
		{
			if(vertex[findi(vertex[u].neighbour[i])].color == 0)
			   {
				vertex[findi(vertex[u].neighbour[i])].color = 1;
				vertex[findi(vertex[u].neighbour[i])].d = vertex[u].d+1;
				vertex[findi(vertex[u].neighbour[i])].pi = vertex[u].pi;
				stack[top++] = findi(vertex[u].neighbour[i]);
			   }
		}
		vertex[u].color = 2;
	}
}





blog comments powered by Disqus

Sister Sites: GATE Overflow, GATE CSE Wiki, GATE CSE, Aptitude Overflow

This work is licensed under the CC By-SA 3.0 , without all the cruft that would otherwise be put at the bottom of the page.