删除无向图中导致循环的边

Question

我有一个由邻接矩阵表示的图，G我尝试使用 DFS 删除导致循环的边

可以有多个循环，但我认为最好一次删除它们，所以我只需要我的算法找到一个循环，并且可以重复。

这是我到目前为止所得到的代码：

function [ G, c_flag, c_stack, o_stack, cptr, optr ] =...
    dfs_cycle( G, curr_v, c_stack, o_stack, cptr, optr, c_flag )

    % add current vertex to open list
    optr = optr + 1;
    o_stack(optr) = curr_v;

    % find adjacent vertices
    adj_v = find(G(curr_v,:));

    for next_v = adj_v
        % ensure next_v is not in closed list
        if ~any(c_stack == next_v)
            % if next_v in open list then cycle exists
            if any(o_stack == next_v)
               % remove edge and set flag to 1
               G(curr_v, next_v) = 0;
               G(next_v, curr_v) = 0;
               c_flag = 1;
               break;
            end

            [G, c_flag, c_stack, o_stack, cptr, optr] =...
                dfs_cycle(G, next_v, c_stack, o_stack, cptr, optr, c_flag);

            if c_flag == 1
                break;
            end

            % remove vertex from open list and put into closed list
            o_stack(optr) = 0;
            optr = optr - 1;
            cptr = cptr + 1;
            c_stack(cptr) = next_v;
        end
    end
end

使用以下方式调用该函数：

v_list = find(sum(G)>0);
o_stack = zeros(1,numel(v_list));
c_stack = o_stack;
optr = 0;
cptr = 0;
root_v = v_list(randperm(length(v_list),1));
c_flag = 0;
[G_dash,c_flag,~,~,~,~] =...
    dfs_cycle(G, root_v, c_stack, o_stack, cptr, optr, c_flag);

它应该返回修改后的（如果找到环路）邻接矩阵，G_dash以及对应于是否找到环路的 c_flag。

然而，它似乎并没有发挥应有的作用。

我想我已经找到了问题所在；在该行中if any(o_stack == next_v)它将返回 true，因为之前访问的顶点通常仍在 中o_stack，但是我不确定应该如何解决这个问题。

有人有什么想法吗？

Answer 1

连通的无向无环图称为树，具有 n 个节点和 n - 1 个边。有关正式证明，请参见此处。

因此，要从图中形成一棵树，您只需运行一次 DFS，并保留此 DFS 使用的所有边（有关 DFS 创建的树的更多信息，请参阅wiki 链接，示例部分）。那些未使用的边缘可以被删除。