数据结构和算法 笔记2 https://facert.gitbooks.io/python-data-structure-cn/

是否连通

class NODE(object):
  def __init__(self,value):
    self.value=value
    self.childs=[]

  def add_child(self,data):
    self.childs.append(data) # 子节点其实也是NODE类型，即子节点和自己是一个类型

  def __str__(self):
    return str(self.value)

class VECTOR(object):
  def __init__(self):
    self.sons={}
    self.ret=[]

  def add_son(self,lst):
    for k,v in lst:
      if k not in self.sons:
        self.sons[k]=NODE(k)
      if v not in self.sons:
        self.sons[v]=NODE(v)
      self.sons[k].add_child(self.sons[v]) #关键点，k的子节点v就是sons里的那个v，要是一个v ！！！

  def judge(self,x_node,y):
    if x_node.value == y:
      self.ret.append(x_node)
      return True
    for i in x_node.childs:
      k_node = self.sons.get(i.value,None)
      if not k_node:
        continue
      if self.judge(i,y):
        self.ret.append(x_node)  #我的孩子和y是联通的，也就代表我也是和y联通的，所以要把我也加到结果集里去
        return True
    else:
      return False

  def weather_in(self,x,y):
    x_node = self.sons.get(x,None)
    if not x_node:
      return False

    return self.judge(x_node,y)


  def show(self):
    ret=reversed(self.ret) #要倒序一下
    for i in ret:
      print(i)

sl=VECTOR()
lst=[('a','b'),('b','z'),('c','d'),('b','c')]
sl.add_son(lst)
ret=sl.weather_in('a','c')
print(ret)
sl.show()