锐客网

  1. 首页 > 睿知 > it技术 > >

php面试问到数据结构 php数据库面试题( 六 )

IT技术函数


十字链表主要是针对有向图的存储结构进行了优化，那么对于无向图的邻接表，有没有问题呢？如果我们在无向图的应用中，关注的重点是顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作 。如下图，若要删除(v0,v2)这条边，需要对邻接表结构中右边表的两个结点进行删除 ， 显然这是比较繁琐的 。
因此 ， 我们也仿照十字链表的方式，对边表结点的结构进行一些改造 ， 重新定义的边表结点结构如下表：
|ivex|ilink|jvex|jlink|
其中ivex和jvex是指某条边依附的两个顶点在顶点表中的下标 。ilink指向依附顶点ivex的下一条边，jlink指向依附顶点jvex的下一条边 。
这就是邻接多重表结构 。如上图有4个顶点和5条边，先将边表结点画出来 。由于是无向图 ， 所以ivex，jvex正反过来都可以，为了绘图
方便，都将ivex值设置的与一旁的顶点下标相同 。
下面开始连线 ， 首先连线的（1）（2）（3）（4）是将顶点的firstedge指向一条边 ， 顶点下标要与ivex的值相同 。接着，由于顶点v0的(v0,v1)边的
邻边有(v0,v3)和(v0,v2) 。因此（5）（6）的连线就是满足指向下一条依附于顶点v0的边的目标，注意ilink指向的结点的jvex（ivex）一定要与它本身
的jvex（ivex）的值相同 。同理 ， 连线（7）就是指（v1,v0）这条边，它是相当于顶点v1指向（v1,v2）边后的下一条 。v2有三条边依附 ， 所以（3）之后就有
了（8）（9） 。连线（10）就是顶点v3在连线（4）之后的下一条边 。左图一共有5条边 ， 所以右图有10条连线 ， 完全符合预期 。
邻接多重表与邻接表的差别，仅仅是在于同一条边在邻接表中用两个边表结点表示，而在邻接多重表中只有一个结点。这样对边的操作就方便
多了，若要删除左图的(v0,v2)这条边，只需要将右图的（6）（9）的链接指向改为^即可 。
---- 边集数组是由两个一维数组构成 。一个是存储顶点的信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）和权（weight）组成 。
如上图所示，边集数组关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高 。因此它更适合对边依次
进行处理的操作，而不适合对顶点相关的操作
路径长度：路径上各活动持续时间的总和（即路径上所有权之和） 。
完成工程的最短时间：从工程开始点（源点）到完成点（汇点）的最长路径称为完成工程的最短时间 。
关键路径：路径长度最长的路径称为关键路径 。
二分图是一类特殊的图，又称为双分图、二部图、偶图 。二分图的顶点可以分成两个互斥的独立集 U 和 V 的图，使得所有边都是连结一个 U 中的点和一个 V 中的点 。顶点集 U、V 被称为是图的两个部分 。等价的，二分图可以被定义成图中所有的环都有偶数个顶点 。可以将 U 和 V 当做一个着色：U 中所有顶点为蓝色，V 中所有顶点着绿色，每条边的两个端点的颜色不同 ， 符合图着色问题的要求 。相反的 ， 非二分图无法被二着色
完全二分图 是一种特殊的二分图，可以把图中的顶点分成两个集合，使得第一个集合中的所有顶点都与第二个集合中的所有顶点相连 。
欧拉图是指通过图（无向图或有向图）中所有边且每边仅通过一次通路，相应的回路称为欧拉回路 。具有欧拉回路的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为半欧拉图 。欧拉证明了如下定理： 一个非空连通图是欧拉图当且仅当它的每个顶点的度数都是偶数 。由此可得如下结论：一个连通图有欧拉迹当它至多有两个度数是奇数的顶点 。

推荐阅读


上一篇：安卓appweb框架，android framework框架

下一篇：怎么导出pdf横版，怎么导出pdf横版竖版