package com.yzh.hehe;

 import java.util.ArrayList;

 import java.util.Stack;

 public class DirGraCheckPath {

     public static void main(String[] args) {

         // TODO Auto-generated method stub

     }

      public boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b) {

         return  checkSingle(a, b)||checkSingle(b, a);

      }

      private boolean checkSingle(UndirectedGraphNode a, UndirectedGraphNode b) {

          if (a.label==b.label) {

                 return true;

             }

              //深度优先遍历用堆栈实现（广度优先遍历用队列实现）

             Stack<UndirectedGraphNode> stack= new  Stack<UndirectedGraphNode>();

             //已遍历的点

             ArrayList<UndirectedGraphNode> list=new ArrayList<UndirectedGraphNode>();

             list.add(a);

             stack.addAll(a.neighbors);

             UndirectedGraphNode temp = null;

             //深度遍历一个点，看是否目标点，是结束，否则再将此点的连接点放入栈中等待遍历重复（入栈将连接点中已经在栈中和已遍历过的点去掉）。

             while (!stack.isEmpty()) {

                 temp = stack.pop();

                 if (temp.label==b.label) {

                     return true;

                 }

                 for (UndirectedGraphNode undirectedGraphNode : temp.neighbors) {

                     if (!stack.contains(undirectedGraphNode)&&!list.contains(undirectedGraphNode)) {

                         stack.push(undirectedGraphNode);

                     }

                 }

                 list.add(temp);

             }

             return false;

     }

 }

  class UndirectedGraphNode {

     int label = 0;

     UndirectedGraphNode left = null;

     UndirectedGraphNode right = null;

     ArrayList<UndirectedGraphNode> neighbors = new ArrayList<UndirectedGraphNode>();

     public UndirectedGraphNode(int label) {

         this.label = label;

     }

 }