2

GraphPartition截图

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

图有边 AB、BC、CD、DE、CF、FG

我需要将它划分为 3 个部分,因为顶点 C 的度数为 3:ABC CDE CFG

首先,我认为我可以使用典型方法删除 C 节点并断开图。但也许有已知的方法来按节点度划分图?

4

1 回答 1

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; }
}
于 2018-12-25T22:09:16.530 回答