import java.util.Scanner;
class Stack
{
int stk[]=new int[10];
int top;
Stack()
{
top=-1;
}
void Push (int item)
{
if (top==9)
System.out.println("Stack overflow");
else
stk[++top]=item;
boolean isEmpty()
{
if (top<0)
return true;
else
return false;
}
int Pop()
{
if (isEmpty())
{
System.out.println("Stack underflow");
return 0;
}
else
return (stk[top--]);
}
void stackTop()
{
if(isEmpty())
System.out.println("Stack underflow ");
else
System.out.println("Stack top is "+(stk[top]));
}
void Display()
{
System.out.println("Stack-->");
for(int i=0;i<=top;i++)
System.out.println(stk[i]);
}
}
class Graph
{
int MAXSIZE=51;
int adj[][]=new int[MAXSIZE][MAXSIZE];
int visited[]=new int [MAXSIZE];
Stack s=new Stack();
void createGraph()
{
int n,i,j,parent,adj_parent,initial_node;
int ans=0,ans1=0;
System.out.print("\nEnter total number elements in a Undirected Graph :");
n=getNumber();
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
adj[i][j]=0;
for (int c=1;c<=50;c++)
visited[c]=0;
System.out.println("\nEnter graph structure for BFS ");
do
{
System.out.print("\nEnter parent node :");
parent=getNumber();
do
{
System.out.print("\nEnter adjacent node for node "+parent+ " : ");
adj_parent=getNumber();
adj[parent][adj_parent]=1;
adj[adj_parent][parent]=1;
System.out.print("\nContinue to add adjacent node for "+parent+"(1/0)?");
ans1= getNumber();
} while (ans1==1);
System.out.print("\nContinue to add graph node?");
ans= getNumber();
}while (ans ==1);
System.out.print("\nAdjacency matrix for your graph is :\n");
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
System.out.print(" "+adj[i][j]);
System.out.print("\n");
}
System.out.println("\nYour Undirected Graph is :");
for(i=1;i<=n;i++)
{
System.out.print("\nVertex "+i+"is connected to : ");
for (j=1;j<=n;j++)
{
if (adj[i][j]==1)
System.out.print(" "+j);
}
}
System.out.println("\nEnter the initial node for BFS traversal:");
initial_node=getNumber();
DFS (initial_node, n);
}
void DFS (int initial_node,int n)
{
int u,i;
s.top = -1;
s.Push(initial_node);
System.out.println("\nDFS traversal for given graph is : ");
while(!s.isEmpty())
{
u=s.Pop();
if(visited[u]==0)
{
System.out.print("\n"+u);
visited[u]=1;
}
for (i=1;i<=n;i++)
{
if((adj[u][i]==1) && (visited[i]==0))
{
s.Push(u);
visited[i]=1;
System.out.print(" "+i);
u = i;
}
}
}
}
int getNumber()
{
Scanner in = new Scanner(System.in);
int ne=0;
ne=in.nextInt();
return ne;
}
}
class DFS
{
public static void main(String args[])
{
Graph g=new Graph();
g.createGraph();
}
}