【数据结构问题】二流码农求助，只会编码，数据结构不甚懂

现在会写代码的人虽多，真正可以精通数据结构的却不多，遇到个问题，求助。
有多条线段，需要根据线段是否相接，将线段重构为新的线段，相接的合并为一条。
如图：有12条线段，有相接的和不想接的部分，现在的目的就是把这些线最终合并为3条线，和并原则就是线段是否相接，结果为：1-6为一条，7为一条，9到12为一条。
判断线是否相接已经处理好，就是没有弄清楚这里面的循环遍历关系，求助有没有经典的算法结构或者思路可以解决这类问题，多谢啦。

70 个解决方案

#1

我是不是可以认为这些都是只有一个子节点的树……

#2

一条线段有两个端点
如果两条线段相接，则必然会有成对的端点在端点集合中出现
因此只需一个双重循环就可找到全部相接的线段

#3

如果‘相连’是判断端点相接，那么就比较简单。

1、可以用一个HashSet<Point>作为连通组，来放连通线段的端点。
2、如果一条新线段的任一端点，在某一个连通组中可以找到，那么该线段（的两个端点）就加入该连通组。
3、如果一条新线段的任一端点，在多个连通组中可以找到，那么就合并多个连通组，并加入该线段。
4、最后连通组的个数等，就给出了连通拓扑结构。

#4

给你写了一个例子

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            var db = new DB
            {
                {"1","a","b" }, {"2", "b","c" },{"3", "c","d" },
                {"4","d","g" }, {"5", "g","h" },{"6","h","i" }, {"7", "k","l" },
                {"9","n","o" }, {"10", "o","p" },{"11","p","q" }, {"12", "q","r" },
            };
            var result = 路径(db);
            var cnt = 0;
            foreach (var r in result)
            {
                Console.Write("路径 {0}: ", ++cnt);
                var first = true;
                foreach (var p in r)
                {
                    if (!first)
                        Console.Write("->");
                    else
                        first = false;
                    Console.Write("{0}", p);
                }
                Console.WriteLine();
            }
            Console.Write("Press any key to continue . . . ");
            Console.ReadKey(true);
        }

        private static IEnumerable<IEnumerable<string>> 路径(DB db)
        {
            var 所有路径的起点 = from x in db
                        where !db.Any(y => y.End == x.Start) //没有其它path是以x点为终点的
                        select x.Start;
            foreach (var n in 所有路径的起点)
                foreach (var result in 路径(db, n))
                    yield return result;
        }

        private static IEnumerable<IEnumerable<string>> 路径(DB db, string 起点)
        {
            var paths = (from x in db
                         where x.Start == 起点
                         select x).ToList();
            if (paths.Count == 0)
                yield return new string[0];
            else
                foreach (var p in paths)
                    foreach (var r in 路径(db, p.End))    //递归查找从p.End为起点的所有路径
                        yield return new string[] { p.Name }.Concat(r);     //将p点与r路径组合在一起，然后返回
        }
    }

    public class Path
    {
        public string Name;
        public string Start;
        public string End;
    }

    public class DB : IEnumerable<Path>
    {
        private List<Path> ps = new List<Path>();

        public void Add(string name, string start, string end)
        {
            ps.Add(new Path { Name = name, Start = start, End = end });
        }

        public IEnumerator<Path> GetEnumerator()
        {
            return ps.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }
    }
}

#5

数据结构在最下边，两个class的定义。

算法在中间，两个method方法用来寻找并遍历所有路径。（这里没有判断“死循环”情况，你可以自己加上。例如简单地用最大长度来控制算法必定会结束）

最顶上的Main方法中的代码是简单的测试打印。

#6

例如我们增加2条新的路径到这个题目的数据库中，你可以重新看看计算结果

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            var db = new DB
            {
                {"1","a","b" }, {"2", "b","c" },{"3", "c","d" },
                {"4","d","g" }, {"5", "g","h" },{"6","h","i" }, {"7", "k","l" },
                {"9","n","o" }, {"10", "o","p" },{"11","p","q" }, {"12", "q","r" },
                {"新1","g","p" },{"新2","g","k" }
            };
            var result = 路径(db);
            var cnt = 0;
            foreach (var r in result)
            {
                Console.Write("路径 {0}: ", ++cnt);
                var first = true;
                foreach (var p in r)
                {
                    if (!first)
                        Console.Write("->");
                    else
                        first = false;
                    Console.Write("{0}", p);
                }
                Console.WriteLine();
            }
            Console.Write("Press any key to continue . . . ");
            Console.ReadKey();
        }

        private static IEnumerable<IEnumerable<string>> 路径(DB db)
        {
            var 所有路径的起点 = from x in db
                        where !db.Any(y => y.End == x.Start) //没有其它path是以x点为终点的
                        select x.Start;
            foreach (var n in 所有路径的起点)
                foreach (var result in 路径(db, n))
                    yield return result;
        }

        private static IEnumerable<IEnumerable<string>> 路径(DB db, string 起点)
        {
            var paths = (from x in db
                         where x.Start == 起点
                         select x).ToList();
            if (paths.Count == 0)
                yield return new string[0];
            else
                foreach (var p in paths)
                    foreach (var r in 路径(db, p.End))    //递归查找从p.End为起点的所有路径
                        yield return new string[] { p.Name }.Concat(r);     //将p点与r路径组合在一起，然后返回
        }
    }

    public class Path
    {
        public string Name;
        public string Start;
        public string End;
    }

    public class DB : IEnumerable<Path>
    {
        private List<Path> ps = new List<Path>();

        public void Add(string name, string start, string end)
        {
            ps.Add(new Path { Name = name, Start = start, End = end });
        }

        public IEnumerator<Path> GetEnumerator()
        {
            return ps.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }
    }
}

#7

不就是把有端点重叠的放一组吗，，

#8

是不是呢123456888

#9

我感觉用链表的思路就行了，反正你这个不是二叉树
判断三条线是不是正常的话，要分两步：
第一步，判断每一条链表是否有断开的地方，并且链表是否正确链接
第二部，判断每一条的链表首和尾，是否是你想要的，比如第一个链表的头是否是线条1，尾部是否是条线2

以上两步判断完了之后就可以了，代码就不写了，思路在这里
感觉这个跟数据结构关系不大，就是一个设计思路而已

#10

写的好，对我有很大的帮助

#11

这个看起来很复杂的样子，因为没有说明各线段的连接情况。例如出现环就有点麻烦了，另外出现分支时怎么算的？因为题目没有说太清楚。所以最糟糕的可以考虑用图吧，然后遍历图。

#12

该回复于2015-08-14 13:11:14被管理员删除

#13

首先非常感谢，我也深深认识到了自己有多菜。你的代码我也详细的读完了，也测试过了，没有问题。现在的问题是我的原数据是没有方向的，我只能知道线段的两个端点，像你测试数据中那种带有顺序的结构是构造不出来的。具体到你的代码的话就是要弱化程序中的start和end属性，只有2个点，到底是start还是end是不能确定的，你的测试数据正好是顺序拍下来的，把其中的start和end换个位置的话结果就不对了。

引用 4 楼 sp1234 的回复:

给你写了一个例子

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            var db = new DB
            {
                {"1","a","b" }, {"2", "b","c" },{"3", "c","d" },
                {"4","d","g" }, {"5", "g","h" },{"6","h","i" }, {"7", "k","l" },
                {"9","n","o" }, {"10", "o","p" },{"11","p","q" }, {"12", "q","r" },
            };
            var result = 路径(db);
            var cnt = 0;
            foreach (var r in result)
            {
                Console.Write("路径 {0}: ", ++cnt);
                var first = true;
                foreach (var p in r)
                {
                    if (!first)
                        Console.Write("->");
                    else
                        first = false;
                    Console.Write("{0}", p);
                }
                Console.WriteLine();
            }
            Console.Write("Press any key to continue . . . ");
            Console.ReadKey(true);
        }

        private static IEnumerable<IEnumerable<string>> 路径(DB db)
        {
            var 所有路径的起点 = from x in db
                        where !db.Any(y => y.End == x.Start) //没有其它path是以x点为终点的
                        select x.Start;
            foreach (var n in 所有路径的起点)
                foreach (var result in 路径(db, n))
                    yield return result;
        }

        private static IEnumerable<IEnumerable<string>> 路径(DB db, string 起点)
        {
            var paths = (from x in db
                         where x.Start == 起点
                         select x).ToList();
            if (paths.Count == 0)
                yield return new string[0];
            else
                foreach (var p in paths)
                    foreach (var r in 路径(db, p.End))    //递归查找从p.End为起点的所有路径
                        yield return new string[] { p.Name }.Concat(r);     //将p点与r路径组合在一起，然后返回
        }
    }

    public class Path
    {
        public string Name;
        public string Start;
        public string End;
    }

    public class DB : IEnumerable<Path>
    {
        private List<Path> ps = new List<Path>();

        public void Add(string name, string start, string end)
        {
            ps.Add(new Path { Name = name, Start = start, End = end });
        }

        public IEnumerator<Path> GetEnumerator()
        {
            return ps.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }
    }
}

#14

该回复于2015-09-30 23:47:55被版主删除

#15

引用 3 楼 Forty2 的回复:

如果‘相连’是判断端点相接，那么就比较简单。

1、可以用一个HashSet<Point>作为连通组，来放连通线段的端点。
2、如果一条新线段的任一端点，在某一个连通组中可以找到，那么该线段（的两个端点）就加入该连通组。
3、如果一条新线段的任一端点，在多个连通组中可以找到，那么就合并多个连通组，并加入该线段。
4、最后连通组的个数等，就给出了连通拓扑结构。

  嗯，思路明白了，具体实现的时候，我想再问一哈如何动态的管理和合并联通组，用什么数据类型，我能想到最简单的就是用arraylist存放hashset<point>,先遍历每一条线段，在线段里面遍历arraylist，没有找到的就新建hashset，找到了就添加或者合并arraylist。是这样吗？

#16

引用 3 楼 Forty2 的回复:

如果‘相连’是判断端点相接，那么就比较简单。

1、可以用一个HashSet<Point>作为连通组，来放连通线段的端点。
2、如果一条新线段的任一端点，在某一个连通组中可以找到，那么该线段（的两个端点）就加入该连通组。
3、如果一条新线段的任一端点，在多个连通组中可以找到，那么就合并多个连通组，并加入该线段。
4、最后连通组的个数等，就给出了连通拓扑结构。

用这个思路实现了哈，首先定义保存结果的ResultPolyline类，类中HashSet保存有链接关系的所有起止点，List<IPolyline>保存这些点所在的线。然后遍历原始的所有线，可以在已有的ResultPolyline里面找到点的就把线添加到该ResultPolyline，找不到的就新建ResultPolyine。最后得到存放所有ResultPolyline的List.
public class HashSetDivide
    {
        struct ResultPolyline
        {
            public List<IPolyline> PolylineParts = new List<IPolyline>();
            public HashSet<IPoint> PolylineHashSet = new HashSet<IPoint>();
        }
        public List<ResultPolyline> methods(List<IPolyline> input_polylines)
        {
            List<ResultPolyline> all_result_lines = new List<ResultPolyline>();
            foreach (IPolyline per_input_line in input_polylines)
            {
                if (all_result_lines.Count == 0)
                {
                    ResultPolyline per_result_line = new ResultPolyline();
                    per_result_line.PolylineParts.Add(per_input_line);
                    per_result_line.PolylineHashSet.Add(per_input_line.FromPoint);
                    per_result_line.PolylineHashSet.Add(per_input_line.ToPoint);
                    all_result_lines.Add(per_result_line);
                }
                else
                {
                    bool flag = true;
                    foreach (ResultPolyline per_result_line in all_result_lines)
                    {
                        if (per_result_line.PolylineHashSet.Contains(per_input_line.FromPoint) | per_result_line.PolylineHashSet.Contains(per_input_line.ToPoint))
                        {
                            per_result_line.PolylineParts.Add(per_input_line);
                            per_result_line.PolylineHashSet.Add(per_input_line.FromPoint);
                            per_result_line.PolylineHashSet.Add(per_input_line.ToPoint);
                            flag = false;
                        }
                    }
                    if (flag)
                    {
                        ResultPolyline per_result_line = new ResultPolyline();
                        per_result_line.PolylineParts.Add(per_input_line);
                        per_result_line.PolylineHashSet.Add(per_input_line.FromPoint);
                        per_result_line.PolylineHashSet.Add(per_input_line.ToPoint);
                        all_result_lines.Add(per_result_line);
                    }
                }
            }
            return all_result_lines;
        }
    }

#17

该回复于2016-03-31 23:53:07被版主删除

#18

该回复于2016-03-31 23:53:22被版主删除

#19

很好，不错！

#20

可以参考并查集(很经典的)

#21

该回复于2015-08-15 12:57:37被管理员删除

#22

如果只是“联通”而根本不需要绘制出路径，那么你在问题中描述花费精力去说明的“线段路径”就是个误导的概念了。

找到联通的线段分组，这个算法就更加简单（中间的两个method）：

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            var db = new DB
            {
                {"1","a","b" }, {"2", "b","c" },{"3", "c","d" },
                {"4","d","g" }, {"5", "g","h" },{"6","h","i" }, {"7", "k","l" },
                {"9","n","o" }, {"10", "o","p" },{"11","p","q" }, {"12", "q","r" },
            };
            var result = 分组(db);
            var cnt = 0;
            foreach (var r in result)
            {
                Console.Write("分组 {0}: ", ++cnt);
                var first = true;
                foreach (var p in r)
                {
                    if (!first)
                        Console.Write("->");
                    else
                        first = false;
                    Console.Write("{0}", p);
                }
                Console.WriteLine();
            }
            Console.Write("Press any key to continue . . . ");
            Console.ReadKey();
        }

        private static IEnumerable<IEnumerable<string>> 分组(DB db)
        {
            loop:
            var n = db.FirstOrDefault();
            if (n != null)  //存在一个没有访问过的 Path
            {
                var visited = new List<Path>();
                删除联通(db, n, visited);
                yield return visited.Select(x => x.Name);
                goto loop;
            }
        }

        private static void 删除联通(DB db, Path current, List<Path> visited)
        {
            if (!visited.Contains(current))
            {
                visited.Add(current);
                db.Remove(current);
                var paths = (from x in db
                             where x.End == current.Start || x.Start == current.End
                             select x).ToList();
                if (paths.Count > 0)
                {
                    foreach (var x in paths)
                        删除联通(db, x, visited);
                }
            }
        }
    }

    public class Path
    {
        public string Name;
        public string Start;
        public string End;
    }

    public class DB : IEnumerable<Path>
    {
        private List<Path> ps = new List<Path>();

        public void Add(string name, string start, string end)
        {
            ps.Add(new Path { Name = name, Start = start, End = end });
        }

        public void Remove(Path x)
        {
            ps.Remove(x);
        }

        public IEnumerator<Path> GetEnumerator()
        {
            return ps.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }
    }
}

算法部分（两个method）不但简单，而且你应该观察一下输出结果的速度。


如果增加一个新的节点，重新看看输出结果，更有意义。

var db = new DB
{
    {"1","a","b" }, {"2", "b","c" },{"3", "c","d" },
    {"4","d","g" }, {"5", "g","h" },{"6","h","i" }, {"7", "k","l" },
    {"9","n","o" }, {"10", "o","p" },{"11","p","q" }, {"12", "q","r" },
        {"新1","g","p" }
};

#23

这里强调的是“算法”，也就是中间两个 method。可以对比一下程序的写法。

如果写的越简单、越傻瓜化，就越容易理解和维护。

#24

实际上，分组并不是找到具体的路径。假设把上面的 {"新1","g","p" } 路径加入 DB，如果是找到路径，那么结果就应该多出来新的分支路径，而分组结果则正相反，结果分支变少了。

因此如果在问题中没有搞明白到底是简单地联通分组、还是寻找路径，那么就会产生完全不一样的算法。错误的假设会使得应用推倒重来。

另外，算法其实不适合高达上地动不动就用“集合方式”去推导。用集合方式，顶多只是“证明”方法，而不是好的“发现”方法。用集合方式的算法与迭代方式的算法相比，不但不能支持“延迟计算”等等特性，而且通常都非常慢。

#25

很好不错。 感谢

#26

懂了，O(∩_∩)O谢谢

#27

引用 16 楼 JingPrayer的回复:

Quote: 引用 3 楼 Forty2 的回复:

如果‘相连’是判断端点相接，那么就比较简单。

1、可以用一个HashSet<Point>作为连通组，来放连通线段的端点。
2、如果一条新线段的任一端点，在某一个连通组中可以找到，那么该线段（的两个端点）就加入该连通组。
3、如果一条新线段的任一端点，在多个连通组中可以找到，那么就合并多个连通组，并加入该线段。
4、最后连通组的个数等，就给出了连通拓扑结构。

用这个思路实现了哈，首先定义保存结果的ResultPolyline类，类中HashSet保存有链接关系的所有起止点，List<IPolyline>保存这些点所在的线。然后遍历原始的所有线，可以在已有的ResultPolyline里面找到点的就把线添加到该ResultPolyline，找不到的就新建ResultPolyine。最后得到存放所有ResultPolyline的List.
public class HashSetDivide
    {
        struct ResultPolyline
        {
            public List<IPolyline> PolylineParts = new List<IPolyline>();
            public HashSet<IPoint> PolylineHashSet = new HashSet<IPoint>();
        }
        public List<ResultPolyline> methods(List<IPolyline> input_polylines)
        {
            List<ResultPolyline> all_result_lines = new List<ResultPolyline>();
            foreach (IPolyline per_input_line in input_polylines)
            {
                if (all_result_lines.Count == 0)
                {
                    ResultPolyline per_result_line = new ResultPolyline();
                    per_result_line.PolylineParts.Add(per_input_line);
                    per_result_line.PolylineHashSet.Add(per_input_line.FromPoint);
                    per_result_line.PolylineHashSet.Add(per_input_line.ToPoint);
                    all_result_lines.Add(per_result_line);
                }
                else
                {
                    bool flag = true;
                    foreach (ResultPolyline per_result_line in all_result_lines)
                    {
                        if (per_result_line.PolylineHashSet.Contains(per_input_line.FromPoint) | per_result_line.PolylineHashSet.Contains(per_input_line.ToPoint))
                        {
                            per_result_line.PolylineParts.Add(per_input_line);
                            per_result_line.PolylineHashSet.Add(per_input_line.FromPoint);
                            per_result_line.PolylineHashSet.Add(per_input_line.ToPoint);
                            flag = false;
                        }
                    }
                    if (flag)
                    {
                        ResultPolyline per_result_line = new ResultPolyline();
                        per_result_line.PolylineParts.Add(per_input_line);
                        per_result_line.PolylineHashSet.Add(per_input_line.FromPoint);
                        per_result_line.PolylineHashSet.Add(per_input_line.ToPoint);
                        all_result_lines.Add(per_result_line);
                    }
                }
            }
            return all_result_lines;
        }
    }

楼主你的实现有bug。比如，本来1-6是一条线的，但传进来的6条线段的顺序为:123564，然后你就会发现你的输出是1234和456两条线，而不是123456一条线

#28

引用 27 楼 u013170811 的回复:

楼主你的实现有bug。比如，本来1-6是一条线的，但传进来的6条线段的顺序为:123564，然后你就会发现你的输出是1234和456两条线，而不是123456一条线

嗯，这个代码没有实现它自己说的规则3（....任一端点，在多个连通组中可以找到，那么就合并多个连通组....）的逻辑。

实际上基于集合的算法总是那么诡异。我建议c#程序员学好“迭代器”技术，用简单清晰的“递归化作迭代”的代码来实现算法，而基本上不用去考虑“集合算法”（当然，如果你处理巨大的数据量的业务，可以借鉴这些算法几十年在数据结构——例如特定的索引树结构——上的研究成果）。

c#（以及.net平台）有一些很“时髦”的机制，可以让我们比其它编程平台（特别是几年前的）上的一些算法程序的应用扩展效率高得多的方式去写类似的程序。使用c# 或许不但语法比较优雅，而且方便于算法设计。

#29

该回复于2016-03-31 23:48:43被版主删除

#30

那我出一个吧

public class MyClass
{
	public IEnumerable<Segment[]> GroupLine(List<Segment> list)
	{
		var tt = list.Select(p => new Segment[] { p });
		int count = tt.Count();
		while (true)
		{
			//由于首位相连为一组，不一定按顺序进入HashTable，以循环方式将所有节点相同的线进行合并组
			tt = tt.GroupBy(p => p, new SegmentEquals()).Select(p => p.SelectMany(s => s).ToArray());
			int c = tt.Count();
			if (c == count)
			{
				break;
			}
			else
			{
				count = c;
			}
		}
		return tt;
	}
}

public class Segment
{
	public Point A { get; set; }
	public Point B { get; set; }
}

public class SegmentEquals : IEqualityComparer<Segment[]>
{
	public bool Equals(Segment[] Le, Segment[] Ri)
	{
		foreach (var r in Ri)
		{
			if (Le.Any(p => p.A.Equals(r.A) || p.A.Equals(r.B) || p.B.Equals(r.A) || p.B.Equals(r.B)))
			{
				return true;
			}
		}
		return false;
	}

	public int GetHashCode(Segment[] s)
	{
		return s.ToString().GetHashCode();
	}
}

#31

该回复于2015-12-31 23:42:24被版主删除

#32

呵呵，根据“分组”两个字眼儿，又去套统计聚类算法了。

其实每一个问题都要先审题。这个问题的数据结构可以看出，只需要“一趟扫描”就能得到所有的分组，而不需要对n个数据进行n^2数量级的扫描。所以千万不要乱套用统计聚类算法（至少在Path数据比较多的时候千万不要舍近求远去使用最累赘的算法）。

#33

该回复于2016-02-28 23:37:12被版主删除

#34

        public sealed class polyNode
        {
            public IPoint Point { get; internal set; }
            internal polyNode Left;
            public polyNode Right { get; private set; }
            internal void Append(polyNode other)
            {
                System.Diagnostics.Debug.Assert(Right == null && Left != other && Right != other);
                if (Left == null) Left = other;
                else Right = other;
            }
            internal polyNode CheckRight()
            {
                polyNode node = this, other = Left;
                while ((other = other.checkRight(ref node)) != null) ;
                return node;
            }
            private polyNode checkRight(ref polyNode node)
            {
                if (Right == node)
                {
                    Right = Left;
                    Left = node;
                }
                node = this;
                return Right;
            }
        }
        public static IEnumerable<polyNode> methods(List<IPolyline> input_polylines)
        {
            Dictionary<IPoint, polyNode> nodes = new Dictionary<IPoint, polyNode>();
            foreach (IPolyline per_input_line in input_polylines)
            {
                System.Diagnostics.Debug.Assert(!per_input_line.FromPoint.Equals(per_input_line.ToPoint));
                polyNode fromNode, toNode;
                if (!nodes.TryGetValue(per_input_line.FromPoint, out fromNode)) nodes.Add(per_input_line.FromPoint, fromNode = new polyNode { Point = per_input_line.FromPoint });
                if (!nodes.TryGetValue(per_input_line.ToPoint, out toNode)) nodes.Add(per_input_line.ToPoint, toNode = new polyNode { Point = per_input_line.ToPoint });
                fromNode.Append(toNode);
                toNode.Append(fromNode);
            }
            foreach (KeyValuePair<IPoint, polyNode> node in nodes.ToList())
            {
                if (nodes.ContainsKey(node.Key)) nodes.Remove(node.Value.Right == null ? node.Value.CheckRight().Point : node.Key);
            }
            return nodes.Values;
        }

#35

该回复于2016-01-31 23:20:08被版主删除

#36

那就再上一个，只用一次循环

public class MyClass
{
    public IEnumerable<Segment[]> GroupLine(List<Segment> list)
    {
        Dictionary<IEnumerable<Point>, IEnumerable<Segment>> dic = new Dictionary<IEnumerable<Point>, IEnumerable<Segment>>();
		foreach (var s in list)
		{
			var arr = dic.Where(p => p.Key.Any(t => t == s.A || t == s.B)).ToArray();
			switch (arr.Length)
			{
				case 2:
					dic.Add(arr.SelectMany(p => p.Key), arr.SelectMany(p => p.Value).Concat(new Segment[] { s }));
					dic.Remove(arr[0].Key);
					dic.Remove(arr[1].Key);
					break;
				case 1:
					dic.Add(arr[0].Key.Union(new Point[] { s.A, s.B }), arr[0].Value.Concat(new Segment[] { s }));
					dic.Remove(arr[0].Key);
					break;
				default:
					dic.Add(new Point[] { s.A, s.B }, new Segment[] { s });
					break;
			}
		}
		return dic.Values.Select(p => p.ToArray());
    }

	public struct Segment
	{
		public Point A { get; set; }
		public Point B { get; set; }
	}
}

#37

该回复于2015-08-17 09:18:33被管理员删除

#38

1. 使用 List<Tulple<List<Point>, List<Segment>>>,  在Add和枚举遍历方面的性能要好于 Dictionary<IEnumerable<Point>, IEnumerable<Segment>>。在 remove 旧的分组的时候可以直接从 List<> 中移除。

2. 对于每一个原始的路径，如果都到所有的分组中去遍历的话，这可能用不上索引。通常在原始的路径列表中会有索引，因此在处理了路径 a 之后再接触去找来与a相邻的路径进一步处理时，可以用上索引。而对于中间结果（分组的数据），通常没有索引，这时候到已经分组的数据中去遍历查找所有的路径，（当数据量比较大时）通常用不上索引。

3. ...where(....).ToArray()这也会有性能问题。显然顶多找到两个结果就够了，使用 Take(2) 足矣。

4. 每处理一个原始路径，都要把1或者2个分组毁掉，重建新的分组然后（按照如此复杂的key去）插入dic，这也是挺复杂的。

5. 最主要的，这是在“最后”才输出结果，而不能迭代方式提前输出、提前终止。比如说调用程序只是想找到路径最终在哪一个分组中，那么算法在找到这个分组之后，就终止了，并不需要找到其它的分组。

总之，面向集合的算法与基于迭代器的算法，有着不一样的“简化中间数据结构、计算性能、延迟启动、提前结束、最小化内存占用量、可读性”等特性。我是推荐各位在各种算法中搞懂和多用c#的迭代器，基本上避免所有面向集合的算法。

#39

比如说调用程序只是想找到路径最终在哪一个分组中 -->  比如说调用程序只是想找到路径7最终在哪一个分组中

#40

引用 38 楼 sp1234 的回复:

1. 使用 List<Tulple<List<Point>, List<Segment>>>,  在Add和枚举遍历方面的性能要好于 Dictionary<IEnumerable<Point>, IEnumerable<Segment>>。在 remove 旧的分组的时候可以直接从 List<> 中移除。

2. 对于每一个原始的路径，如果都到所有的分组中去遍历的话，这可能用不上索引。通常在原始的路径列表中会有索引，因此在处理了路径 a 之后再接触去找来与a相邻的路径进一步处理时，可以用上索引。而对于中间结果（分组的数据），通常没有索引，这时候到已经分组的数据中去遍历查找所有的路径，（当数据量比较大时）通常用不上索引。

3. ...where(....).ToArray()这也会有性能问题。显然顶多找到两个结果就够了，使用 Take(2) 足矣。

4. 每处理一个原始路径，都要把1或者2个分组毁掉，重建新的分组然后（按照如此复杂的key去）插入dic，这也是挺复杂的。

5. 最主要的，这是在“最后”才输出结果，而不能迭代方式提前输出、提前终止。比如说调用程序只是想找到路径最终在哪一个分组中，那么算法在找到这个分组之后，就终止了，并不需要找到其它的分组。

总之，面向集合的算法与基于迭代器的算法，有着不一样的“简化中间数据结构、计算性能、延迟启动、提前结束、最小化内存占用量、可读性”等特性。我是推荐各位在各种算法中搞懂和多用c#的迭代器，基本上避免所有面向集合的算法。

你绝对牛逼的，真乃是老虎不发威，发威浑身就是性能，我之前用Dictionary进行查询、新增、移除的方式，模拟了400组坐标list，计算时间在50至80毫秒之间，同样的坐标组用list加元组，计算时间在3到4毫秒，其实我的方法逻辑是一样的，我以前见过元祖，但没注意这东西，今天花了点时间看了看，真是个好东西，在组织数据上非常方便，这个口袋可以一直延伸下去。

public IEnumerable<Segment[]> GroupLine(List<Segment> list)
{
	List<Tuple<List<Point>, List<Segment>>> tlist = new List<Tuple<List<Point>, List<Segment>>>();
	Tuple<List<Point>, List<Segment>>[] t;
	foreach (var s in list)
	{
		t = tlist.Where(p => p.Item1.Any(x => x == s.A || x == s.B)).ToArray();
		switch (t.Length)
		{
			case 2:
				t[1].Item1.ForEach(p => t[0].Item1.Add(p));
				t[0].Item2.Add(s);
				tlist.Remove(t[1]);
				break;
			case 1:
				t[0].Item1.Add(t[0].Item1.Contains(s.A) ? s.B : s.A);
				t[0].Item2.Add(s);
				break;
			default:
				tlist.Add(new Tuple<List<Point>, List<Segment>>(new List<Point>() { s.A, s.B }, new List<Segment>() { s }));
				break;
		}
	}
	return tlist.Select(p=>p.Item2.ToArray());
}

public struct Segment
{
	public Point A;
	public Point B;
}

#41

tlist.Where(p => p.Item1.Any(x => x == s.A || x == s.B)).Take(2)  最多找到2个就足矣。

#42

当然，实际上也最多只能找到2个结果。但是电脑不知道啊，它会一直找第三个.....这就没有必要了。

#43

少了一点点，重新测试，400组坐标计算时间依然3到4毫秒，赶快睡觉。

public IEnumerable<Segment[]> GroupLine(List<Segment> list)
{
	List<Tuple<List<Point>, List<Segment>>> tlist = new List<Tuple<List<Point>, List<Segment>>>();
	Tuple<List<Point>, List<Segment>>[] t;
	foreach (var s in list)
	{
		t = tlist.Where(p => p.Item1.Any(x => x == s.A || x == s.B)).ToArray();
		switch (t.Length)
		{
			case 2:
				t[1].Item1.ForEach(p => t[0].Item1.Add(p));
				t[1].Item2.ForEach(p => t[0].Item2.Add(p));
				t[0].Item2.Add(s);
				tlist.Remove(t[1]);
				break;
			case 1:
				t[0].Item1.Add(t[0].Item1.Contains(s.A) ? s.B : s.A);
				t[0].Item2.Add(s);
				break;
			default:
				tlist.Add(new Tuple<List<Point>, List<Segment>>(new List<Point>() { s.A, s.B }, new List<Segment>() { s }));
				break;
		}
	}
	return tlist.Select(p=>p.Item2.ToArray());
}

public struct Segment
{
	public Point A;
	public Point B;
}

#44

引用 41 楼 sp1234 的回复:

tlist.Where(p => p.Item1.Any(x => x == s.A || x == s.B)).Take(2)  最多找到2个就足矣。

此言有理，发上来发现你回贴了，再次修改一下，400组坐标测试时间差不多，应该用更多的坐标组进行测试，今天不能弄下去了，谢谢大神！

public IEnumerable<Segment[]> GroupLine(List<Segment> list)
{
	List<Tuple<List<Point>, List<Segment>>> tlist = new List<Tuple<List<Point>, List<Segment>>>();
	Tuple<List<Point>, List<Segment>>[] t;
	foreach (var s in list)
	{
		t = tlist.Where(p => p.Item1.Any(x => x == s.A || x == s.B)).Take(2).ToArray();
		switch (t.Length)
		{
			case 2:
				t[1].Item1.ForEach(p => t[0].Item1.Add(p));
				t[1].Item2.ForEach(p => t[0].Item2.Add(p));
				t[0].Item2.Add(s);
				tlist.Remove(t[1]);
				break;
			case 1:
				t[0].Item1.Add(t[0].Item1.Contains(s.A) ? s.B : s.A);
				t[0].Item2.Add(s);
				break;
			default:
				tlist.Add(new Tuple<List<Point>, List<Segment>>(new List<Point>() { s.A, s.B }, new List<Segment>() { s }));
				break;
		}
	}
	return tlist.Select(p=>p.Item2.ToArray());
}

public struct Segment
{
	public Point A;
	public Point B;
}

#45

该回复于2015-08-17 09:28:30被管理员删除

#46

#47

#48

该回复于2016-01-31 23:20:08被版主删除

#49

如果存在多条线段交于一点 或 联通路线中有环
你打算怎么处理？

#50

该回复于2015-08-17 12:55:37被管理员删除