Graph中有四个循环 [英] Four cycles in Graph

问题描述

我需要编写一个方法来查找无向图中4个周期的计数（包含4个边的周期）。如果您对算法有任何了解，请给我一些建议。

I need to write a method to find the count of 4 cycles(cycles containing 4 edges) in an undirected graph. Please give me some advices if you have any idea about the algorithm.

推荐答案

参见 Robert Sedgewick [ ^ ]的书单：第5部分：图形算法是要阅读的书（你选择：C，C ++，Java）。如果你用C＃编写本书的所有代码，这将是一个很好的练习。 ;-)

干杯

Andi

See Robert Sedgewick[^]''s book list: Part 5: Graph Algorithms is the book to read (you choose: C, C++, Java). It would be a nice exercise if you write all the code of the book in C#. ;-)
Cheers
Andi

我自己做了。该算法使用DFS。并且在每一步中它都进入4个级别，并查找找到的顶点是否与完成该步骤的顶点相同。在正式语言中，它应该是这样的：

I have done this myself. The algorithm uses DFS. And on every step it goes 4 levels and finds if the found vertex is the same as the one for which is done the step. In formal language it should be something like this:

for path in dfs(start=node, max_depth=4):
        if len(path) == 4 and path[1] == path[4]:
            output.append(path)

这篇关于Graph中有四个循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！