Добавить в граф ребро, соединяющее вершину а и b для взвешенного графа - C#
Формулировка задачи:
В входном файле указывается количество вершин графа/орграфа и матрица смежности.
Решение задачи: «Добавить в граф ребро, соединяющее вершину а и b для взвешенного графа»
textual
Листинг программы
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 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); } } } //конец вложенного кла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(); } } } } } static void Main() { Graph g = new Graph("input.txt"); Console.WriteLine("Graph:"); g.Show(); } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д