Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections;
- using System.IO;
- 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 fileIn = new StreamReader("../../input.txt"))
- {
- int n = int.Parse(fileIn.ReadLine());
- int[,] a = new int[n, n];
- for (int i = 0; i < n; i++)
- {
- string line = fileIn.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);
- }
- }
- class Program
- {
- static void Main(string[] args)
- {
- Graph graph = new Graph("input.txt");
- graph.SearchG();
- Console.ReadKey();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement