[發明專利]一種路由遍歷搜索方法及裝置

有效

• 申請號: 201310482907.1
• 申請日: 2013-10-15
• 公開（公告）號: CN104579725B
• 公開（公告）日: 2018-03-23
• 發明（設計）人: 周泉
• 申請（專利權）人: 中國移動通信集團江蘇有限公司
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L12/701
• 代理公司: 北京中譽威圣知識產權代理有限公司11279
• 代理人: 郭振興,叢芳

1.一種路由遍歷搜索方法，其特征在于，包括：

搜索與起始點關聯的第一路由及與終止點關聯的第二路由；

比較所述與起始點關聯的第一路由的尾節點和所述與終止點關聯的第二路由的尾節點；

當所述與起始點關聯的第一路由的尾節點和所述與終止點關聯的第二路由的尾節點相同時，將所述與起始點關聯的第一路由和終止點關聯的第二路由組合后形成從起始點到終止點的路由；

其中，所述搜索與起始點關聯的第一路由包括：

搜索第一指定路由深度下所有以起始點起始的第一路由，所述第一指定路由深度i＝1,2,3…(n+1)/2，其中，n為最大路由深度，且i為不大于(n+1)/2的整數；

所述搜索與終止點關聯的第二路由包括：

搜索第二指定路由深度下所有以起始點起始的第二路由，所述第二指定路由深度j＝n,n-1,n-2…n/2，其中，n為最大路由深度，且j為不小于n/2的整數。

2.根據權利要求1所述的方法，其特征在于，所述搜索與起始點關聯的第一路由還包括：

對于第一路由深度下的以起始點起始的第一路由，查找所述第一路由的尾節點，查找與所述尾節點關聯的所有邊；

將在所述邊上但不在所述第一路由上的節點加入到所述第一路由，得到第一路由深度下以所述起始點起始的第一路由。

3.根據權利要求1所述的方法，其特征在于，所述搜索與終止點關聯的第二路由還包括：

對于第二路由深度下的以終止點起始的第二路由，查找所述第二路由的尾節點，查找與所述尾節點關聯的所有邊；

將在所述邊上但不在所述第二路由上的節點加入到所述第二路由，得到第二路由深度下與所述終止點起始的第二路由。

4.一種路由遍歷搜索裝置，其特征在于，包括：

搜索模塊，用于搜索與起始點關聯的第一路由及與終止點關聯的第二路由；

比較模塊，用于比較所述與起始點關聯的第一路由的尾節點和所述與終止點關聯的第二路由的尾節點；

組合模塊，用于當所述與起始點關聯的第一路由的尾節點和所述與終止點關聯的第二路由的尾節點相同時，將所述與起始點關聯的第一路由和終止點關聯的第二路由組合后形成從起始點到終止點的路由；

其中，所述搜索模塊包括：第一搜索子模塊，用于搜索第一指定路由深度下所有以起始點起始的第一路由，所述第一指定路由深度i＝1,2,3…(n+1)/2，其中，n為最大路由深度，且i為不大于(n+1)/2的整數；

所述搜索模塊還包括：第二搜索子模塊，用于搜索第二指定路由深度下所有以起始點起始的第二路由，所述第二指定路由深度j＝n,n-1,n-2…n/2，其中，n為最大路由深度，且j為不小于n/2的整數。

5.根據權利要求4所述的裝置，其特征在于，所述第一搜索子模塊，還用于對于第一路由深度下的以起始點起始的第一路由，查找所述第一路由的尾節點，查找與所述尾節點關聯的所有邊；將在所述邊上但不在所述第一路由上的節點加入到所述第一路由，得到第一路由深度下以所述起始點起始的第一路由。

6.根據權利要求4所述的裝置，其特征在于，所述第二搜索子模塊，用于對于第二路由深度下的以終止點起始的第二路由，查找所述第二路由的尾節點，查找與所述尾節點關聯的所有邊；將在所述邊上但不在所述第二路由上的節點加入到所述第二路由，得到第二路由深度下與所述終止點起始的第二路由。