首页 > 代码库 > 算法系列001---dfs理解

算法系列001---dfs理解

1.研究范围

1)多叉树,图的遍历

2)回溯法的解空间树=多叉树的遍历

2.研究方法

    我们现在研究的是多叉树的遍历,固然要从二叉树的遍历开始,然后研究为什么不能直接用二叉树的遍历方法,找到多叉树不同于二叉树的地方,并对其进行解决,就得到了我们的多叉树的遍历方法。

2.1 从二叉树和多叉树|图的结构和二叉树的dfs特点及应用范围来研究

1)二叉树

   public class TreeNode {

    int val;
  TreeNode left;
  TreeNode right;
    TreeNode(int x) { val = x; }
   }

        

 2)多叉树|图

  class UndirectedGraphNode {
     int label;
    List<UndirectedGraphNode> neighbors;
    UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
   };

 3)不同点或不能直接用二叉树遍历的原因

   二叉树的邻接点是确定的(或者说是可以直接点名点到的),而多叉树和图的邻接点是不确定的,我们不可能直接点名某节点君的第i个邻接点。