Laboratoriya mashg’uloti №7 Graflar bilan ishlovchi sodda algoritmlar. Graflarni tasvirlash. Eniga va tubiga qarab qidirish

Akmal Muzafarov

TUIT




Laboratoriya ishi – 7-8

Algaritmlarni loyihalash


Laboratoriya mashg’uloti №7-8. Graflar bilan ishlovchi sodda algoritmlar.Graflarni tasvirlash. Eniga va tubiga qarab qidirish

Ishdan maqsad: Talabalarda graflar bilan ishlash algoritmlari haqida ko’nikmalar hosil qilish va ular bilan ishlashni o’rganish.

Nazariy qism:

Deykstra algoritmi

Eng qisqa masofani aniqlash misolini ko’rib chiqaylik. Shahar viloyatlarini birlashtiruvchi avtomobil yo’llari tarmog’I berilgan bo’lsin. Ba’zi yo’llar bir tomonlama. Shahar markazidan har bir viloyatga eng qisqa yo’lni topishimiz zarur.

Deykstraning Algoritmi graflarga asoslangan bo’lib, u 1959 yil niderlandiyalik olim E. Deykstra tomonidan yaratilgan. U grafning bitta uchidan boshqa uchlarigacha eng qisqa masofani aniqlaydi, bunda grafning quvurg’alari manfiy og’irlikka ega bo’lmasligi lozim.

Deykstra algoritmining tadbiqi

Grafning og’irligini saqlash uchun kvadrat matritsadan foydalaniladi. Satrlar va ustunlar sarlavhalarida grafning uchlari joylashadi. Graf yoylarining og’irligi jadvalning ichki yacheykalariga joylashtiriladi.

Misol:

  class DekstraAlgorim

  {

    public Point[] points { get; private set; }

    public Rebro[] rebra { get; private set; }
    public Point BeginPoint { get; private set; }

    public DekstraAlgorim(Point[] pointsOfgrath, Rebro[] rebraOfgrath)

    {
      points = pointsOfgrath;
      rebra = rebraOfgrath;
    }
    public void AlgoritmRun(Point beginp)
    {
      if (this.points.Count() == 0 || this.rebra.Count() == 0)
      {
        throw new DekstraException("Массив вершин или ребер не задан!");
      }
      else
      {
        BeginPoint = beginp;
        OneStep(beginp);
        foreach (Point point in points)
        {
          Point anotherP = GetAnotherUncheckedPoint();
          if (anotherP != null)
          {
            OneStep(anotherP);
          }
          else
          {
            break;
          }

        }

      }

    }
    public void OneStep(Point beginpoint)

    {
      foreach(Point nextp in Pred(beginpoint))
      {
        if (nextp.IsChecked == false)//не отмечена
        {
          float newmetka = beginpoint.ValueMetka + GetMyRebro(nextp, beginpoint).Weight;
          if (nextp.ValueMetka > newmetka)
          {
            nextp.ValueMetka = newmetka;
            nextp.predPoint = beginpoint;
          }
          else
          {

          }

        }
      }
      beginpoint.IsChecked = true;//вычеркиваем
    }
    private IEnumerable
Pred(Point currpoint)
    {
      IEnumerable
firstpoints = from ff in rebra where ff.FirstPoint==currpoint select ff.SecondPoint;
      IEnumerable
secondpoints = from sp in rebra where sp.SecondPoint == currpoint select sp.FirstPoint;
      IEnumerable
totalpoints = firstpoints.Concat
(secondpoints);
      return totalpoints;
    }
    private Rebro GetMyRebro(Point a, Point b)
    {//ищем ребро по 2 точкам
      IEnumerable myr = from reb in rebra where (reb.FirstPoint == a & reb.SecondPoint == b) || (reb.SecondPoint == a & reb.FirstPoint == b) select reb;
      if (myr.Count() > 1 || myr.Count() == 0)
      {
        throw new DekstraException("Не найдено ребро между соседями!");
      }
      else
      {
        return myr.First();
      }
    }
    private Point GetAnotherUncheckedPoint()
    {
      IEnumerable
pointsuncheck = from p in points where p.IsChecked == false select p;
      if (pointsuncheck.Count() != 0)
      {
        float minVal = pointsuncheck.First().ValueMetka;
        Point minPoint = pointsuncheck.First();
        foreach (Point p in pointsuncheck)
        {
          if (p.ValueMetka < minVal)
          {
            minVal = p.ValueMetka;
            minPoint = p;
          }
        }
        return minPoint;
      }
      else
      {
        return null;
      }
    }
          
    public List
MinPath1(Point end)
    {
      List
listOfpoints = new List
();
      Point tempp = new Point();
      tempp = end;
      while (tempp != this.BeginPoint)
      {
        listOfpoints.Add(tempp);
        tempp = tempp.predPoint;
      }

      return listOfpoints;

    }
  class Rebro
  {
    public Point FirstPoint { get; private set; }
    public Point SecondPoint { get; private set; }
    public float Weight { get; private set; }

    public Rebro(Point first, Point second, float valueOfWeight)

    {
      FirstPoint = first;
      SecondPoint = second;
      Weight = valueOfWeight;
    }
  }
  class Point
  {
    public float ValueMetka { get; set; }
    public string Name { get; private set; }
    public bool IsChecked { get; set; }
    public Point predPoint { get; set; }
    public object SomeObj { get; set; }
    public Point(int value,bool ischecked)
    {
      ValueMetka = value;
      IsChecked = ischecked;
      predPoint = new Point();
    }
    public Point(int value, bool ischecked,string name)
    {
      ValueMetka = value;
      IsChecked = ischecked;
      Name = name;
      predPoint = new Point();
    }
    public Point()
    {
    }
  }
  static class PrintGrath
  {
    public static List PrintAllPoints(DekstraAlgorim da)
    {
      List retListOfPoints = new List();
      foreach (Point p in da.points)
      {
        retListOfPoints.Add(string.Format("point name={0}, point value={1}, predok={2}", p.Name, p.ValueMetka, p.predPoint.Name ?? "нет предка"));
      }
      return retListOfPoints;
    }
    public static List PrintAllMinPaths(DekstraAlgorim da)
    {
      List retListOfPointsAndPaths = new List();
      foreach (Point p in da.points)
      {
        
        if (p != da.BeginPoint)
        {
          string s = string.Empty;
          foreach (Point p1 in da.MinPath1(p))
          {
            s += string.Format("{0} ", p1.Name);
          }
          retListOfPointsAndPaths.Add(string.Format("Point ={0},MinPath from {1} = {2}", p.Name, da.BeginPoint.Name, s));
        }

      }
      return retListOfPointsAndPaths;

    }
  }

class DekstraException:ApplicationException

  {
    public DekstraException(string message):base(message)
    {

    }
    

  }


Natija