Search code examples
c++algorithmgraphcycle

4 cycles in undirected graph

I have an undirected graph which is given as a neighbourship matrix. I need to find the count of 4 cycles: the cycles which contain 4 edges. If you have any idea about the algorithm, please help me.

Solution

  • Simple (not optimal) approach pseudo code:

    output = []
skip_nodes = []
for node in input_graph:
    if node in skip_nodes:
        continue
    for path in deep_search(start=node, max_depth=4):
        if len(path) == 4 and path[1] == path[4]:
            output.append(path)
            skip_nodes.append(path[2], path[3], path[4])
return output