如何从 Matlab 中的边列表中找到连接的边

Question

我有如下边列表。

75  77
77  78
78  79
60  63
61  65
65  67
57  62
62  64
67  81
81  85

我想按如下方式分离连接的边。

75 60 61 57 
77 63 65 62
78    67 64
79    81
      85

我在 Matlab 中编写了以下代码。

edges = [75 77; 77 78; 78 79; 60 63; 61 65; 65 67; 57 62; 62 64; 67 81; 81 85];
visited = zeros(size(edges,1),1);
cEdges = [];

cEdgesC = 1;
cEdges(1,cEdgesC) = edges(1,1);
cEdges(2,cEdgesC) = edges(1,2);
visited(1,1) = 1;
orgR = 1;
orgC = 2;

while sum(visited) <= size(visited,1)
    cEdgesR = nnz(cEdges(:,cEdgesC));
    currentVertex = cEdges(cEdgesR,cEdgesC);
    fprintf('\n%d\t%d',cEdgesR,currentVertex);

    [foundR,foundC] = find(edges==currentVertex);
    foundR(foundR==orgR) = [];
    foundC(foundC==orgC) = [];

    while isempty(foundR)
        fmt=repmat('%d ',1,cEdgesR);
        fprintf('\nLoop found: ');
        fprintf(fmt,(cEdges(:,cEdgesC))');

        cEdgesC = cEdgesC+1;

        orgR = find(visited==0, 1, 'first');
        orgC = 1;

        cEdges(1,cEdgesC) = edges(orgR,orgC);
        cEdges(2,cEdgesC) = edges(orgR,orgC+1);
        visited(orgR,1) = 1;

        cEdgesR = nnz(cEdges(:,cEdgesC));
        currentVertex = cEdges(2,cEdgesC);
        fprintf('\n%d\t%d',cEdgesR,currentVertex);

        [foundR,foundC]=find(edges==currentVertex);
        foundR(foundR==orgR) = [];
        foundC(foundC==orgC) = [];

        if isempty(foundR)
            // What to do here?
        end
    end

    fprintf('\t%d\t%d',foundR,foundC);
    orgR = foundR;
    if foundC == 1
        cEdges(cEdgesR+1,1) = edges(foundR,foundC+1);
        orgC = foundC+1;
    else
        cEdges(cEdgesR+1,1) = edges(foundR,foundC-1);
        orgC = foundC-1;
    end
    visited(foundR,1) = 1;
end

代码在循环中运行，没有停止。我觉得问题出在内部 while 循环的末尾。如果最后再次满足相同条件，我如何跳回到内部 while 循环的开头？谢谢。

编辑： Example larger matrix of edges.

Answer 1

如果不考虑循环情况和后向连接，这应该是个简单的问题。

edges = [75 77; 77 78; 78 79; 60 63; 61 65; 65 67; 57 62; 62 64; 67 81; 81 85];
NumEdges=size(edges,1);
visited = false(NumEdges,1);
List=cell(0);
k=0;
for i=1:NumEdges
    if ~visited(i)
        k=k+1;
        List{k}=edges(i,1);
        Idx=i;
        while ~isempty(Idx)
            visited(Idx)=true;
            List{k}(end+1)=edges(Idx,2);
            Idx=find(edges(:,1)==edges(Idx,2) & ~visited,1);
        end
    end
end
celldisp(List)

Answer 2

我解决了它，包括循环案例和反向连接。只是想 post 为了任何感兴趣的人。

edges = [75 77; 77 78; 78 79; 60 63; 61 65; 65 67; 57 62; 62 64; 67 81; 81 85];
visited = zeros(size(edges,1),1);
cEdges = [];

cEdgesC = 1;
cEdges(1,cEdgesC) = edges(1,1);
cEdges(2,cEdgesC) = edges(1,2);
visited(1,1) = 1;
orgR = 1;
orgC = 2;

cEdgesR = nnz(cEdges(:,cEdgesC));
currentVertex = cEdges(cEdgesR,cEdgesC);

loops = 0;

while sum(visited) < size(visited,1)
    i=0;
    found=0;
    while i<size(edges,1)
        i=i+1;
        if edges(i,1)==currentVertex && visited(i,1)==0
            cEdgesR = nnz(cEdges(:,cEdgesC));
            cEdges(cEdgesR,cEdgesC)=edges(i,1);
            cEdges(cEdgesR+1,cEdgesC)=edges(i,2);
            currentVertex = cEdges(cEdgesR+1,cEdgesC);
            visited(i,1)=1;
            i=0;
            found=1;
        elseif edges(i,2)==currentVertex && visited(i,1)==0
            cEdgesR = nnz(cEdges(:,cEdgesC));
            cEdges(cEdgesR,cEdgesC)=edges(i,2);
            cEdges(cEdgesR+1,cEdgesC)=edges(i,1);
            currentVertex = cEdges(cEdgesR+1,cEdgesC);
            visited(i,1)=1;
            i=0;
            found=1;
        end
    end
    if found==0
        fprintf('\nloop: ');
        loops = loops+1;
        loopVs = nnz(cEdges(:,loops));
        for j=1:loopVs
            fprintf('\t%d',cEdges(j,loops));
        end
        cEdgesT = cEdges.';
        cEdgesC = nnz(cEdgesT(:,1))+1;
        cEdgesR = 1;
        nextEi = find(visited==0, 1, 'first');
        cEdges(1,cEdgesC) = edges(nextEi,1);
        cEdges(2,cEdgesC) = edges(nextEi,2);
        visited(nextEi,1) = 1;
        currentVertex = cEdges(2,cEdgesC);
    end
end

fprintf('\nno. of loops = %d',loops);