c# - 按连接度划分图

Question

我想问一下是否已经有图的算法将图划分为子图，如所附的屏幕截图:

图有边A-B,B-C,C-D,D-E,C-F,F-G

我需要将它分成 3 个部分，因为顶点 C 的度数为 3:A-B-CC-D-EC-F-G

首先，我想我可以使用典型方法删除 C 节点并断开图。但是也许已经有已知的方法可以按节点度划分图？

Answer 1

我为此编写了一个简单的算法。请注意，图表需要订购

public static void Main()
{
    Console.WriteLine("Hello World");
    var str = "A-B,B-C,C-D,D-E,C-F,F-G";
    var resultSet = Graph(str.Split(','), '-');

}


public static string[] Graph(string[] s, char delimiter)
{
    var resultSet = new List<string>();

    var prevOperLeft = "";
    var prevOperRight = "";

    foreach (var part in s)
    {
        var oper = part.Split(delimiter);
        var left = oper[0];
        var right = oper[1];

        if (prevOperRight == left)
        {
            resultSet.Add(string.Format("{0}{1}{2}{3}{4}", prevOperLeft, delimiter, left, delimiter, right));
            prevOperLeft = prevOperRight = "";
        }
        else
        {
            prevOperLeft = left;
            prevOperRight = right;
        }
    }

    return resultSet.ToArray();
}

https://dotnetfiddle.net/e3kmpR

更通用的 LinkedList 示例

public static IList<LinkedList<T>> Graph2<T>(LinkedList<T> ll) where T: class
{
    var resultSet = new List<LinkedList<T>>();

    T prevOperLeft = null;
    T prevOperRight = null;

    while (ll.Count > 0) 
    {
        var left = ll.First.Value;
        ll.RemoveFirst();
        var right = ll.First.Value;
        ll.RemoveFirst();

        if (prevOperRight != null && prevOperRight.Equals(left))
        {
            resultSet.Add(new LinkedList<T>(new []{ prevOperLeft, left, right }));
            prevOperLeft = prevOperRight = null;
        }
        else
        {
            prevOperLeft = left;
            prevOperRight = right;
        }
    }

    return resultSet;
}

public static void Main()
{
    var A = new MyClass {Name = "A"};
    var B = new MyClass {Name = "B"};
    var C = new MyClass {Name = "C"};
    var D = new MyClass {Name = "D"};
    var E = new MyClass {Name = "E"};
    var F = new MyClass {Name = "F"};
    var G = new MyClass {Name = "G"};

    List<MyClass> list = new List<MyClass>
    {
         A,B,B,C,C,D,D,E,C,F,F,G
    };

    LinkedList<MyClass> ll = new LinkedList<MyClass>(list);
    var resultSet2 = Graph2(ll);
}

class MyClass
{
    public string Name { get; set; }
}