MATLAB 矩阵中两个节点之间的所有可能路径

Question

我有一个矩阵，其中包含四个列1链接号（现在不重要），列2：开始，列3：结束和列4如果大于0 ->则节点已连接。我写了一个递归代码，但它没有正确显示输出：例如：在节点 1 和 18 之间，它输出

path=[1 2 6 8 16 18] % which is correct
path=[1 2 6 8 16 7 18] % from 8 there are two paths (16 and 7)- it shouldnt show 16 anymore
% the code is
function findpaths(Matrix,start, destination,pathD)
if(start==destination)
   pathD % have a problem in storing them too (it just outputs now)
   return
end
    % to find all the rows that have start 
    % then it can find all the nodes connected to start 
    % if start is 6 then it return 4 and 9th row where 
    %there are 8 and 5 connected to 6 in those rows
    [row] = find(Matrix(:,2)==start); % to find all the rows that have this node
        for i=1:size(row,1) % adjecent nodes to start
            if Matrix(row(i),4)>0 % condition to see if the nodes are connected
                adj_node = Matrix(row(i),3);  % the adjacent node              
                if ismember(adj_node, pathD)==0
                    pathD;
                    pathD = [pathD adj_node];
                    start = adj_node;
                    findpaths(Matrix,start,destination,pathD);
                end
            end
        end
   end 

下面是矩阵

1   1   2   1
2   1   3   0
4   2   6   1
16  6   8   1
6   3   4   0
7   3   12  0
21  8   9   0
10  4   11  0
15  6   5   0
22  8   16  0.5
20  8   7   0.5
37  12  13  0
32  11  10  0
25  9   10  0
49  16  17  0
18  7   18  0.5
28  10  15  0
50  16  18  0.5
34  11  14  0
53  17  19  0
39  13  24  0
46  15  22  0
56  18  20  0
42  14  23  0
76  24  23  0
62  20  21  0
69  22  21  0

Answer 1

大多数算法，至少是我发现的算法，实现BFS或DFS的算法将输出它们访问的节点 - 例如，当访问死胡同时，回溯时，死胡同节点也真正显示在路径中。主要问题是在 matlab 中创建队列数据结构;我找不到任何有用的可用队列实现，所以我使用了结构（我确定这不是一种非常有效的方法，但我需要以以下格式将数据存储在 matlab 中，例如：

[['1', '4', '8'], ['1', '2', '5', '9'], ['1', '2', '5', '10'], ['1', '4', '7', '11']]
the Pseudo code is:
function [nodes,links] = bfs4(GRAPH, start, destination)% def BFS(graph,start,end,q):
nodes=struct;
links=struct;
path = struct;
temp_path = start;

last_node=[];
% q.enqueue(temp_path)
path(1).data = temp_path;

    while size(fieldnames(path),1)~=0
        tmp_path = path(1).data;
        if length(path) == 1
            path=struct;
        else
            path = path(2:end);
        end
        last_node = tmp_path(end);
    %         Storing the nodes in Two Forms (NODEs) and (LINKs)
        if last_node == destination
             tmp_path;
             if size(fieldnames(nodes),1)==0
             nodes(end).data=tmp_path
             else
                nodes(end+1).data=tmp_path
             end
%             taking the links 
         link=[];
            for i=1:(length(tmp_path)-1)
                link(i) = GRAPH(GRAPH(:,2)==tmp_path(i) & GRAPH(:,3)==tmp_path(i+1));
            end
            if size(fieldnames(links),1)==0
                links(end).data=link;
            else
                links(end+1).data=link;
            end
        end
        [row] = find(GRAPH(:,2)==last_node);
        for i=1:size(row,1)
     %              be careful -- the condition to be remove GRAPH(row(i),10)>0
             if   GRAPH(row(i),10)>0 && ismember(GRAPH(row(i),3),tmp_path)==0  
                   new_path=[];
                   new_path = [tmp_path GRAPH(row(i),3)];
                   if size(fieldnames(path),1)==0
                       path(end).data = new_path;
                   else
                       path(end+1).data = new_path;
                   end
             end
        end
    end % while
end % function