графы 3

// класс городов

using System;

namespace Myloyorrrr
{
    internal class GorodaOnline
    {
        public string Name { get; set; }
        public int X { get; set; }
        public int Y { get; set; }

        public GorodaOnline(string name, int x, int y)
        {
            Name = name;
            X = x;
            Y = y;
        }
        public double Distance(GorodaOnline a)
        {
            return Math.Sqrt((this.X - a.X) * (this.X - a.X) + (this.Y - a.Y) * (this.Y - a.Y));
        }

        public override string ToString()
        {
            return Name + " " + X + " " + Y;
        }

    }
}

// класс графов

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;

namespace Myloyorrrr
{
    public class Graph
    {
        private class Node //вложенный класс для скрытия данных и алгоритмов
        {
            private double[,] array; //матрица смежности
            public double this[int i, int j] //индексатор для обращения к матрице смежности
            {
                get
                {
                    return array[i, j];
                }
                set
                {
                    array[i, j] = value;
                }
            }
            public int Size //свойство для получения размерности матрицы смежности
            {
                get
                {
                    return array.GetLength(0);
                }
            }
            private bool[] nov; //вспомогательный массив: если i-ый элемент массива равен
                                //true, то i-ая вершина еще не просмотрена; если i-ый
                                //элемент равен false, то i-ая вершина просмотрена
            public void NovSet() //метод помечает все вершины графа как непросмотреные
            {
                for (int i = 0; i < Size; i++)
                {
                    nov[i] = true;
                }
            }
            //конструктор вложенного класса, инициализирует матрицу смежности и
            // вспомогательный массив
            public Node(double[,] a)
            {
                array = a;
                nov = new bool[a.GetLength(0)];

            }

            public void Add(int a, int b)
            {
                if (a >= 0 && a < Size && b >= 0 && b < Size)
                {
                    //array[a - 1, b - 1] = 1; // Для орграфа
                    array[b - 1, a - 1] = 1; // Для неорграфа
                }
                else
                {
                    Console.WriteLine("Некорректные вершины");
                }
            }

            //реализация алгоритма обхода графа в глубину
            public void Dfs(int v)
            {
                Console.Write("{0} ", v); //просматриваем текущую вершину
                nov[v] = false; //помечаем ее как просмотренную
                                // в матрице смежности просматриваем строку с номером v
                for (int u = 0; u < Size; u++)
                {
                    //если вершины v и u смежные, к тому же вершина u не просмотрена,
                    if (array[v, u] != 0 && nov[u])
                    {
                        Dfs(u); // то рекурсивно просматриваем вершину
                    }
                }
            }
            //реализация алгоритма обхода графа в ширину
            public void Bfs(int v)
            {
                Queue q = new Queue(); // инициализируем очередь
                q.Add(v); //помещаем вершину v в очередь
                nov[v] = false; // помечаем вершину v как просмотренную
                while (!q.IsEmpty) // пока очередь не пуста
                {
                    v = (int)q.Take(); //извлекаем вершину из очереди
                    Console.Write("{0} ", v); //просматриваем ее
                    for (int u = 0; u < Size; u++) //находим все вершины
                    {
                        if (array[v, u] != 0 && nov[u]) // смежные с данной и еще не просмотренные
                        {
                            q.Add(u); //помещаем их в очередь
                            nov[u] = false; //и помечаем как просмотренные
                        }
                    }
                }
            }
            //реализация алгоритма Дейкстры
            public double[] Dijkstr(int v, int nz, out int[] p)
            {
                //создаем матрицы d и p
                double[] d = new double[Size]; // массив расстояний
                p = new int[Size]; // массив предыдущих вершин путей

                for (int u = 0; u < Size; u++)
                {
                    d[u] = int.MaxValue;
                    p[u] = -1;
                }
                d[v] = 0;
                nov[nz] = false; //не ходим в город ненужный

                for (int i = 0; i < Size-1; i++)
                {
                    // выбираем из множества V\S такую вершину w, что D[w] минимально
                    double min = int.MaxValue;
                    int w = 0;
                    for (int u = 0; u < Size; u++)
                    {
                        if (nov[u] && min > d[u])
                        {
                            min = d[u];
                            w = u;
                        }
                    }

                    nov[w] = false; //помещаем w в множество S
                                    //для каждой вершины из множества V\S определяем кратчайший путь от
                                    // источника до этой вершины
                    for (int u = 0; u < Size; u++)
                    {
                        double distance = d[w] + array[w, u];
                        if (nov[u] && d[u] > distance && array[w, u] != 0)
                        {
                            d[u] = distance;
                            p[u] = w;
                        }
                    }
                }
                return d; //в качестве результата возвращаем массив кратчайших путей для
            }
            //заданного источника
            //восстановление пути от вершины a до вершины b для алгоритма Дейкстры
            //public void WayDijkstr(int a, int b, double[] p, ref Stack items)
            //{
            //    items.Push(b); //помещаем вершину b в стек
            //    if (a == p[b]) //если предыдущей для вершины b является вершина а, то
            //    {
            //        items.Push(a); //помещаем а в стек и завершаем восстановление пути
            //    }
            //    else //иначе метод рекурсивно вызывает сам себя для поиска пути
            //    { //от вершины а до вершины, предшествующей вершине b
            //        WayDijkstr(a, p[b], p, ref items);
            //    }
            //}

            //реализация алгоритма Флойда
            public double[,] Floyd(out int[,] p)
            {
                int i, j, k;
                //создаем массивы р и а
                double[,] a = new double[Size, Size];
                p = new int[Size, Size];
                for (i = 0; i < Size; i++)
                {
                    for (j = 0; j < Size; j++)
                    {
                        if (i == j)
                        {
                            a[i, j] = 0;
                        }
                        else
                        {
                            if (array[i, j] == 0)
                            {
                                a[i, j] = int.MaxValue;
                            }
                            else
                            {
                                a[i, j] = array[i, j];
                            }
                        }
                        p[i, j] = -1;
                    }
                }
                //осуществляем поиск кратчайших путей
                for (k = 0; k < Size; k++)
                {
                    for (i = 0; i < Size; i++)
                    {
                        for (j = 0; j < Size; j++)
                        {
                            double distance = a[i, k] + a[k, j];
                            if (a[i, j] > distance)
                            {
                                a[i, j] = distance;
                                p[i, j] = k;
                            }
                        }
                    }
                }
                return a;//в качестве результата возвращаем массив кратчайших путей между
            }

            //восстановление пути от вершины a до вершины в для алгоритма Флойда
            public void WayFloyd(int a, int b, int[,] p, ref Queue items)
            {
                int k = p[a, b];
                //если k<> -1, то путь состоит более чем из двух вершин а и b, и проходит через
                //вершину k, поэтому
                if (k != -1)
                {
                    // рекурсивно восстанавливаем путь между вершинами а и k
                    WayFloyd(a, k, p, ref items);
                    items.Add(k); //помещаем вершину к в очередь
                                  // рекурсивно восстанавливаем путь между вершинами k и b
                    WayFloyd(k, b, p, ref items);
                }
            }
        }

        //конец вложенного клаcса
        private Node graph; //закрытое поле, реализующее АТД «граф»
        private List<GorodaOnline> l;
        public Graph(string name) //конструктор внешнего класса
        {
            using (StreamReader file = new StreamReader(name))
            {
                int n = int.Parse(file.ReadLine());
                l = new List<GorodaOnline>();
                for (int i = 0; i<n; i++)
                {
                    string line = file.ReadLine();
                    string[] mas = line.Split(' ');
                    l.Add(new GorodaOnline(mas[0], int.Parse(mas[1]), int.Parse(mas[2])));
                }

                double[,] a = new double[n, n];
                for (int i = 0; i < n; i++)
                {
                    string line = file.ReadLine();
                    string[] mas = line.Split(' ');
                    for (int j = 0; j < n; j++)
                    {
                        int b = int.Parse(mas[j]);
                        a[i, j] = l[i].Distance(l[j]) * b;
                    }
                }
                graph = new Node(a);
            }
        }
        //метод выводит матрицу смежности на консольное окно
        public void Show()
        {
            foreach(GorodaOnline gorod in l)
            {
                Console.WriteLine(gorod);
            }
            for (int i = 0; i < graph.Size; i++)
            {
                for (int j = 0; j < graph.Size; j++)
                {
                    if (graph[i, j] == 0)
                    {
                        Console.Write("{0}\t", graph[i, j]);
                    }
                    else
                    {
                        Console.Write("{0:f2}\t", graph[i, j]);
                    }
                }
                Console.WriteLine();
            }
        }
        public void Add(int a, int b)
        {
            graph.Add(a, b);
        }
        public void Dfs(int v)
        {
            graph.NovSet();//помечаем все вершины графа как непросмотренные
            graph.Dfs(v); //запускаем алгоритм обхода графа в глубину
            Console.WriteLine();
        }
        public void Bfs(int v)
        {
            graph.NovSet();//помечаем все вершины графа как непросмотренные
            graph.Bfs(v); //запускаем алгоритм обхода графа в ширину
            Console.WriteLine();
        }
        public void Dijkstr(int v, int nz)
        {
            graph.NovSet();//помечаем все вершины графа как непросмотренные
            int[] p;
            double[] d = graph.Dijkstr(v, nz, out p); //запускаем алгоритм Дейкстры
                                                //анализируем полученные данные и выводим их на экран
            Console.WriteLine("Длина кратчайшие пути от вершины {0} до вершины", v);

            for (int i = 0; i < graph.Size; i++)
            {
                if (i != v)
                {
                    Console.Write("{0} равна {1}, ", i, d[i]);
                    Console.Write("путь ");
                    if (d[i] != int.MaxValue)
                    {
                        Stack items = new Stack();
                        //graph.WayDijkstr(v, i, p, ref items);
                        while (items.Peek()!= null)
                        {
                            Console.Write("{0} ", items.Pop());
                        }
                    }

                }
                Console.WriteLine();
            }
        }
        public void Myloyo_find(int a, int b, int nz)
        {
            graph.NovSet();//помечаем все вершины графа как непросмотренные
            int[] p;
            double[] d = graph.Dijkstr(a, nz, out p); //запускаем алгоритм Дейкстры
                                                      //анализируем полученные данные и выводим их на экран
            if (d[b]!= int.MaxValue)
            {
                Console.WriteLine("Длина кратчайшего пути из города {0} в город {1} без города {2} равен {3}", l[a].Name, l[b].Name, l[nz].Name, d[b]);
                Console.WriteLine();
                List<int>path = new List<int>();
                int cur = b;
                while (cur != -1)
                {
                    path.Add(cur);
                    cur = p[cur];
                }

                path.Reverse();
                Console.WriteLine($"Путь из города {l[a].Name} в город {l[b].Name} без города {l[nz].Name}:");
                foreach(int i in path){
                    Console.Write(l[i].Name + ", ");
                }
                Console.WriteLine();
            }
            else
            {
                Console.WriteLine($"Пути из {l[a].Name} в {l[b].Name} нет. (точка точка точка)");
            }
        }
        public void Floyd()
        {
            int[,] p;
            double[,] a = graph.Floyd(out p); //запускаем алгоритм Флойда
            int i, j;
            //анализируем полученные данные и выводим их на экран
            for (i = 0; i < graph.Size; i++)
            {
                for (j = 0; j < graph.Size; j++)
                {
                    if (i != j)
                    {
                        if (a[i, j] == int.MaxValue)
                        {
                            Console.WriteLine("Пути из города {0} в город {1} не существует", i, j);
                        }
                        else
                        {
                            Console.Write("Кратчайший путь из города {0} до города {1} равен {2}, ", i, j, a[i,j]);
                            Console.Write(" путь ");
                            Queue items = new Queue();
                            items.Add(i);
                            graph.WayFloyd(i, j, p, ref items);
                            items.Add(j);
                            while (!items.IsEmpty)
                            {
                                Console.Write("{0} ", items.Take());
                            }
                            Console.WriteLine();
                        }
                    }
                }
            }
        }
        public void Adjacent(int v) // 1 задача
        {
            Console.Write("Количество вершин смежных с {0} вершиной: ", v);
            int counter = 0;
            //просматриваем строку с номером v в матрице смежности
            for (int i = 0; i < graph.Size; i++)
            {
                if (graph[v-1, i] != 0)
                {
                    counter++;
                }
            }
            Console.WriteLine(counter);
        }
        public void Floyd_new(int L)
        {
            int[,] p;
            double[,] a = graph.Floyd(out p); //запускаем алгоритм Флойда
            for(int x = 0; x < a.GetLength(0); x++)
            {
                for(int y = 0; y < a.GetLength(1); y++)
                {
                    Console.Write(a[x, y] + " ");

                }
                Console.WriteLine();
            }

            int i, j;
            //анализируем полученные данные и выводим их на экран
            for (i = 0; i < graph.Size; i++)
            {
                for (j = 0; j < graph.Size; j++)
                {
                    if (i != j)
                    {
                        if (a[i, j] == int.MaxValue)
                        {
                            Console.WriteLine("Пути из вершины {0} в вершину {1} не существует", i, j);
                        }
                        else
                        {
                            if (a[i, j] <= L)
                            {
                                Console.WriteLine("Пара вершин: {0} и {1}. Кратчайший путь равен {2}.", i, j, a[i, j]);
                            }
                            Queue items = new Queue();
                            items.Add(i);
                            graph.WayFloyd(i, j, p, ref items);
                            items.Add(j);
                        }
                    }
                }
            }
        }
    }
}

// основная прога

using System;

namespace Myloyorrrr
{
    internal class Program
    {
        static void Main()
        {

            Graph G = new Graph("C:/Настя/книит/in.txt");
            G.Show();
            Console.WriteLine();
            Console.WriteLine("Введите первую вершину:");
            int a = int.Parse(Console.ReadLine());
            Console.WriteLine("Введите вторую вершину:");
            int b = int.Parse(Console.ReadLine());
            Console.WriteLine("Введите вершину, через которую нельзя пройти:");
            int d = int.Parse(Console.ReadLine());
            Console.WriteLine();
            G.Myloyo_find(a-1, b-1, d-1);


            //// 1 задача: подсчитать смежные вершины с данной вершиной
            //Console.Write("Введите номер вершины: ");
            //int v = int.Parse(Console.ReadLine());
            //G.Adjacent(v);

            //// 2 задача: определить все пары вершин, для которых существует путь длиной не более L
            //Console.Write("Введите требуемую длину пути: ");
            //int L = int.Parse(Console.ReadLine());
            //G.Floyd_new(L);

            //BinaryTree lipa = new BinaryTree();
            //int n = 0;

            ////Чтение последовательности чисел из файла input.txt и добавление их в дерево
            //using (StreamReader f = new StreamReader("C:/Настя/книит/in.txt"))
            //{
            //    string line;
            //    while ((line = f.ReadLine()) != null)
            //    {
            //        string[] text = line.Split(' ');
            //        for (int i = 0; i < text.Length; i++)
            //        {
            //            int num = int.Parse(text[i]);
            //            lipa.Add(num);
            //            n++;
            //        }
            //    }

            //}

            //lipa.Preorder();

            ////3 деревья
            //bool IsBalance = lipa.Balance();
            //if (IsBalance)
            //{
            //    Console.WriteLine("Дерево является сбалансированным");
            //}
            //else
            //{
            //    Console.WriteLine("Дерево не является сбалансированным");
            //}
        }
    }
}