- 主题:一系列数据结构问题
1，具有n个结点的完全二叉树的深度是?log2n+1?，这个是怎么推导出来的？
2，已知结点个数n，一共可以构造出多少不同形态的二叉树？B[n]=C[n，2n]/（n+1），其中组合n为上标，2n为下标。这个公式算的时候怎么算，看不懂啊。
3，连通图跟生成树有啥区别?
4，无向图中有回路吗？
5，邻接表的遍历时间复杂度是O（n+e），n+e是什么？
持续等待答案中......
--
FROM 183.197.194.*
【 在 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为下标。这个公式算的时候怎么算，看不懂啊。
n 个节点的二叉树形态总数是 n 阶的卡特兰数。
我发现发链接不行。
您搜下这个关键字：n个节点的二叉树有多少种形态
: 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，连通图跟生成树有啥区别?
: ...................
关于图的回路，其实指的是有向图的强连通分量和无向图的双连通分量。
建议阅读 Tarjan 在 1972 年写的论文：
Depth-First Search and Linear Graph Algorithms
这篇论文超级推荐，花很长时间读都划得来。
看完之后对图、dfs 序、树，以及图和生成树之间的关系的认识会上升一大截。
--
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.*
5，邻接表的遍历时间复杂度是O（n+e），n+e是什么？
n 是图的顶点数，e 是边数。
【 在 DorD 的大作中提到: 】
: 1，具有n个结点的完全二叉树的深度是?log2n+1?，这个是怎么推导出来的？
: 2，已知结点个数n，一共可以构造出多少不同形态的二叉树？B[n]=C[n，2n]/（n+1），其中组合n为上标，2n为下标。这个公式算的时候怎么算，看不懂啊。
: 3，连通图跟生成树有啥区别?
: ...................
--
FROM 223.72.44.*
【 在 ameng 的大作中提到: 】
:
: 关于图的回路，其实指的是有向图的强连通分量和无向图的双连通分量。
: 建议阅读 Tarjan 在 1972 年写的论文：
: ...................
真没想到，还能在认知上提升，非常感谢！因为我以前根本就不知道这篇论文，或者说我学的层次还没有达到那个境界。
我写了一段对dijkstra算法的理解，麻烦您再看一下。
1，与起点有直接相连的，距离记录在数组中。没有直连的，记为无穷大。
2，比较与起点直连的几个节点，找一个最短距离的，把这个节点的前置节点记为起点，并把这个顶点加入集合中。
3，从新加入的这个顶点出发访问其余没有加入集合的节点，条件是与该节点直接相连，如果有的话比较从起点直接到这些新节点的距离哪个更短，如果经过新并入集合的节点距离更短，就更新距离，并把前置节点改为新加入集合的那个节点，否则啥也不做。没有直连的依然记为无穷。
4，然后在这些节点里找与新加入集合节点有直连的节点里距离最短的那个，加入集合。
5，从新加入的这个节点出发，重复第3步，这里有一个原则：从起点可以经过已经加入集合的节点访问集合外的节点，但集合外的节点必须是与集合里的节点直连。直到把所有的节点都加入集合。
--
FROM 183.197.194.*
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.*