仅从关系图中获取环节点

本文关键字:获取 节点 关系 | 更新日期: 2023-09-27 18:35:47

>我遇到了一个问题,需要我获取环内的节点。我写了一个递归方法,但它没有做我想要的,所以我需要一些帮助。

下图解释了我正在寻找的内容,因为我很难解释它。

给定根节点 0,我想从这些节点获取基本上是 0、1、2、7、8、9 的环

请记住,每个节点都包含连接到它的节点

列表,因此节点 0 同时具有连接到它的节点 1 和节点 9。 所以一切都在那里,但我无法获得正确的逻辑来获得那个戒指。 这是我写的方法,但不幸的是,它不适用于所有图表。

    private bool SetMainRingList(StructureFeature strct, StructureFeature root, List<StructureFeature> mainRing) {
        if ((strct.Equals(root) && mainRing.Contains(strct))) {
            return false;
        }
        var children = strct.GetConnectedStructures();
        if ((children.Contains(root) && mainRing.Contains(strct))) {
            return false;
        }
        mainRing.Add(strct);
        foreach (var structureFeature in children) {
            if (mainRing.Contains(structureFeature)) {
                var strcture = mainRing.Find(x => x.Oid == structureFeature.Oid);
                if (strcture.ParentFeature == null)
                    continue;
                if (strcture.ParentFeature.Equals(root)) {
                    bool skip = false;
                    var crntChildren = strcture.GetConnectedStructures();
                    foreach (var childContainerse in crntChildren) {
                        if (!mainRing.Contains(childContainerse)) {
                            skip = true;
                            break;
                        }
                    }
                    if (!skip)
                        return false;
                }
                continue;
            }
            structureFeature.ParentFeature = strct;
            var leaf = SetMainRingList(structureFeature, root, mainRing);
            var exchangeSite = structureFeature as ExchangeStructure;
            if (leaf && ReferenceEquals(exchangeSite, null)) {
                mainRing.Remove(structureFeature);
            } else {
                return false;
            }
        }
        return true;
    }

仅从关系图中获取环节点

我了解,你有一个图表,需要让参与循环的节点。

在这里,您可以使用寻桥算法并删除形成 bridge.so 的相应节点,最后剩下的节点将形成环。