常问问题（3）

1. 图的存储方式，优缺点？连通性的判断

我们知道，对于图而言，最重要的是点集和边集；
对于存储方式，主要是顺序存储和链式存储；

（一）邻接矩阵

邻接矩阵是表示顶点之间相邻关系的矩阵。

邻接矩阵的好处：
（1）直观、简单、好理解
（2）方便检查任意一对定点间是否存在边
（3）方便找任一顶点的所有“邻接点”（有边直接相连的顶点）
（4）方便计算任一顶点的度

对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度。（对称阵----可以优化存储）

对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度（或入度）。

邻接矩阵的局限性：时间复杂度O(n²），空间复杂度O(n²)

（1）浪费空间。对于稠密图还是很合算的。但是对于稀疏图（点很多而边很少）有大量无效元素。
（2）浪费时间。要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。

（二）邻接表

图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。

在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点i的边（对有向图是以顶点i为尾的边）。每个单链表上附设一个表头节点。

邻接表的特点如下：

（1）邻接表表示不唯一。这是因为在每个顶点对应的单链表中，各边节点的链接次序可以是任意的，取决于建立邻接表的算法以及边的输入次序。
（2）对于有n个顶点和e条边的无向图，其邻接表有n个顶点节点和2e个边节点。显然，在总的边数小于n(n-1)/2的情况下，邻接表比邻接矩阵要节省空间。
（3）对于无向图，邻接表的顶点i对应的第i个链表的边节点数目正好是顶点i的度。
（4）对于有向图，邻接表的顶点i对应的第i个链表的边节点数目仅仅是顶点i的出度。其入度为邻接表中所有adjvex域值为i的边节点数目。
入度不好求，如果是强需求，可以用逆邻接表来存储。

上面的两种存储结构是针对顶点，下面的三种存储结构是针对边

我们想要知道出度方向的顶点，可以使用邻接表，我们要了解入度就需要使用逆邻接表。但是我们既想要了解入度有想要了解出度，那么我们该如何处理？
这时就需要使用到有向图的一种存储方法：十字链表

十字链表
是综合邻接表和逆邻接表形式的一种链式存储结构。
在十字链表存储结构中，有向图中的顶点的结构如下所示：

其中data表示顶点的具体数据信息，而firstIn则表示指向以该顶点为弧头的第一个弧节点。而firstOut则表示指向以该顶点为弧尾的第一个弧节点。

为了表示有向图中所有的顶点，采用一个顶点数组存储每一个结点，如下图所示。

另外，在十字链表存储结构中，有向图中的每一条弧都有一个弧结点与之对应，具体的弧结点结构如下所示：

其中的tailVex表示该弧的弧尾顶点在顶点数组xList中的位置，headVex表示该弧的弧头顶点在顶点数组中的位置。hLink则表示指向弧头相同的下一条弧，tLink则表示指向弧尾相同的下一条弧。

从十字链表的数据结构来看，每一个顶点对应两个链表：以该顶点为弧尾的弧结点所组成的链表以及以该顶点为弧头的弧结点所组成的链表。

邻接多重表
邻接多重表是对无向图的存储结构的优化

我们只出现无向图中对应条数的边表结点，其他的结构，我们全部由指针来联系，所以当我们想要删除一条边时，就只需要删除对应的边表结点。指向她的指针会置为空，他自己产生的指针会消失。就完成了对边的操作。
邻接多重表与邻接表的差别，仅仅是在于同一条边在邻接表中用两个边表结点表示，而在邻接多重表中只有一个结点。这样对边的操作就方便多了，

边集数组

边集数组是由两个一维数组构成。一个是存储顶点的信息；另一个是存储边的信息。
这个边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）和权（weight）组成。

优点：适合对边处理，
缺点：入度、出度不好计算

前向星

前向星是一个特殊的边集数组， 其特殊性在于他在边集数组的基础上，按照起点进行了一次排序，
优点（相同的起点的边， 就可以邻在一起）。

利用c++中vector的特点（动态数组）来存图；
其实， vector 很像邻接表， 相比邻接表（Edge结构体是边表， vector 是一个 Edge类型 的二维动态数组， 相当于 ）， 他写起来比邻接表更方便。
这种方法很多人叫他（vector + 前向星）。

连通性判断：

1 DFS判断：

从任一结点开始，进行一次深度优先遍历。深度优先遍历的结果是一个图的连通分量。当一次遍历没有访问到所有结点，那么就说明图是不连通。

2 BFS判断：

从一个结点开始，访问与其关联的所有结点，将这些结点入队，重复此过程，直至队列为空。访问的结点构成一个连通分量，若该连通分量未包含所有结点，则无向图不连通。

3 Warshell判断：

图中点与点之间构成边，也可以理解为存在边的两个结点之间存在关系，那么就可以使用Warshell算法求这些关系的传递闭包。Warshell算法更改矩阵的依据实质上是关系的继承，若结点i与结点j之间有边，那么结点 i 就继承结点 j
的连通关系。

4 Union-Find判断：

根据读入的边对进行集合的划分，读入的边对证明是相连的，那么我们就划分到一个集合中，然后读入新的边对就划分到新的集合中，一旦读入的边对（两个顶点）都在同一个集合中出现过，那么证明是相互连通的，如果读入的边对，两个顶点是出现在两个集合中，那么说明这两个集合至少通过该边是可以相连的，那么集合进行合并。重复以上过程，即可得到求解结果。最后只要判断所以结点是否在一个集合就可得到图是否连通，若在一个集合，则图连通，反之不连通。

5 Tarjan判断：

该算法可以用来求有向图的强连通分量。在无向图中，两点之间的连通其实等价于有向图中的强连通，都是互相可达的概念。所以，就可以使用Tarjan算法来得到无向图的“强”连通分量。如果无向图只有一个“强”连通分量，那么这个图就是一个连通图。

2. 深度优先和广度优先

(1)广度优先

它的基本思想类似二叉树的层序遍历，首先访问起始顶点v,然后由v出发依次访问v的各个未访问过的邻接顶点w1
…wi,然后再依次访问w1 …wi的所有未被访问过的邻接顶点。再从

这些访问过的顶点出发，再访问她们所有未访问过的顶点，依次类推直到图中所有顶点都被访问过为止。算法要借助辅助队列进行。

深度优先

它的基本思想类似树的先序遍历，首先访问图中某-起始顶点V,然后由v出发访问与v邻接且未被访问的任一顶点w1，再访闷与w1邻接且.未被访问的任一顶点w2,重复上述过程。当不能继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问，则从该点开始继续上述搜索过程，直到图中所有顶点均被访问过为止。算法要借助递归思想来进行。

深度优先和广度优先的对比

深度优先搜索(回溯法) 算法思路

深度优先搜索(DFS,Depth-First Search)是搜索的手段之一

它从某个状态开始,不断地转移状态直到无法转移,然后回退到前一步状态,继续转移到其他状态,如此不断重复,直到找到最终的解.根据深度优先搜索的特点,采用递归函数(隐式地利用了栈进行计算)实现比较简单.

算法效率

深度优先搜索从最开始的状态出发,遍历所有可以到达的状态.由此可以对所有的状态进行操作,或列举出所有的状态.作为搜索算法的一种,DFS对于寻找一个解的NP(包括NPC)问题作用很大.

但是,搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法，它的效率比较低,在数据规模变大时,这种算法就显得力不从心了.关于深度优先搜索的效率问题,有多种解决方法.最具有通用性的是**剪枝(prunning),**也就是去除没有用的搜索分支.有可行性剪枝和最优性剪枝两种.此外,对于很多问题,可以把搜索与动态规划(DP,dynamic programming)、完备匹配(匈牙利算法)等高效算法结合.

2.宽度优先搜索(分支限界法)

算法思路

宽度优先搜索(BFS,Breadth-First Search)也是搜索的手段之一.他与深度优先搜索类似,从某个状态出发搜索所有可以到达的状态.根据宽度优先搜索的特点,采用队列实现比较简单.

算法效率

与深度优先不同之处在与搜索的顺序,宽度优先搜索总是先搜索距离初始状态近的状态.也就是说,它是按照开始状态->只需1次转移就可以到达的所有状态->只需2次转移就可以到达的所有状态->…这样的顺序进行搜索.对于同一个状态,宽度优先搜索只经过一次,因此复杂度为

O(状态数*转移的方式).很容易地用来求最短路径、最少操作之类问题的答案.

广度搜索的判断重复如果直接判断十分耗时,我们一般借助哈希表来优化时间复杂度.

3.Death-Breadth总结

宽度优先搜索与深度优先搜索一样,都会生成所有能够遍历到的状态,因此需要对所有状态进行处理时使用宽度优先也是可以的.但是递归函数可以很简短地编写,而且状态的管理也更简单,所以大多数情况下还是用深度优先搜索实现.反之,在求取最短路时深度优先搜索需要反复经过同样的状态,所以还是使用宽度优先搜索比较好.

宽度优先搜索会把状态逐个加入队列,因此通常需要与状态数成正比的内存空间.反之,深度优先搜索是与最大的递归深度成正比的.一般与状态数相比,递归的深度并不会太大,所以可以认为深度优先搜索更加节省内存.

3. 进程与线程

进程与线程的区别

1 线程是程序执行的最小单位，而进程是操作系统分配资源的最小单位；
2 一个进程由一个或多个线程组成，线程是一个进程中代码的不同执行路线
3 进程之间相互独立，但同一进程下的各个线程之间共享程序的内存空间(包括代码段，数据集，堆等)及一些进程级的资源(如打开文件和信号等)，某进程内的线程在其他进程不可见；
4 调度和切换：线程上下文切换比进程上下文切换要快得多

4. 堆和栈

1.程序内存分区中的堆与栈

堆与栈区别堆与栈实际上是操作系统对进程占用的内存空间的两种管理方式，主要有如下几种区别： （1）管理方式不同。栈由操作系统自动分配释放，无需我们手动控制；堆的申请和释放工作由程序员控制，容易产生内存泄漏； （2）空间大小不同。每个进程拥有的栈的大小要远远小于堆的大小。理论上，程序员可申请的堆大小为虚拟内存的大小，进程栈的大小64bits的Windows默认1M，64bits的Linux默认10M；
（3）生长方向不同。堆的生长方向向上，内存地址由低到高；栈的生长方向向下，内存地址由高到低。 （4）分配方式不同。堆都是动态分配的，没有静态分配的堆。栈有2种分配方式：静态分配和动态分配。静态分配是由操作系统完成的，比如局部变量的分配。动态分配由alloca函数进行分配，但是栈的动态分配和堆是不同的，他的动态分配是由操作系统进行释放，无需我们手工实现。 （5）分配效率不同。栈由操作系统自动分配，会在硬件层级对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是由C/C++提供的库函数或运算符来完成申请与管理，实现机制较为复杂，频繁的内存申请容易产生内存碎片。显然，堆的效率比栈要低得多。
（6）存放内容不同。栈存放的内容，函数返回地址、相关参数、局部变量和寄存器内容等。当主函数调用另外一个函数的时候，要对当前函数执行断点进行保存，需要使用栈来实现，首先入栈的是主函数下一条语句的地址，即扩展指针寄存器的内存（eip），然后是当前栈帧的底部地址，即扩展基址指针寄存器内容（ebp），再然后是被调函数的实参等，一般情况下是按照从右向左的顺序入栈，之后是调用函数的局部变量，注意静态变量是存放在数据段或者BSS段，是不入栈的。出栈的顺序正好相反，最终栈顶指向主函数下一条语句的地址，主程序又从该地址开始执行。堆，一般情况堆顶使用一个字节的空间来存放堆的大小，而堆中具体存放内容是由程序员来填充的。

2.数据结构中的堆与栈

堆可以被看成是一棵树；

栈是一种先进后出的数据结构

5. B树、B+树、红黑树

B树和B+树的区别，以一个m阶树为例。

关键字的数量不同：B+树中分支结点有m个关键字，其叶子结点也有m个，其关键字只是起到了一个索引的作用，但是B树虽然也有m个子结点，但是其只拥有m-1个关键字。

存储的位置不同：B+树中的数据都存储在叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据，但是B树的数据存储在每一个结点中，并不仅仅存储在叶子结点上。

分支结点的构造不同：B+树的分支结点仅仅存储着关键字信息和儿子的指针（这里的指针指的是磁盘块的偏移量），也就是说内部结点仅仅包含着索引信息。

查询不同:B树在找到具体的数值以后，则结束，而B+树则需要通过索引找到叶子结点中的数据才结束，也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径

红黑树：平衡二叉树，通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束，确保没有一条路径会比其他路径长2倍，因而是近似平衡的。所以相对于严格要求平衡的AVL树来说，它的旋转保持平衡次数较少。用于搜索时，插入删除次数多的情况下我们就用红黑树来取代AVL。
红黑树就是一颗m=3的B树