2015-03-03 557 views
1

我需要找到所有帶有圖形的路徑,並保存這些路徑。我的起始節點是A,B或C,最後一個節點是G.我的圖最多有16個未加權的頂點。使用Matlab查找圖形中所有可能的路徑蠻力搜索

我做了下面的Matlab代碼,但這有分叉問題。另外,我不知道如何強制開始節點和最終節點。誰能幫我這個?

path  = cell(1,10) ; % initialize 
% one_graph ={'AH','BO','CN','EG','EN','EO','HO','KN'} % (Graph example) 
one_graph ={'AH','BN','DH','DN','GN'} % (Graph example) 

for p = 1:length(one_graph) 

edge = one_graph(p); 
% In each graph there is only 1:1 conections 
% detect node 1 
existing_node1 = edge{1}(1) ; 
Index_existing_node1 = strfind(allnodes, existing_node1) ; 
[row1,col1] = find(ismember(allnodes, existing_node1)); 
% detect node 2 
existing_node2 = edge{1}(2) ; 
Index_existing_node2 = strfind(allnodes, existing_node2); 
[row2,col2] = find(ismember(allnodes, existing_node2)); 

path_nonz = path(~cellfun('isempty',path)) ; 
t   = length(path_nonz)    ; 
if t>0 % save the first 2 nodes in the path 
ttt = strcmp(allnodes(row1), path{t}); 
ttt2 = strcmp(allnodes(row2), path{t});  
end; 
if t==0 
    path{t+1} = allnodes{row1} ; 
    path{t+2} = allnodes{row2} ; 
elseif ttt == 1 
    % disp('connect right') 
    path{t+1} = allnodes{row2} ; 
elseif ttt2 == 1 
    % disp('connect right') 
    path{t+1} = allnodes{row1} ; 
else 
    disp('Not next vertex') 
end 
end 

例如,對於

one_graph ={'AH','BN','DH','DN','GN'} % (Graph example) 

我應該保存以下路徑:

PATH1 = HDN ģ

PATH2 = Ñģ

one_graph ={'AH','BO','CN','EG','EN','EO','HO','KN'} % (Graph example) 

我應該保存以下路徑:

PATH1 = HOE ģ

PATH2 = OE ģ

path3時= Ç NE ģ

UPDATE 1:

從鄰接矩陣B(:,:,1)

B = 

0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0 
0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0 
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
0  0  0  0  0  0  0  1  0  0  0  0  0  1  0  0 
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0 
1  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0 
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
0  1  0  1  0  0  1  0  0  0  0  0  0  0  0  0 
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 

我導出適當的鄰接表:

Asparse = sparse(B(:,:,1)); 
Asparse = 

(8,1)  1 
(14,2)  1 
(8,4)  1 
(14,4)  1 
(14,7)  1 
(1,8)  1 
(4,8)  1 
(2,14)  1 
(4,14)  1 
(7,14)  1 

然後, 我試過了使用上發現的BFS算法Matlab Website

[distances,times,pred] = bfs(Asparse,1); 

但是,這不保存路徑。它只保存每個當前節點的前一個節點(在pred中)和從初始節點到每個節點的距離(在distances中)。任何想法,如何保存每條路徑?

+1

通常,在圖中查找所有路徑是使用深度優先搜索完成的。我首先將你的圖轉換成一個適當的鄰接表。爲了允許路徑從頂點的子集開始,比如說'{A,B,C}',你可以將這些路徑作爲DFS的第一步推入堆棧,可能會以相反的順序將路徑排序爲更合理。爲了確保在到達端點'G'後不再繼續路徑,請將'G'的鄰接列表清空。一旦找到了所有可能的路徑,刪除那些不以'G'結尾的路徑,如果有的話。 – beaker 2015-03-03 19:01:44

+0

謝謝你的建議!我已經構建了鄰接矩陣。我也將製作鄰接表並嘗試實施DFS。 – Aquila 2015-03-03 19:08:04

+0

@beaker因爲我不擅長編程,所以我試圖使用一個已經實現的BFS版本。你能建議一種方法來保存所有的路徑嗎? – Aquila 2015-03-03 23:01:23

回答

1

我不得不寫一個自定義函數來做到這一點,因爲1)大多數BFS/DFS函數在達到目標時停止,並且2)它們明確地忽略了對於同一目標的多個路徑所需的週期。

我相信這會讓你得到你需要的東西。我已經對示例中的鄰接矩陣進行了一些修改,從{2,7}{7,2}創建邊緣,以便從214有兩條路徑。請注意,這是一個遞歸函數,所以如果你有大約500個節點左右,你將遇到問題,我們將不得不提出一個使用顯式堆棧的版本。

function paths = findpaths(Adj, nodes, currentPath, start, target) 
    paths = {}; 
    nodes(start) = 0; 
    currentPath = [currentPath start]; 
    childAdj = Adj(start,:) & nodes; 
    childList = find(childAdj); 
    childCount = numel(childList); 
    if childCount == 0 || start == target 
     if start == target 
     paths = [paths; currentPath]; 
     end 
     return; 
    end 
    for idx = 1:childCount 
     currentNode = childList(idx); 
     newNodes = nodes; 
     newNodes(currentNode) = 0; 
     newPaths = findpaths(Adj, newNodes, currentPath, currentNode, target); 
     paths = [paths; newPaths]; 
    end 
end 

如果調用此函數是這樣的:

A =[ 
0 0 0 0 0 0 0 1 0 0 0 0 0 0; 
0 0 0 0 0 0 1 0 0 0 0 0 0 1; 
0 0 0 0 0 0 0 0 0 0 0 0 0 0; 
0 0 0 0 0 0 0 1 0 0 0 0 0 1; 
0 0 0 0 0 0 0 0 0 0 0 0 0 0; 
0 0 0 0 0 0 0 0 0 0 0 0 0 0; 
0 1 0 0 0 0 0 0 0 0 0 0 0 1; 
1 0 0 1 0 0 0 0 0 0 0 0 0 0; 
0 0 0 0 0 0 0 0 0 0 0 0 0 0; 
0 0 0 0 0 0 0 0 0 0 0 0 0 0; 
0 0 0 0 0 0 0 0 0 0 0 0 0 0; 
0 0 0 0 0 0 0 0 0 0 0 0 0 0; 
0 0 0 0 0 0 0 0 0 0 0 0 0 0; 
0 1 0 1 0 0 1 0 0 0 0 0 0 0]; 

unusedNodes=ones(1,size(A,1)); 
start=2; 
target=14; 
emptyPath=[]; 

allPaths = findpaths(A, unusedNodes, emptyPath, start, target) 

輸出應該是:

allPaths = 
{ 
    [1,1] = 

     2 7 14 

    [2,1] = 

     2 14 

} 

當然,你需要調用這個對於每個起始節點。


其實,你不必多次調用它。還有一個提示,我忘了告訴你。如果您的圖有n節點,並且您引入了僅包含候選啓動節點的新節點n+1,則可以使用新節點作爲起點調用該函數一次。

所以,如果我添加節點15圖表上方與邊緣:

{15,1}, {15,2} 
%// I wouldn't bother with {1,15} and {2,15}, they're totally unnecessary 

,並調用函數start = 15,這裏就是我得到:

allPaths = 
{ 
    [1,1] = 

    15 1 8 4 14 

    [2,1] = 

    15 2 7 14 

    [3,1] = 

    15 2 14 

} 

您現在擁有的所有路徑只需一次呼叫,但您需要從每個路徑的頭部刪除新節點15

+0

但我需要改進BFS以獲得所有路徑,對吧?如果從節點1到目標節點有兩條路徑會怎麼樣?我的目標節點是7,可能的起始節點是1,2和3. – Aquila 2015-03-03 23:47:27

+0

@Aquila查看新代碼是否適合您。 – beaker 2015-03-04 21:43:34

+0

太棒了!很高興它的工作。從函數中打印出返回值也應該起作用。 (這是我得到我的輸出。) – beaker 2015-03-05 00:38:26