Поиск вершины в графе по алгоритму Флойда - C#

Узнай цену своей работы

Формулировка задачи:

Добрый час суток! Есть такая задача : Написать программу в которой будет выполняться алгоритм Флойда; Поиск вершины в графе;
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);

        }
    }
}
С Флойдом вроде бы всё ок. А вот поиск вершины в графе как организовать? как я понял,с помощью поиска в глубину,у нас будут нумероваться вершины,по мере их прохождения. посмотрел в интернете,кучу примеров,но еще больше запутался,с тем же DFS- посмотрел и рекурсивный и не рекурсивный,вроде алгоритм понял,а вот как организовать сам поиск вершины,не пойму. граф матрицей смежности задан. Подскажите пожалуйста,как по простому организовать?

Решение задачи: «Поиск вершины в графе по алгоритму Флойда»

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;
        }   
    }

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

13   голосов , оценка 4.231 из 5
Похожие ответы