数据结构――架的概念

发布: 2007-7-01 20:40 | 作者: admin | 来源: | 查看: 13次 | 进入软件测试论坛讨论

数据结构――架的概念

一、有向架的定义：

有向架是指共享n个节点的m张有向图，每张有向图包含的节点集都是n个节点的子集。

设有n个节点散布在一个平面之上，有节点集合{1,2,3,…}

有m张有向图，其中任意一有向图的节点集合都是以上n个节点的子集。

这m张有向图共享节点集的n个节点

则以上说明构成了一个有向架。

可以把有向架看成m层有向图的叠加，相同的节点迭在一起。

有向架节点的节点入度：指向本节点的不重复的其他节点的数量。

有向架节点的节点出度：本节点指向的不重复的其他节点的数量。

有向架节点的路段入度：指向本节点的所有路段的数量。

有向架节点的路段出度：本节点指向的所有路段的数量。

二、 有向架的描述：

1、邻接矩阵描述:

可以用M×N×N的三维矩阵描述架。每一层有向图可用一个n*n的矩阵描述，则m层有向图（即架）可以用m层n*n的矩阵，即m*n*n的三维矩阵描述。

2、邻接链表描述：

首先建立一个节点类和一个路径类，每个节点拥有一条指针链，每个指针指向一个路径，每条路径有一个来源节点和一个到达节点，还有自己的路径编号，路径编号可以重复。则一个节点可以经由不同编号的路径多次指向一个其他节点，也可以多个其他节点所多次指向。

3、邻接压缩表描述：

使用三个数组：

第一个数组长度为路段总数，第二个数组长度为m+1，第三个数组为节点描述。

4、有向架描述举例：

图1