深度优先遍历算法是经典的图论算法。从某个节点v出发开始进行搜索。不断搜索直到该节点所有的边都被遍历完,当节点v所有的边都被遍历完以后,深度优先遍历算法则需要回溯到v以前驱节点来继续搜索这个节点。
注意:深度优先遍历问题一定要按照规则尝试所有的可能才行。
二、二叉树
2.二叉树类型
二叉树类型:空二叉树、满二叉树、完全二叉树、完美二叉树、平衡二叉树。
空二叉树:有零个节点
完美二叉树:每一层节点都是满的二叉树(如1中举例的图)
满二叉树:每一个节点都有零个或者两个子节点
完全二叉树:出最后一层外,每一层节点都是满的,并且最后一层节点全部从左排列
平衡二叉树:每个节点的两个子树的深度相差不超过1.
注:国内对完美二叉树和满二叉树定义相同
3.二叉树相关术语
术语 解释
度 节点的度为节点的子树个数
叶子节点度为零的节点
分支节点度不为零的节点
孩子节点节点下的两个子节点
双亲节点节点上一层的源节点
兄弟节点拥有同一双亲节点的节点
根 二叉树的源头节点
深度 二叉树中节点的层的数量
DLR(先序):
LDR(中序):
LRD(后序):
注意:L代表左子树R代表右子树;D代表根
6.深度优先遍历和广度优先遍历
深度优先遍历:前序、中序和后序都是深度优先遍历
从根节点出发直奔最远节点,
广度优先遍历:首先访问举例根节点最近的节点,按层次递进,以广度优先遍历上图的顺序为:1-2-3-4-5-6-7
三、面试题+励志
企鹅运维面试题:
1.二叉树遍历顺序:看上文
2.用你熟悉的语言说说怎么创建二叉树? python看上文
如果只是画图的话,visio甚至powerpoint之类有画图功能的软件都可以。如果是要根据数据动态生成,不妨尝试一些脚本语言,比如python有一个图论算法包networkx,动态画图很方便。当然,首先你得了解python这个语言。不然做法无从谈起。
谱聚类概念 :
谱聚类是一种基于图论的聚类方法,通过对样本数据的拉普拉斯矩阵的特征向量进行聚类,从而达到对样本数据聚类的母的。谱聚类可以理解为将高维空间的数据映射到低维,然后在低维空间用其它聚类算法(如KMeans)进行聚类。
算法步骤
1 计算相似度矩阵 W
2 计算度矩阵 D
3 计算拉普拉斯矩阵L=D-W
4 计算L的特征值,将特征值从小到大排序,取前k个特征值.将这个特征值向量转换为矩阵
5 通过其他聚类算法对其进行聚类,如k-means
详细公式和概念请到 大佬博客
相比较PCA降维中取前k大的特征值对应的特征向量,这里取得是前k小的特征值对应的特征向量。但是上述的谱聚类算法并不是最优的,接下来我们一步一步的分解上面的步骤,总结一下在此基础上进行优化的谱聚类的版本。
python实现
例子一:使用谱聚类从噪声背景中分割目标
效果图
例子2:分割图像中硬币的区域
效果图
注意
1)当聚类的类别个数较小的时候,谱聚类的效果会很好,但是当聚类的类别个数较大的时候,则不建议使用谱聚类;
(2)谱聚类算法使用了降维的技术,所以更加适用于高维数据的聚类;
(3)谱聚类只需要数据之间的相似度矩阵,因此对于处理稀疏数据的聚类很有效。这点传统聚类算法(比如K-Means)很难做到
(4)谱聚类算法建立在谱图理论基础上,与传统的聚类算法相比,它具有能在任意形状的样本空间上聚类且收敛于全局最优解
(5)谱聚类对相似度图的改变和聚类参数的选择非常的敏感;
(6)谱聚类适用于均衡分类问题,即各簇之间点的个数相差不大,对于簇之间点个数相差悬殊的聚类问题,谱聚类则不适用;
参考
谱聚类算法介绍
sklearn官网