algorithm - 在图形中查找每个元素可以互相到达的组

我正在编写代码，将网络图转换为可用于生成虚拟网络的配置文件，并且在确定VLAN中的节点时遇到问题。
vlan：一组节点，其中每个节点与组中的每个其他节点都有一个边一个节点可以位于多个VLAN中。
例如：节点A、B、C具有相互连接的边，并被视为VLAN。节点c、d、e具有相互连接的边，并且被认为是另一个vlan。
我的第一个方法是遍历图中所有节点的列表。在每次迭代中，我都会跟踪每条边，看看当前节点的每条边是否是连接节点的边。

//If true, node.edges is a vlan
for node in graph
    for edge in node.edges
        for check_edge in node.edges
            if(check_edge != edge && !(check_edge in edge.edges))
                return false
return true

这看起来真是个糟糕的主意。有什么建议吗？

最佳答案

你所要做的就是找到帮派，这是一个非常hard problem。没有任何假设，你能做的最好的事情就是指数时间我建议查看cliques of a fixed sized算法列表，因为它似乎最适合您想要的（可能）。然而，考虑到你的算法是O(nk^3)有n个节点和k个边，似乎没有明显的改进。重要的是要认识到，找到所有的派系将是一个难以迅速解决的问题。

关于algorithm - 在图形中查找每个元素可以互相到达的组，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24545288/