生成树：极小连通子图 连通分量：极大连通子图

邻接表，边链表结点的个数为v的出度，而v在邻接表中出现的次数为v的入度

答案错了

拓扑排序可以用来判断是否有环 Dijkstra 最短路径 prim 最小生成树

prim算法的时间复杂度为O(|V|^2),不依赖于边，适合求解边稠密的图的最小生成树 kruskal算法 时间复杂度取决于边的数量，因此适合存储稀疏图

dijkstra是解决带权图的单源点最短路径问题的 floyd是解决带权图的每对顶点之间的最短路径问题 广度优先遍历解决的是无权图的单源点最短路径问题

与存储结构没有太大关系

从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径

递归深度优先输出的也是逆拓扑序列

拓扑序列为有向无环图 强连通图不一定有环，顶点数目大于一的强连通分量有环

n 较少时采用 直接插入，简单选择 基本有序的时候采用 直接插入和冒泡排序 n较大时采用快速排序，堆排序，归并排序  基数排序用于n较大，关键字的位数较小时

最坏的情况元素逆序

简单选择排序元素的移动次数非常少，最多不会超过3（n-1）

快排需要借助递归工作栈来储存信息，所以说快速排序需要的空间不是最小的

最好的情况就是均匀的划分，第一趟排序是比较 。。。，。。。。 需要比较7次，第二趟排序 。，。    。，。。 前边比较两次，后边比较三次，第三趟排序 ，。最后比较一次 7+2+3+1=13

k个关键字互为同义词说明在相同的散列函数下映射到的地址是相同的，因此1+2+...+k次

散列表的查找效率取决于散列函数，处理冲突的方法和装填因子，线性探测法和拉链法都属于处理冲突的方法，不管使用哪一个查找的效率都和装填因子相关

装填因子越大说明表的长度就越短，所以不能增大装填因子，应该去减少装填因子

线性探测法的堆积现象是非同义词之间的冲突引起的，拉链法很好的解决了这种问题

王道书上给的是n+1次