一个简单图搜索算法_.NET_编程开发_程序员俱乐部

[Serializable]  
    public class VPoint
    {
        public int ID { get; set; }
        public int X { get; set; }
        public int Y { get; set; }
        public bool IsFind { get; set; }
        public List<int> Dependences { get; set; }//与该点关联的点ID

    }

private void FindPath()
        {
            VPoint v1 = new VPoint() { ID = 0, X = 0, Y = 20, Dependences = new List<int>() {2, 1 } };
            VPoint v2 = new VPoint() { ID = 1, X = 20, Y = 0, Dependences = new List<int>() { 0, 3, 2 } };
            VPoint v3 = new VPoint() { ID = 2, X = 20, Y = 20, Dependences = new List<int>() { 0, 1, 4 } };
            VPoint v4 = new VPoint() { ID = 3, X = 40, Y = 0, Dependences = new List<int>() { 1, 4, 5 } };
            VPoint v5 = new VPoint() { ID = 4, X = 40, Y = 20, Dependences = new List<int>() { 2, 3, 5 } };
            VPoint v6 = new VPoint() { ID = 5, X = 60, Y = 20, Dependences = new List<int>() { 3, 4 } };
            List<VPoint> points = new List<VPoint>() { v1, v2, v3, v4, v5, v6 };
            VPoint start = v1;
            VPoint end = v6;
            List<VPoint> resultpoint = new List<VPoint>();
            FindPoint(Clone(points), start, end, resultpoint);
            foreach (var item in Paths)
            {
                string path = "";
                foreach (var point in item)
                {
                    path += point.ID +"=>";
                }
                Console.WriteLine(path);//打印路径
            }
            Console.WriteLine(count);
        }
        int count = 0;
        List<IList<VPoint>> Paths = new List<IList<VPoint>>();//全局变量，保存所有的路径
        private void FindPoint(List<VPoint> points, VPoint start, VPoint end, List<VPoint> resultpoint)
        {
            resultpoint.Add(start);
            int index = points.IndexOf(points.Where(p => p.ID == start.ID).ToList()[0]);
            points[index].IsFind = true; //标记已经查找过
            if (start.Dependences.Contains(end.ID))//如果是终点
            {
                resultpoint.Add(end);
                Paths.Add(resultpoint);
                int _index = points.IndexOf(points.Where(p => p.ID == end.ID).ToList()[0]);
                points[_index].IsFind = true;
            }
            else
            {
                foreach (var item in start.Dependences)
                {
                    var newstart = points.Where(p => p.ID == item && p.IsFind == false).ToList();
                    if (newstart.Count > 0)
                    {
                        count++;
                        List<VPoint> newpoints = Clone(resultpoint);
                        FindPoint(Clone(points), newstart[0], end, newpoints);
                    }
                }
            }
        }
        public static T Clone<T>(T RealObject)//深度拷贝
        {
            using (Stream objectStream = new MemoryStream())
            {
                IFormatter formatter = new BinaryFormatter();
                formatter.Serialize(objectStream, RealObject);
                objectStream.Seek(0, SeekOrigin.Begin);
                return (T)formatter.Deserialize(objectStream);
            }
        }