finding the shortest cycle in a graph

Question

R yan 2015-7-23

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/230900-finding-the-shortest-cycle-in-a-graph

回答： Jaynik 2024-9-5，9:46

hi I am trying to implement the following to find the length of a smallest cycle in a graph G. Please suggest which functions/toolbox are useful for this. I will also be computing how many cycles are there of a particular length. thanks

girth = 1000;
for each edge e(u,v) in G(V,E)
        new_girth = shortestpathlength(G\{e}, u, v) + 1 
                     % shortest distance between u and v
             if (new_girth < = girth)
                girth= new_girth
          G= G U {e}
    end

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Jaynik 2024-9-5，9:46

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/230900-finding-the-shortest-cycle-in-a-graph#answer_1511329

在 MATLAB Online 中打开

Hi @R yan,

You can use the allcycles function on a graph object to find all the cycles in a graph. Once you obtain all the cycles, you can count the number of elements in each cycle and increment a counter variable if they match the required count. Here is a sample code to do the same:

function cycleCount = countCyclesOfLength(G, length)
    % Find all cycles in the graph
    cycles = allcycles(G);
    
    % Count cycles of the specified length
    cycleCount = 0;
    for i = 1:numel(cycles)
        if numel(cycles{i}) == length
            cycleCount = cycleCount + 1;
        end
    end
end