锐客网

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

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

IT技术函数


2）图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定 ， 所以用单链表存储，无向图称为顶点vi的边表，有向图则称为以vi为弧尾的出边表 。
从图中我们知道 ， 顶点表的各个结点由data和firstedge两个域表示 ， data是数据域，存储顶点的信息 。
firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点 。
边表结点由adjvex和next两个域组成 。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指
向边表中下一个结点的指针，比如v1顶点与v0、v2互为邻接点，则在v1的边表中，adjvex分别为v0的0和v2的2.
如果想知道某个顶点的度 ， 就去查找这个顶点的边表中结点的各数 。
若要判断顶点vi和vj是否存在边，只需要测试顶点vi的边表adjvex中是否存在结点vj的下标就行了 。
若求顶点的所有邻接点，其实就是对此顶点的边表进行遍历，得到的adjvex域对应的顶点就是邻接点 。
有向图的邻接表中顶点vi的边表是指以vi 为弧尾 的弧来存储的，这样很容易就可以得到每个顶点的出度 。
有时为了便于确定顶点的入度或以顶点为弧头的?。?可以建立一个有向图的逆邻接表，即对每个顶点vi都建立
一个链接为vi为弧头的表 。如下图所示：
此时我们很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很容易实现 。
对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可
对于有向图来说，邻接表是有缺陷的 。关心了出度问题 ， 想了解入度就必须要遍历整个图才能知道 。反之，逆邻接表解决了入度
却不了解出度的情况 。有没有可能把邻接表和逆邻接表结合起来呢？
答案是肯定的，就是把它们整合在一起 。这种存储有向图的方法是：十字链表（Orthogonal List）.
我们重新定义顶点表结点结构为：
|data|firstin|firstout|
其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表中的第一个结点 。
重新定义的 边表 结点结构如下表：
|tailvex|headvex|headlink|taillink|
其中tailvex是指弧起点在顶点表的下标，headvex是指弧终点在顶点表中的下标，headlink是指入边表指针域，指向终点（弧头）相同的
下一条边，taillink是指出边表指针域，指向起点（弧尾）相同的下一条边 。如果是带权值的网 ， 还可以再增加一个weight域来存储权值 。
如下图表示的十字链表：
顶点表依然是存入一个一维数组{v0,v1,v2,v3},以顶点v0来说 ， firstout指向的是出边表中的第一个结点v3 。所以v0边表结点的headvex=3,
而tailvex其实就是当前顶点v0的下标0 ， 由于v0只有一个出边顶点，所以headlink和taillink都是空 。
这里虚线箭头的含义 ， 其实就是逆邻接表的表示 。对于v0来说，它有两条入边，分别来自顶点v1和v2 。因此v0的firstin指向顶点v1的边表
结点中headvex为0的结点，虚线（1），接着由入边结点的headlink指向下一个入边顶点v2，虚线（2） 。
对于顶点v1,它有一个入边顶点v2，2个出边顶点v0和v2，所以它的firstin指向顶点v2的边表结点中headvex为1的结点，虚线（3）.
十字链表的好处就是因为把邻接表和逆邻接表整合在了一起，这样既容易找到以vi为尾的?。?也容易找到以vi为头的弧，因而容易求得
顶点的出度和入度 。除了结构复杂一点外，其实创建图算法的时间复杂度和邻接表是相同的，因此很好的应用在有向图中 。

推荐阅读


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

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