這是去年的問題了，今天在整理郵件的時(shí)候才發(fā)現(xiàn)這個(gè)問題，感覺頂有意思的，特記錄下來。

圖1.

圖2.

在圖2，可清晰的看出各個(gè)節(jié)點(diǎn)直接如何相連，也可以清楚的看出節(jié)點(diǎn)"p"至節(jié)點(diǎn)"j"的的幾種可能路徑。

從上面可以看出第2種可能路徑，經(jīng)過的節(jié)點(diǎn)最少。

為了解決開始的問題，我參考了兩種方法，

第1方法是，

參考單源最短路徑算法：Dijkstra(迪杰斯特拉)算法，主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。

圖3.

第2方法是，

針對(duì)第1種方法的改進(jìn)，就是采用多源點(diǎn)方法，這里就是以節(jié)點(diǎn)"p"和節(jié)點(diǎn)"j"為中心向外層擴(kuò)展，直到兩圓外切點(diǎn)，如圖4. ：

圖4.

在接下來，我就描述在SQL Server中，如何實(shí)現(xiàn)。當(dāng)然我這里采用的前面說的第2種方法，以"P"和"J"為始點(diǎn)像中心外層層擴(kuò)展。

這里提供有表RelactionGraph的create& Insert數(shù)據(jù)的腳本：

use TestDB     
go 
if object_id('RelactionGraph') Is not null drop table RelactionGraph 
create table RelactionGraph(ID int identity,Item nvarchar(50),RelactionItemnvarchar(20),constraint PK_RelactionGraph primary key(ID)) 
go 
create nonclustered index IX_RelactionGraph_Item on RelactionGraph(Item)include(RelactionItem) 
create nonclustered index IX_RelactionGraph_RelactionItem on RelactionGraph(RelactionItem)include(Item) 
go 
insert into RelactionGraph (Item, RelactionItem ) values 
    ('a','b'),('a','c'),('a','d'),('a','e'), 
    ('b','f'),('b','g'),('b','h'), 
    ('c','i'),('c','j'), 
    ('f','k'),('f','l'), 
    ('k','o'),('k','p'), 
    ('o','i'),('o','l') 
go 

編寫一個(gè)存儲(chǔ)過程up_GetPath

use TestDB 
go 
exec dbo.up_GetPath 
        @Node = 'p', 
@RelatedNode = 'j' 
go 

上面的存儲(chǔ)過程，主要分為兩大部分，第1部分是實(shí)現(xiàn)如何搜索，第2部分實(shí)現(xiàn)如何構(gòu)造返回結(jié)果。其中第1部分的代碼根據(jù)前面的方法2，通過@Node 和 @RelatedNode 兩個(gè)節(jié)點(diǎn)向外層搜索，每次搜索返回的節(jié)點(diǎn)都保存至臨時(shí)表#1和#2，再判斷臨時(shí)表#1和#2有沒有出現(xiàn)切點(diǎn)，如果出現(xiàn)就說明已找到最短的路徑（經(jīng)過多節(jié)點(diǎn)數(shù)最少），否則就繼續(xù)循環(huán)搜索，直到循環(huán)至***的搜索深度（@MaxLevel smallint=100）或找到切點(diǎn)。要是到100層都沒搜索到切點(diǎn)，將放棄搜索。這里使用***可搜索深度@MaxLevel，目的是控制由于數(shù)據(jù)量大可能會(huì)導(dǎo)致性能差，因?yàn)樵谶@里數(shù)據(jù)量與搜索性能成反比。代碼中還說到一個(gè)正向和反向搜索，主要是相對(duì)Node 和 RelatedNode來說，它們兩者互為參照對(duì)象，進(jìn)行向外搜索使用。

下面是存儲(chǔ)過程的執(zhí)行：

你可以根據(jù)需要來，賦予@Node 和 @RelatedNode不同的值。

use TestDB 
go 
--Procedure: 
if object_id('up_GetPath') Is not null 
    Drop proc up_GetPath 
go 
create proc up_GetPath 
( 
    @Node nvarchar(50), 
    @RelatedNode nvarchar(50) 
) 
As 
set nocount on 
declare 
    @level smallint =1, --當(dāng)前搜索的深度 
    @MaxLevel smallint=100, --***可搜索深度 
    @Node_WhileFlag bit=1, --以@Node作為中心進(jìn)行搜索時(shí)候，作為能否循環(huán)搜索的標(biāo)記 
    @RelatedNode_WhileFlag bit=1 --以@RelatedNode作為中心進(jìn)行搜索時(shí)候，作為能否循環(huán)搜索的標(biāo)記 
--如果直接找到兩個(gè)Node存在直接關(guān)系就直接返回 
if Exists(select 1 from RelationGraph where (Node=@Node And RelatedNode=@RelatedNode) 
or(Node=@RelatedNode And RelatedNode=@Node) ) or @Node=@RelatedNode 
begin 
    select convert(nvarchar(2000),@Node + ' --> '+ @RelatedNode) AsRelationGraphPath,convert(smallint,0) As StopCount 
    return 
end 
-- 
if object_id('tempdb..#1') Is not null Drop Table #1 --臨時(shí)表#1，存儲(chǔ)的是以@Node作為中心向外擴(kuò)展的各節(jié)點(diǎn)數(shù)據(jù) 
if object_id('tempdb..#2') Is not null Drop Table #2 --臨時(shí)表#2，存儲(chǔ)的是以@RelatedNode作為中心向外擴(kuò)展的各節(jié)點(diǎn)數(shù)據(jù) 
create table #1( 
    Node nvarchar(50),--相對(duì)源點(diǎn) 
    RelatedNode nvarchar(50), --相對(duì)目標(biāo) 
    Level smallint --深度 
    ) 
create table #2(Node nvarchar(50),RelatedNode nvarchar(50),Level smallint) 
insert into #1 ( Node, RelatedNode, Level ) 
    select Node, RelatedNode, @level from RelationGraph a where a.Node =@Node union --正向：以@Node作為源查詢 
    select RelatedNode, Node, @level from RelationGraph a where a.RelatedNode = @Node --反向：以@Node作為目標(biāo)進(jìn)行查詢 
set @Node_WhileFlag=sign(@@rowcount) 
insert into #2 ( Node, RelatedNode, Level ) 
    select Node, RelatedNode, @level from RelationGraph a where a.Node =@RelatedNode union --正向：以@RelatedNode作為源查詢 
    select RelatedNode, Node, @level from RelationGraph a where a.RelatedNode = @RelatedNode--反向：以@RelatedNode作為目標(biāo)進(jìn)行查詢 
set @RelatedNode_WhileFlag=sign(@@rowcount) 
--如果在表RelationGraph中找不到@Node 或 @RelatedNode 數(shù)據(jù)，就直接跳過后面的While過程 
if not exists(select 1 from #1) or not exists(select 1 from #2) 
begin 
    goto While_Out 
end 
while not exists(select 1 from #1 a inner join #2 b on b.RelatedNode=a.RelatedNode) --判斷是否出現(xiàn)切點(diǎn) 
     and (@Node_WhileFlag|@RelatedNode_WhileFlag)>0 --判斷是否能搜索 
     And @level<@MaxLevel --控制深度 
begin 
    if @Node_WhileFlag >0 
    begin     
        insert into #1 ( Node, RelatedNode, Level ) 
            --正向 
            select a.Node,a.RelatedNode,@level+1 
                From RelationGraph a 
                where exists(select 1 from #1 where RelatedNode=a.Node And Level=@level) And 
                    Not exists(select 1 from #1 where Node=a.Node)             
            union 
            --反向 
            select a.RelatedNode,a.Node,@level+1 
                From RelationGraph a 
                where exists(select 1 from #1 where RelatedNode=a.RelatedNode AndLevel=@level) And 
                    Not exists(select 1 from #1 where Node=a.RelatedNode) 
        set @Node_WhileFlag=sign(@@rowcount) 
   end 
    if @RelatedNode_WhileFlag >0 
    begin         
        insert into #2 ( Node, RelatedNode, Level ) 
           --正向 
            select a.Node,a.RelatedNode,@level+1 
                From RelationGraph a 
                where exists(select 1 from #2 where RelatedNode=a.Node And Level=@level) And 
                    Not exists(select 1 from #2 where Node=a.Node) 
            union 
            --反向 
            select a.RelatedNode,a.Node,@level+1 
                From RelationGraph a 
                where exists(select 1 from #2 where RelatedNode=a.RelatedNode AndLevel=@level) And 
                    Not exists(select 1 from #2 where Node=a.RelatedNode) 
        set @RelatedNode_WhileFlag=sign(@@rowcount) 
  end 
    select @level+=1 
end 
While_Out: 
--下面是構(gòu)造返回的結(jié)果路徑 
if object_id('tempdb..#Path1') Is not null Drop Table #Path1 
if object_id('tempdb..#Path2') Is not null Drop Table #Path2 
;with cte_path1 As 
( 
select a.Node,a.RelatedNode,Level,convert(nvarchar(2000),a.Node+' -> '+a.RelatedNode) AsRelationGraphPath,Convert(smallint,1) As PathLevel 
From #1 a where exists(select 1 from #2where RelatedNode=a.RelatedNode) 
union all 
select b.Node,a.RelatedNode,b.Level,convert(nvarchar(2000),b.Node+' -> '+a.RelationGraphPath) As RelationGraphPath ,Convert(smallint,a.PathLevel+1) 
As PathLevel 
    from cte_path1 a 
        inner join #1 b on b.RelatedNode=a.Node 
            and b.Level=a.Level-1 
) 
select * Into #Path1 from cte_path1 
;with cte_path2 As 
( 
select a.Node,a.RelatedNode,Level,convert(nvarchar(2000),a.Node) AsRelationGraphPath,Convert(smallint,1) As PathLevel 
From #2 a where exists(select 1 from #1where RelatedNode=a.RelatedNode) 
union all 
select b.Node,a.RelatedNode,b.Level,convert(nvarchar(2000),a.RelationGraphPath+' -> '+b.Node) As RelationGraphPath ,Convert(smallint,a.PathLevel+1) 
    from cte_path2 a 
        inner join #2 b on b.RelatedNode=a.Node 
            and b.Level=a.Level-1 
) 
select * Into #Path2 from cte_path2 
;with cte_result As 
( 
select a.RelationGraphPath+' -> '+b.RelationGraphPath AsRelationGraphPath,a.PathLevel+b.PathLevel -1 
As StopCount,rank() over(order bya.PathLevel+b.PathLevel) As Result_row 
    From #Path1 a 
        inner join #Path2 b on b.RelatedNode=a.RelatedNode 
            and b.Level=1 
    where a.Level=1 
)     
select distinct RelationGraphPath,StopCount From cte_result where Result_row=1 
go 

前面的例子，可擴(kuò)展至城市的公交路線，提供兩個(gè)站點(diǎn)，搜索經(jīng)過這兩個(gè)站點(diǎn)最少站點(diǎn)公交路線；可以擴(kuò)展至社區(qū)的人際關(guān)系的搜索，如一個(gè)人與另一個(gè)人想認(rèn)識(shí)，那么他們直接要經(jīng)過多少個(gè)人才可以。除了人與人直接有直接的朋友、親戚關(guān)聯(lián)，還可以通過人與物有關(guān)聯(lián)找到人與人關(guān)聯(lián)，如幾個(gè)作家通過出版一個(gè)本，那么就說明這幾個(gè)人可以通過某一本書的作者列表中找到他們存在共同出版書籍的關(guān)聯(lián)，這為搜索兩個(gè)人認(rèn)識(shí)路徑提供參考。這問題可能會(huì)非常大復(fù)雜，但可以這樣的擴(kuò)展。

這里只是找兩個(gè)節(jié)點(diǎn)的所有路徑中，節(jié)點(diǎn)數(shù)最少的路徑，在實(shí)際的應(yīng)用中，可能會(huì)碰到比這里更復(fù)雜的情況。在其他的環(huán)境或場景可能會(huì)帶有長度，時(shí)間，多節(jié)點(diǎn)，多作用域等一些信息。無論如何，一般都要參考一些原理，算法來實(shí)現(xiàn)。

原文鏈接：http://www.cnblogs.com/wghao/archive/2013/04/23/3036965.html

【編輯推薦】