使用 Matlab 蛮力搜索在图中查找所有可能的路径

Question

我需要找到所有带有图形的路径，并保存这些路径。我的起始节点是 A、B 或 C，最终节点是 G。我的图最多有 16 个未加权的顶点。

我在下面制作了 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 = AHDNG

path2 = BNG

和

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

我应该保存以下路径：

path1 = AHOEG

path2 = BOEG

path3 = CNEG

更新 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

然后，我尝试使用在 Matlab Website

上找到的 BFS 算法

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

但是，这不会保存路径。它只是保存了每个当前节点的前一个节点（在pred中）和从初始节点到每个节点的距离（在distances中）。任何想法，如何保存每条路径？

Answer 1

我不得不编写一个自定义函数来执行此操作，因为 1) 大多数 BFS/DFS 函数在达到目标时停止，并且 2) 它们显式地忽略了循环，这是通向相同路径的多条路径所必需的目标。

我相信这会让你得到你需要的。我对您示例中的邻接矩阵进行了轻微修改，以创建从 {2,7} 和 {7,2} 的边，以便从 2 到 14 有两条路径。请注意，这是一个递归函数，所以如果你有大约 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。

使用 Matlab 蛮力搜索在图中查找所有可能的路径

Find all possible paths in a graph using Matlab Brute Force Search

matlab

graph

brute-force

search-path