我需要找到所有帶有圖形的路徑,並保存這些路徑。我的起始節點是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
中)。任何想法,如何保存每條路徑?
通常,在圖中查找所有路徑是使用深度優先搜索完成的。我首先將你的圖轉換成一個適當的鄰接表。爲了允許路徑從頂點的子集開始,比如說'{A,B,C}',你可以將這些路徑作爲DFS的第一步推入堆棧,可能會以相反的順序將路徑排序爲更合理。爲了確保在到達端點'G'後不再繼續路徑,請將'G'的鄰接列表清空。一旦找到了所有可能的路徑,刪除那些不以'G'結尾的路徑,如果有的話。 – beaker 2015-03-03 19:01:44
謝謝你的建議!我已經構建了鄰接矩陣。我也將製作鄰接表並嘗試實施DFS。 – Aquila 2015-03-03 19:08:04
@beaker因爲我不擅長編程,所以我試圖使用一個已經實現的BFS版本。你能建議一種方法來保存所有的路徑嗎? – Aquila 2015-03-03 23:01:23