【 在 DorD 的大作中提到: 】
: 1，具有n个结点的完全二叉树的深度是?log2n+1?，这个是怎么推导出来的？
第一层 1 个节点；
第二层 2 个节点；
第 n 层 2^(n-1) 个节点。
前 n 层完全二叉树的节点数总和是 1+2+4+...+2^(n-1) = 2^n -1

: 2，已知结点个数n，一共可以构造出多少不同形态的二叉树？B[n]=C[n，2n]/（n+1），其中组合n为上标，2n为下标。这个公式算的时候怎么算，看不懂啊。
: 3，连通图跟生成树有啥区别?
: ...................
--
FROM 223.72.44.*

【 在 DorD 的大作中提到: 】
: 1，具有n个结点的完全二叉树的深度是?log2n+1?，这个是怎么推导出来的？
: 2，已知结点个数n，一共可以构造出多少不同形态的二叉树？B[n]=C[n，2n]/（n+1），其中组合n为上标，2n为下标。这个公式算的时候怎么算，看不懂啊。
: 3，连通图跟生成树有啥区别?
连通图就是这个图上节点之间互相是可以通过边连通的，连通图可以有环。
生成树是连通图的一个子图，保留所有节点和 n-1 条边，使得任意两个节点间都连通，但是只有一条路，没有环。


: ...................
--
FROM 223.72.44.*

【 在 DorD 的大作中提到: 】
: 1，具有n个结点的完全二叉树的深度是?log2n+1?，这个是怎么推导出来的？
: 2，已知结点个数n，一共可以构造出多少不同形态的二叉树？B[n]=C[n，2n]/（n+1），其中组合n为上标，2n为下标。这个公式算的时候怎么算，看不懂啊。
: 3，连通图跟生成树有啥区别?
: ...................

4，无向图中有回路吗？
5，邻接表的遍历时间复杂度是O（n+e），n+e是什么？

n 是有向图所有的节点数，e 是所有的边数。
--
FROM 223.72.44.*

dijkstra 算法的重点是理解算法正确性成立的条件。

dijkstra 算法有一个正确性的前提条件，就是边权不能为 负。
原因是：算法的正确性证明里面，用了这个条件。一旦条件不满足，算法的正确性就塌了。

dijkstra 努力维护一个“已经获得从起点出发最距离的点的集合 S”。
最开始把起点 "小 s" 加入到集合 "大 S" 里面。
然后不断的从 S 外找到 “还没有加入 S 的，距离起点最短的点”，然后把它加入 S。
这个找候选点的第一步，就是把 S 中唯一的一个点 s 直接相连的点加入“候选集合”。
然后不断从 “候选集合”中找到距离 s 最短的点，把它加入 S。
这个点加入 S 的同时，枚举与它直接连接的点，更新（松弛）这些点到 s 的距离。
一旦某个点的距离被松弛，则加入到“候选集合”中。
同一个点如果被多次松弛，则有可能多次被加入“候选集和”。

上述“把候选集合中距离 s 最小的点加入 S”这个步骤，需要证明这时候这个点与 s 的距离已经是最短路，
不可能再被更新了。
这个关键环节用到了“边权不能为负”的条件。
具体证明有点复杂，我勉强能看懂，自己写出来有困难。您可以参考《算法导论》。



【 在 DorD 的大作中提到: 】
: 真没想到，还能在认知上提升，非常感谢！因为我以前根本就不知道这篇论文，或者说我学的层次还没有达到那个境界。
: 我写了一段对dijkstra算法的理解，麻烦您再看一下。
: 1，与起点有直接相连的，距离记录在数组中。没有直连的，记为无穷大。
: ...................
--
FROM 223.72.44.*