Question

记得看过一个创意，我非常喜欢。说的是在美国，晚上需要保安通过视频监控对如商场超市、码头仓库、办公写字楼等场所进行安保工作，如图7-4-9所示。值夜班代价总是比较大的，所以人员成本很高。我们国家的一位老兄在国内经常和美国的朋友视频聊天，但总为白天黑夜的时差苦恼，突然灵感一来，想到一个绝妙的点子。他创建一家公司，承接美国客户的视频监控任务，因为美国的黑夜就是中国的白天，利用互联网，他的员工白天上班就可以监控到美国仓库夜间的实际情况，如果发生了像火灾、偷盗这样的突发事件，及时电话到美国当地相关人员处理。由于利用了时差和人员成本的优势，这位老兄发了大财。这个创意让我们知道，充分利用现有的资源，正向思维、逆向思维、整合思维可以创造更大价值。

图7-4-9

那么对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度却不了解出度的情况。有没有可能把邻接表与逆邻接表结合起来呢？答案是肯定的，就是把它们整合在一起。这就是我们现在要讲的有向图的一种存储方法：十字链表（Orthogonal List）。

我们重新定义顶点表结点结构如表7-4-1所示。

表7-4-1

data	firstin	firstout

其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表中的第一个结点。

重新定义的边表结点结构如表7-4-2所示。

表7-4-2

其中tailvex是指弧起点在顶点表的下标，headvex是指弧终点在顶点表中的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。如果是网，还可以再增加一个weight域来存储权值。

比如图7-4-10，顶点依然是存入一个一维数组{v₀,v₁,v₂,v₃}，实线箭头指针的图示完全与图7-4-7的邻接表相同。就以顶点v₀来说，firstout指向的是出边表中的第一个结点v₃。所以v₀边表结点的headvex=3，而tailvex其实就是当前顶点v₀的下标0，由于v₀只有一个出边顶点，所以headlink和taillink都是空。

图7-4-10

我们重点需要来解释虚线箭头的含义，它其实就是此图的逆邻接表的表示。对于v₀来说，它有两个顶点v₁和v₂的入边。因此v₀的firstin指向顶点v₁的边表结点中headvex为0的结点，如图7-4-10右图中的①。接着由入边结点的headlink指向下一个入边顶点v₂，如图中的②。对于顶点v₁，它有一个入边顶点v₂，所以它的firstin指向顶点v₂的边表结点中headvex为1的结点，如图中的③。顶点v₂和v₃也是同样有一个入边顶点，如图中④和⑤。

十字链表的好处就是因为把邻接表和逆邻接表整合在了一起，这样既容易找到以v_i为尾的弧，也容易找到以v_i为头的弧，因而容易求得顶点的出度和入度。而且它除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图的应用中，十字链表是非常好的数据结构模型。