rapidio 网络枚举--深度优先遍历算法

根据 RapidIO 协议规范在 RapidIO 路由网络拓扑结构中，一般采用深度优先遍历

的枚举算法，因为广度优先遍历算法空间复杂度大，在规模较大的 RapidIO 网络中容易找不到最优路径。

RapidIO 深度优先遍历算法流程

0.   将与主机 HOST 所连的交换机 SWITCH M 作为出发点

1.   判断与该交换机 M 端口相连的是交换机 SWITCH N 还是终端 EndPoint

2.   若相连的是交换机 SWITCH N，则判断交换机 N 是否被访问过

3.   如果交换机 N 未被访问过，则将 N 标记为已被访问，并从 N 点继续进行深度优先

搜索

4.   如果交换机 N 已被访问过，则只与交换机 N 建立连接关系

5.   若相连的是终端 EndPoint，则将该终端与交换机 M 建立一定的关系

6.   如果任何一个交换机 SWITCH 周围相邻的交换机结点均已被访问过，则从最近一

个被访问的节点开始按逆序依次退回，直至初始顶点

7.   当所有 SWITCH 顶点均已被访问过，或者从任何已被访问过的 SWITCH 顶点出发，

再也无法到达未被访问过的 SWITCH 顶点，则终止该算法

该算法 为 RapidIO 路由网络中较为普遍的一种可以遍历各个交换机 SWITCH 的方式，

其算法时间复杂度为 O(n) ，其中 n 代表 RapidIO 路由网络中各个路径所经过的交换机

SWITCH 结点的平均数量。经过算法 1，可以得到 RapidIO 路由网络中所有遍历的路径，继而能够从中筛选出符合约束要求的某些路径。