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

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);

应该return修改后的（if cycle found）邻接矩阵，G_dash和c_flag对应是否找到环

但是，它似乎没有正常运行。

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

有没有人有什么想法？

Answer 1

连通的、无向的、无环图称为tree, with n nodes and n - 1 edges. For a formal proof, see here。

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

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

Removing edge that causes a cycle in an undirected graph

algorithm

matlab

graph-theory