import java.util.*;
public class Test 
{
    private static int number=8;
    private static boolean[] flag;
    private static String[] point={"A","B","C","D","E","F","G","H"};
//邻接矩阵
    private static int[][] edge={
        {0,1,1,0,0,0,0,0},
        {1,0,0,1,1,0,0,0},
        {1,0,0,0,0,0,0,0},
        {0,1,0,0,0,0,0,0},
        {0,1,0,0,0,0,0,0},
        {0,0,0,0,0,0,1,1},
        {0,0,0,0,0,1,0,0},
        {0,0,0,0,0,1,0,0}};
    //后进先出，所以用栈
    public static void DFS()
    {
        //标记是否访问过的数组
        flag=new boolean[number];
        //扫描point数组的索引
        int index=0;
        Deque<Integer> stack=new ArrayDeque<>();
        //只要index<number，就继续扫描
        while (index<number)
        {
            //如果某个节点还没有访问过
            if (!flag[index])
            {
                flag[index]=true;
                System.out.print(point[index]+" ");
                stack.push(index);
                //以该节点为根节点，到达所有与该根节点相连的节点
                //依次将其入栈并访问
                while (!stack.isEmpty())
                {
                    int k=stack.peek();//important
                    //如果栈顶节点所连的节点还有节点未访问
                    //获得未访问的节点
                    int temp=Helper(k);
                    if (temp>=0)
                    {
                        //得到一个未访问的节点
                        //将未访问的节点入栈
                        stack.push(temp);
                    }
                    else
                        //如果栈顶节点所直接相连的节点都已经访问过
                        //栈顶节点已毫无利用价值，将其出栈
                        stack.pop();
                }
            }
            //注意循环控制变量自增
            index++;
        }
    }
    public static int Helper(int k)
    {
        for (int i=0;i<number ;i++ )
        {
            //如果找到栈顶节点k可以到达某个节点i
            if (!flag[i]&&edge[k][i]==1)
            {
                flag[i]=true;
                System.out.print(point[i]+" ");
                return i;
            }
        }
        return -1;
    }
    //先进先出所以用队列
    public static void BFS()
    {
        flag=new boolean[number];
        //扫描point数组的索引
        int index=0;
        Deque<Integer> queue=new ArrayDeque<>();
        while (index<number)
        {
            if (!flag[index])
            {
                flag[index]=true;
                System.out.print(point[index]+" ");
                queue.offer(index);
                //访问该节点能直接到达的所有节点
                //即下一层节点
                while (!queue.isEmpty())
                {
                    int k=queue.peek();//important
                    while (true)
                    {
                        int temp=Helper(k);
                        //得到一个下一层节点，就将该节点入队列
                        if (temp>=0)
                            queue.offer(temp);
                        else
                            break;
                    }
                    //把所有下一层节点都访问过之后，该节点就可以出队列
                    queue.poll();
                }
            }
            index++;
        }
    }
    public static void main(String[] args) 
    {
        DFS();
        System.out.println();
        BFS();
    }
}