算法系列001---dfs|多叉|解空间树理解

时间：2022-02-01 09:24:42

1.研究范围

1）多叉树，图的遍历

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

2.研究方法

我们现在研究的是多叉树的遍历，突然想到为什么不能直接用二叉树的遍历方法呢？我们抱着这个问题，先找到多叉树的结构不同于二叉树的地方，然后研究二叉树的遍历，找到其适用范围的限制和多叉树不能采用二叉树遍历的原因，并解决，最后就得到了我们的多叉树的遍历方法。

2.1 从二叉树和多叉树|图的结构来研究

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个邻接点。

2.2二叉树遍历方法，适用范围，多叉树|图不能适用的原因

1）二叉树的先序递归遍历

 public class Solution {

     List<Integer> l = new ArrayList<Integer>();

     public List<Integer> preorderTraversal(TreeNode root) {

         if (root != null) {

             l.add(root.val);

             preorderTraversal(root.left);

             preorderTraversal(root.right);

         }

         return l;

     }

 }

2）从上面的遍历得知，它的递归遍历中，preorderTraversal(root.left)是直接点名去遍历的，然后结合二叉树和多叉树和图结构的不同点，得出多叉和图不能直接使用二叉遍历的原因，就是它们的邻接点不确定，不能直接点到自己邻接点的名字。当然，这可以应用到三叉，四叉。。，必然要给其邻接点起好名字，下面以四叉为例，

结构：

public class TreeNode {

　 int val;

　TreeNode first;

　 TreeNode second;

    TreeNode third;

    TreeNode fouth;

    TreeNode(int x) { val = x; }

}

遍历：

public class Solution {

    List<Integer> l = new ArrayList<Integer>();

    public List<Integer> preorderTraversal(TreeNode root) {

        if (root != null) {

            l.add(root.val);

            preorderTraversal(root.first);

            preorderTraversal(root.second);

            preorderTraversal(root.third);

            preorderTraversal(root.fouth);

        }

        return l;

    }

}

所以，如果想要五叉，六叉都要给其邻接点起好名字，然后再列举出来分别遍历，呀，我们看出来了，这是在是很麻烦，也正是循环起源的原因，当邻接点可以起名字但很多，或者根本就不能起名字（当邻接点的个数不确定的时候）的时候，我们就不能采用二叉遍历的方法，我们要加入循环。当然，如果是图的话，我们还要加入visit[]数组，判断是否已经遍历过了。

2.3

1）不确定几叉的多叉的结构和遍历

import java.util.ArrayList;

import java.util.List;

class TreeNode{

    int val;

     List<TreeNode> neighbors;

     TreeNode(int x) { val = x; neighbors = new ArrayList<TreeNode>(); }

}

public class b {

    List<Integer> l = new ArrayList<Integer>();

    public List<Integer> DFS(TreeNode root) {

        if (root != null) {

            l.add(root.val);

            for(int i=0;i<root.neighbors.size();i++){

                    DFS(root.neighbors.get(i));

            }

        }

        return l;

    }

}

2）图的遍历

  • 由于图的联通性未知，所以要对每个节点进行确认，循环遍历，如果没有visit过就要对其进行DFS;如果是连通的话，只需考虑下面一点即可。
  • 由于图没有层次性特点，加入visit的hashMap结构

相关文章