Реализовать программу поиска путей в графе - C#

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

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

нужно сделать граф 8 вершин И сделать одно из трех. 1. Поиск всех путей в неориентированном графе 2. Поиск кратчайшего пути в графе 3. Поиск путей в ориентированном графе. Пишите пожалуйста более простым языком ибо я новичок в С# Заранее благодарен

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

textual
Листинг программы
using System;
using System.Collections;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
 class Program
  {
   public static int i, j, k, kol;
   public struct uzel 
    {
     public int nom;
     public int ki;
     public int kj;
    };
   public static uzel n = new uzel();
   static void vkl(Stack vst, uzel n)
    {
     vst.Push(n);
    }
   static void iskl(Stack vst)
    {
     if (vst == null) Console.WriteLine("Стек пуст !");
      else  n = (uzel)vst.Pop();
    }
    public static void Main()
    {
     Stack vstek = new Stack();
     string buf;
     int beg, en, x, i1,i2;
     uzel y1 = new uzel();
     bool[] nov = new bool[10];
     int[,] p = new int[9, 9];
     int[] m = new int[10]; 
     //Матрица смежности графа 
     int[,] a = new int[9, 9]
      {{   0,   6,1000,   4,1000,1000,1000,1000,1000},
       {   6,   0,   5,1000,1000,1000,1000,   4,1000},
       {1000,   5,   0,   3,   4,1000,   5,   6,1000},
       {   4,1000,   3,   0,   7,1000,1000,1000,1000},
       {1000,1000,   4,   7,   0,   5,1000,1000,1000},
       {1000,1000,1000,1000,   5,   0,   4,1000,   9},
       {1000,1000,   5,1000,1000,   4,   0,1000,   6},
       {1000,   4,   6,1000,1000,1000,1000,   0,   8},
       {1000,1000,1000,1000,1000,   9,   6,   8,   0}};
   //Формирование списков смежных вершин по матрице а  
     for (i = 0; i < 9; i++)
      {
       p[i,0] = i;k=1;
       for (j = 0; j < 9; j++)
        if ((a[i, j] != 1000) && (a[i, j] != 0))
         {
          p[i,k]=j;
          k++;
         }
       p[i,k]=1000;  
      }
   //Печать списков смежных вершин         
     for (i = 0; i < 9; i++)
      {
       k = 0;
       while (p[i,k] != 1000)
        {
         Console.Write(" {0}", p[i,k]);
         k++;
        }
       Console.WriteLine();
      }
  Console.Write("Введите номер начального узла графа? ");
     buf = Console.ReadLine();
     beg = Convert.ToInt32(buf);
  Console.Write("Введите номер конечного узла графа? ");
     buf = Console.ReadLine();
     en = Convert.ToInt32(buf);
     //Начальные установки программы
     for (i = 0; i < 9; i++)
      {
       nov[i] = true;
       m[i] = 0;
      }
nov[9] = false;
x = 1;         //Номер очередного маршрута
m[1] = beg; i1 = 2;
y1.nom = beg; //Определяем поле nom узла y1
y1.ki = beg;  // Запоминаем номер списка смеж. вершин
y1.kj = 0;  // Запоминаем номер текущей позиции в списке
vkl(vstek, y1);
kol = 1;       //Количество элементов в стеке
nov[beg] = false;
nov[en] = false;
i = beg; j = 0;
//Цикл поиска всех маршрутов в графе
     while (kol != 0)
      {
       do
        {
         j++;
         if (p[i,j] == en)
          {
           Console.Write(" путь - {0} -", x); x++;
           for (i2 = 1; i2 < i1; i2++)
            Console.Write(" {0}", m[i2]);
           Console.WriteLine(" {0}", en);
          }
        }
       while ((p[i,j] != 1000) && (!nov[p[i,j]]));
       if (p[i,j] != 1000)
        if (nov[p[i,j]])
         {
          y1.ki = i;
          y1.kj = j;
          i = p[i,j];
          y1.nom = i;
          vkl(vstek, y1);
          j = 0;
          kol++;
          nov[i] = false;
          m[i1] = i;
          i1++;
         };
       
       if (p[i,j] == 1000)
        {
         kol--;
         if (kol != 0)
          {
           iskl(vstek);
           i = n.ki;
           j = n.kj;
           i1--;
           m[i1] = 0;
           nov[n.nom] = true;
          }
        };
      }
Console.WriteLine();
Console.WriteLine("Для продолжения нажмите клавишу Enter");
Console.ReadLine();
    }
  }
}

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


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

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

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