1

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

我在下面制作了 Matlab 代码，但这有bifurcations的问题。另外，我不知道如何强加起始节点和最终节点。谁能帮我这个？

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)

我应该保存以下路径：

路径 1 =一个HDN G

路径2 = B N G

并且对于

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

我应该保存以下路径：

路径 1 =一个HOE G

路径 2 = B OE G

路径 3 = C NE G

更新 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 网站上的 BFS 算法

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

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

4

1 回答 1

1

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

我相信这会给你你所需要的。在您的示例中，我对邻接矩阵进行了轻微修改，以创建一条边 from{2,7}和，{7,2}以便有两条路径 from2到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从每个路径的头部删除新节点。

于 2015-03-03T23:44:41.353 回答