C#_Eilerov

public class Graph
    {

        public class Queue
        {
            private class Node //вложенный класс, реализующий базовый элемент очереди
            {
                private object inf;
                private Node next;
                public Node(object nodeInfo)
                {
                    inf = nodeInfo;
                    next = null;
                }
                public Node Next
                {
                    get { return next; }
                    set { next = value; }
                }
                public object Inf
                {
                    get { return inf; }
                    set { inf = value; }
                }
            } //конец класса Node
            private Node head;
            private Node tail;
            public Queue()
            {
                head = null;
                tail = null;
            }
            public void Add(object nodeInfo)
            {
                Node r = new Node(nodeInfo);
                if (head == null)
                {
                    head = r;
                    tail = r;
                }
                else
                {
                    tail.Next = r;
                    tail = r;
                }
            }
            public object Take()
            {
                if (head == null)
                {
                    throw new Exception("Очередь пуста.");
                }
                else
                {
                    Node r = head;
                    head = head.Next;

                    if (head == null)
                    {
                        tail = null;
                    }
                    return r.Inf;
                }
            }
            public bool IsEmpty
            {
                get
                {
                    if (head == null)
                    {
                        return true;
                    }
                    else
                    {
                        return false;
                    }
                }
            }
        }




        private class Node //вложенный класс для скрытия данных и алгоритмов
        {
            private int[,] array; //матрица смежности
            public int 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 bool NovGet(int i) //метод помечает все вершины графа как непросмотреные
            {

                return nov[i];

            }
            //конструктор вложенного класса, инициализирует матрицу смежности и
            // вспомогательный массив
            public Node(int[,] a)
            {
                array = a;
                nov = new bool[a.GetLength(0)];
            }
            //реализация алгоритма обхода графа в глубину

            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 long[,] Floyd(out int[,] p)
            {
                int i, j, k;
                //создаем массивы р и а
                long[,] a = new long[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++)
                        {
                            long 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);
                }
            }
            public void Reach(int v)
            {
                nov[v] = false;
                for (int u = 0; u < Size; u++)
                {
                    if
                    (array[v, u] != 0 && nov[u])
                    {
                        Reach(u);
                    }
                }
            }

            public void SearchG(int v, ref int[,] a, ref Stack c) //во вложенном классе
            {
                for (int i = 0; i < a.GetLength(0); i++)
                {
                    if (a[v, i] != 0)
                    {
                        a[v, i] = 0; a[i, v] = 0;
                        SearchG(i, ref a, ref c);
                    }
                }
                c.Push(v);
            }


        } //конец вложенного клаcса



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

        //метод выводит матрицу смежности на консольное окно
        public void Show()
        {
            for (int i = 0; i < graph.Size; i++)
            {
                for (int j = 0; j < graph.Size; j++)
                {
                    Console.Write("{0,4}", graph[i, j]);
                }
                Console.WriteLine();
            }
        }
        public void Dfs(int v)
        {
            graph.NovSet();//помечаем все вершины графа как непросмотренные
            graph.Dfs(v); //запускаем алгоритм обхода графа в глубину
            Console.WriteLine();
        }
        public void Floyd()
        {
            int[,] p;
            long[,] 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 Reachable(int v)
        {
            graph.NovSet();
            Console.Write("Вершины достижимые из {0} вершины: ", v);
            graph.Reach(v);
            for (int i = 0; i < graph.Size; i++)
            {
                if (!graph.NovGet(i) && i != v) //если вершина была просмотрена, то она достижима
                {
                    Console.Write("{0} ", i);
                }
            }
            Console.WriteLine();
        }

        public void SearchG() //во внешнем классе
        {
            int[,] a = new int[graph.Size, graph.Size];
            for (int i = 0; i < graph.Size; i++)
            {
                for (int j = 0; j < graph.Size; j++)
                {
                    a[i, j] = graph[i, j];
                }
            }
            Stack c = new Stack();
            graph.SearchG(0, ref a, ref c);
            while (c.Count != 0)
            {
                Console.Write("{0} ", (int)c.Pop() + 1);
            }
        }

    }