如何在给定的无向图中找到所有循环

Question

我想在图表中找到节点数量不等的循环。为此，我制定了以下算法，该算法执行 dfs 遍历图形，当它找到一个循环时，它会返回并尝试找到与它找到的大循环相交的小循环。

let graph = JSON.parse('{"nodes":[{"x":876,"y":448},{"x":868,"y":564},{"x":845,"y":710},{"x":1050,"y":710},{"x":1075,"y":568},{"x":1087,"y":458},{"x":870,"y":191}],"connections":[{"from":0,"to":1},{"from":1,"to":2},{"from":2,"to":3},{"from":3,"to":1},{"from":3,"to":4},{"from":4,"to":5},{"from":5,"to":0}]}')

const connections = [];

for (let i = 0; i < graph.nodes.length; i++)
    connections.push([]);

for (let i = 0; i < graph.connections.length; i++)
{
    connections[graph.connections[i].to].push(graph.connections[i].from);
    connections[graph.connections[i].from].push(graph.connections[i].to);
}

const visited = [];
const finished = [];
for (let i = 0; i < graph.nodes.length; i++)
{
    visited.push(false);
    finished.push(false);
}
console.clear();
const cycles = []
for(let i = 0; i < graph.nodes.length; i++)
{
    dfs(i)
}
document.write(cycles.map(item => item.join(',')).join('<br>'));


function dfs(node, stack=[])
{
    if(visited[node])
    {
        let position = 0

        for(const stack_node of stack)
        {
            for(const connection of connections[stack_node])
            {
                if(connection == node)
                {
                    let current_stack = [...[...stack].splice(position), node]
                    let i = 0
                    for(; i < current_stack.length; i++)
                            if(current_stack[i] == node)
                            break
                    if(i != current_stack.length-1)
                    current_stack = current_stack.splice(i+1)
                    if(current_stack.length <= 2) continue
                    if(current_stack.length % 2 == 0) continue
                    if(!cycles.find(cycle => cycle.length == current_stack.length && cycle.every((value, index) => value == current_stack[index])))
                    cycles.push(current_stack)
                }
            }
            position ++
        }
        return;
    }
    visited[node] = true;
    for(const connection of connections[node])
    {
        dfs(connection,[...stack, node])
    }
}

图表：

https://i.imgur.com/yWUmh21.png

预期输出

2, 3, 1

1、3、4、5、0

给定输出

2, 3, 1

但它并没有在每个图表上找到所有的 impar 循环。有没有更好的方法来找到无向图上的每个循环？

Answer 1

我为我的问题做了一个解决方案，但如果你想要所有的循环，只需删除 if(current_stack.length % 2 == 0) continue

let graph = JSON.parse('{"nodes":[{"x":876,"y":448},{"x":868,"y":564},{"x":845,"y":710},{"x":1050,"y":710},{"x":1075,"y":568},{"x":1087,"y":458},{"x":870,"y":191}],"connections":[{"from":0,"to":1},{"from":1,"to":2},{"from":2,"to":3},{"from":3,"to":1},{"from":3,"to":4},{"from":4,"to":5},{"from":5,"to":0}]}')
 const connections = [];

for (let i = 0; i < graph.nodes.length; i++)
    connections.push([]);

for (let i = 0; i < graph.connections.length; i++)
{
    connections[graph.connections[i].to].push(graph.connections[i].from);
    connections[graph.connections[i].from].push(graph.connections[i].to);
}

const loops= [];

const globally_visited = Array(graph.nodes.length).fill(false)

for(const node in graph.nodes)
{
    if(!globally_visited[node])
    dfs(node)
}
document.write(loops.map(item=>item.join(', ')).join('<br>'))

function dfs(node,stack=[],visited= [].fill(0, 0, graph.length))
{
    globally_visited[node] = true;
    visited[node] = 1;
    for(const current of connections[node])
    {
        if(visited[current] === 1)
        {
            let current_stack = [...stack,node]
            let i = 0
            for(; i < current_stack.length; i++)
            if(current_stack[i] == current)
            break
            if(i !== current_stack.length)
            {
                current_stack = current_stack.splice(i)
            }
            current_stack = current_stack.map(item=>Number(item));
            if(current_stack.length <= 2) continue
            if(current_stack.length % 2 == 0) continue
            
            for(const loop of loops)
            {
                if(loop.length !== current_stack.length) continue
                let found = false
                for(const number of current_stack)
                {
                    if(!loop.includes(number))
                    {
                        found = true
                        break
                    }
                }
                if(!found) return
            }
            if(connections[current_stack[0]].includes(node))

            loops.push(current_stack);
        }
        else
        {
            dfs(current, [...stack,Number(node)],[...visited]);
        }
    }
}

如何在给定的无向图中找到所有循环

how to find all cycles is in given undirected graph

javascript

algorithm

graph-theory