Поиск вершины в графе по алгоритму Флойда - C#
Формулировка задачи:
Добрый час суток! Есть такая задача : Написать программу в которой будет выполняться алгоритм Флойда; Поиск вершины в графе;
С Флойдом вроде бы всё ок.
А вот поиск вершины в графе как организовать? как я понял,с помощью поиска в глубину,у нас будут нумероваться вершины,по мере их прохождения. посмотрел в интернете,кучу примеров,но еще больше запутался,с тем же DFS- посмотрел и рекурсивный и не рекурсивный,вроде алгоритм понял,а вот как организовать сам поиск вершины,не пойму. граф матрицей смежности задан. Подскажите пожалуйста,как по простому организовать?
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace task { class Program { static void Floid(int[,] array) { int k, i, j; Console.WriteLine("Алгоритм Флойда"); for (k = 0; k < 6; k++) { for (i = 0; i < 6; i++) { for (j = 0; j < 6; j++) { if (array[i, k] + array[k, j] < array[i, j]) { array[i, j] = array[i, k] + array[k, j]; } } } } } //Алгоритм флойда static void Output(int[,] array) { for (int i = 0; i < 6; i++) { for (int j = 0; j < 6; j++) { Console.Write(" {0,1} ", array[i, j]); } Console.WriteLine(""); } } static void Main(string[] args) { int[,] array = new int[6, 6]//двовимірній масив //матриця суміжності для алгоритму Флойда {{0,3,10000,3,6,10000}, {10000,0,4,7,1000,4}, {3,8,0,5,10000,2}, {10000,6,10000,0,3,10000}, {7,10000,1,4,0,4}, {5,2,10000,10000,2,0}}; Console.WriteLine("Матрица смежности"); Output(array); Floid(array); Console.WriteLine("После"); Output(array); } } }
Решение задачи: «Поиск вершины в графе по алгоритму Флойда»
textual
Листинг программы
private static bool DFS(int[,] a, int n, int k, int r) { //Запрминаем старовую вершину if (_visited.Contains(j) || a[k, j] == 0) // КОРРЕТИРОВКА - добавлено || a[k, j] == 0 { _visited.Push(k); } //Перебор ребер for (var j = 1; j < n; j++) { //Если вершину уже посещали [B] if (_visited.Contains(j) || a[k, j] == 0[/B]) { continue; } //Записываем в стек вершину _visited.Push(j); //Если вершина найдена, то стоп if (j == r) { return true; } else { //Помечаем вершину, как пройденную return DFS(a, n, j, r); // КОРРЕТИРОВКА - убран if } } return false; } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д