graph.cs

public class Graph
    {
        public class Connection
        {
            public Node n1;
            public Node n2;

            public int Distance { get; set; }

            public Connection(Node n1, Node n2)
            {
                this.n1 = n1;
                this.n2 = n2;
            }
        }

        public class Node
        {
            public int F { get; set; }
            public string Name { get; set; }

            public bool IsSource { get; set; }

            public Node Parent { get; set; }

            public Node(bool isSource)
            {
                IsSource = isSource;
            }
        }

        private List<Node> Nodes;
        private List<Connection> Connections;

        public Graph()
        {
            Nodes = new List<Node>();
            Connections = new List<Connection>();
        }

        public void AddNode(Node node)
        {
            Nodes.Add(node);
        }

        public void AddConnection(Connection conn)
        {
            Connections.Add(conn);
        }

        public bool WidthSearch(Node start, Node finish)
        {
            List<Node> testQueue = new List<Node>();
            List<Node> looked = new List<Node>();
            testQueue.Add(start);

            while (testQueue.Count > 0)
            {
                var node = testQueue[0];

                if (node == finish)
                {
                    return true;
                }

                for (int i = 0; i < Connections.Count; i++)
                {
                    if (Connections[i].n1 == node)
                    {
                        if (!looked.Contains(Connections[i].n2))
                        {
                            testQueue.Add(Connections[i].n2);
                        }
                    }

                    if (Connections[i].n2 == node)
                    {
                        if (!looked.Contains(Connections[i].n1))
                        {
                            testQueue.Add(Connections[i].n1);
                        }
                    }
                }

                testQueue.RemoveAt(0);
                looked.Add(node);
            }

            return false;
        }

        List<Connection> GetFor(Node n)
        {
            List<Connection> connections = new List<Connection>();
            for (int i = 0; i < Connections.Count; i++)
            {
                if (Connections[i].n1 == n)
                {
                    connections.Add(Connections[i]);
                }
                else if (Connections[i].n2 == n)
                {
                    var conn = new Connection(Connections[i].n2, Connections[i].n1);
                    conn.Distance = Connections[i].Distance;
                    connections.Add(conn);
                }
            }

            return connections;
        }

        public int AStar(Node start, Node goal)
        {
            List<Node> u = new List<Node>();
            List<Node> q = new List<Node>();
            q.Add(start);
            start.F = 0;
            while (q.Count > 0)
            {
                Node current = q.OrderByDescending(n => n.F).First();
                if (current == goal)
                {
                    return goal.F;
                }

                q.Remove(current);
                u.Add(current);

                foreach (var v in GetFor(current))
                {
                    int tentativeScore = current.F + v.Distance;
                    if (u.Contains(v.n2) && tentativeScore >= v.n2.F)
                    {
                        continue;
                    }

                    if (!u.Contains(v.n2) || tentativeScore < v.n2.F)
                    {
                        v.n2.Parent = current;
                        v.n2.F = tentativeScore;
                        if (!q.Contains(v.n2))
                        {
                            q.Add(v.n2);
                        }
                    }
                }
            }

            return -1;
        }

        public static void Tttt()
        {
            // создание узлов
            var graph = new Graph();
            graph.Nodes.Add(new Node(true));
            graph.Nodes.Last().Name = "1";
            graph.Nodes.Add(new Node(false));
            graph.Nodes.Last().Name = "2";
            graph.Nodes.Add(new Node(false));
            graph.Nodes.Last().Name = "3";

            // создание соединений
            graph.Connections.Add(new Connection(graph.Nodes[0], graph.Nodes[1]));
            graph.Connections.Last().Distance = 10;
            graph.Connections.Add(new Connection(graph.Nodes[0], graph.Nodes[2]));
            graph.Connections.Last().Distance = 20;

            // Разделение на фабрики и производители

            List<Node> processors = graph.Nodes.Where(n => !n.IsSource).ToList();
            List<Node> sources = graph.Nodes.Where(n => n.IsSource).ToList();

            // список расстояний от каждой фабрики до ближайшего источника
            List<int> distances = new List<int>();

            // для каждой фабрики ищем ближайший источник
            foreach (var processor in processors)
            {
                int shortestDist = int.MaxValue;
                foreach (var source in sources)
                {
                    // вызываем поиск в графе A*
                    // https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_A*
                    int currentDistance = graph.AStar(processor, source);
                    if (currentDistance < shortestDist)
                    {
                        shortestDist = currentDistance;
                    }
                }

                distances.Add(shortestDist);
            }

            int k = 1; // количество элементов к удалению
            for (int i = 0; i < k; i++)
            {
                var minimum_index = distances.IndexOf(distances.Max()); // находим индекс минимума
                Console.WriteLine("We delete '{0}' node, with distance {1} to closest source", processors[minimum_index].Name,
                    distances[minimum_index]);

                processors.RemoveAt(minimum_index);
                distances.RemoveAt(minimum_index);
            }

            // выводим все оставшиеся фабрики
            foreach (var processor in processors)
            {
                // Вывод оставшихся
                Console.WriteLine("'{0}' processor left", processor.Name);
            }
        }
    }