你如何从递归函数中获得所有 children 的输出？

Question

我正在尝试编写一个脚本来查找典型最大流问题中从源到汇的所有路径。此总体将作为 Ford-Fulkerson 算法实施的第 1 步，作为 class.

的项目

我已经完成了一些基本的调试，但似乎正在发生的事情是该算法没有生成所有应该通过 for 循环生成的 children，而只是找到了相同的路径 a几次然后终止。

#pathfinder
function final=pathFinder(A,path) #call with path=1 to initiate
    #A is a matrix that looks like
    # u v w where uv is an edge, and w is its weight (weight is used later)
    vert=path(numel(path)); #get last vertex used
    F=find(A(:,1)'==vert); #find incident edges
    disp("F is");
    disp(F); #displaying these for debugging purposes
    if(sum(F)==0) #terminates with no more edges (happens only at sink)
      #save externally
      disp("path found!");
      disp(path);
      final=0; #terminate it
    else
     for i=1:numel(F) #this should split this up in "children" for recursion, but it does not. Why?
        b=F(i);
        path=[path, A(b,2)]; #add new vertex/edge to path
        disp("non-final path");
        disp(path);
        disp("going deeper");
        final=pathFinder(A,path); #recurs on next vertex
     endfor
    endif
endfunction

我使用的示例图是

A=[1 2 0; 1 3 0; 2 3 0; 2 4 0; 3 4 0];

应该有路径 [1 2 3 4]、[1 2 4]、[1 3 4]（按照算法的顺序）。

Answer 1

您的代码有两个问题：

vert=path(numel(path)) 表示沿路径的元素数是您要从的顶点索引。这是错误的。您需要使用 vert=path(end)，路径中的最后一个元素。
在循环中，您更新 path。因此，在下一个循环迭代中，您将使用修改后的 path，而不是回溯。您需要修改下一个递归调用的 path 输入，而不是本地 path 变量。

这是更正后的代码：

function pathFinder(A,path) % call with path=1 to initiate
   % A is a matrix that looks like
   %  u v w where uv is an edge, and w is its weight (weight is used later)
   vert=path(end); % get last vertex used
   F=find(A(:,1)'==vert); % find incident edges
   if isempty(F) % terminates with no more edges (happens only at sink)
      % save externally
      disp(path);
   else
      for b=F % loop over the incident edges
         pathFinder(A,[path, A(b,2)]); % recurse on next vertex
      end
   end
end

^{为简洁起见，我删除了调试输出。我还将一些仅限 Octave 的内容（endfor、# 注释）更改为在 MATLAB 中也将运行的内容。}

你如何从递归函数中获得所有 children 的输出？

How do you get output from all children in recursive function?

octave