Найти ошибку в алгоритме обхода графа - C#

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

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

Всё работает нормально, но почему то он Выводит не правильные значения... Вот код:
Листинг программы
  1. using System;
  2. using System.Collections;
  3. using System.Linq;
  4. using System.Text;
  5. namespace ConsoleApplication1
  6. {
  7. class Program
  8. {
  9. public static int i, j, k, kol;
  10. public struct uzel
  11. {
  12. public int nom;
  13. public int ki;
  14. public int kj;
  15. };
  16. public static uzel n = new uzel();
  17. public static int[] d = new int[12];
  18. static void vkl(Stack vst, uzel n)
  19. {
  20. vst.Push(n);
  21. }
  22. static void iskl(Stack vst)
  23. {
  24. if (vst == null) Console.WriteLine("Стек пуст !");
  25. else n = (uzel)vst.Pop();
  26. }
  27. public static void Main()
  28. {
  29. Stack vstek = new Stack();
  30. string buf;
  31. int beg, en, x, i1, i2;
  32. uzel y1 = new uzel();
  33. bool[] nov = new bool[12];
  34. int[,] p = new int[11, 11];
  35. int[] m = new int[12];
  36. int[,] a = new int[11, 11]
  37. {{0,10,20,1000,1000,1000,1000,1000,1000,1000,1000},
  38. {10,0,1000,30,1000,1000,1000,1000,1000,1000,1000},
  39. {20,1000,0,10,1000,1000,10,1000,1000,1000,1000},
  40. {1000,10,10,0,20,1000,1000,1000,1000,1000,1000},
  41. {1000,1000,1000,20,0,1000,1000,1000,20,1000,1000},
  42. {1000,1000,1000,1000,1000,0,30,20,1000,1000,1000},
  43. {1000,1000,10,1000,1000,30,0,10,10,30,1000},
  44. {1000,1000,1000,1000,1000,20,10,0,1000,1000,1000},
  45. {1000,1000,1000,1000,20,1000,10,1000,0,20,30},
  46. {1000,1000,1000,1000,1000,1000,30,1000,20,0,1000},
  47. {1000,1000,1000,1000,1000,1000,1000,1000,30,1000,0},};
  48. string[] sum = new string[10];
  49. for (i = 0; i < 11; i++)
  50. {
  51. p[i, 0] = i; k = 1;
  52. for (j = 0; j < 11; j++)
  53. if ((a[i, j] != 1000) && (a[i, j] != 0))
  54. {
  55. p[i, k] = j;
  56. k++;
  57. }
  58. p[i, k] = 1000;
  59. }
  60. for (i = 0; i < 11; i++)
  61. {
  62. k = 0;
  63. while (p[i, k] != 1000)
  64. {
  65. Console.Write(" {0}", p[i, k]);
  66. k++;
  67. }
  68. Console.WriteLine();
  69. }
  70. Console.Write("Введите номер начального узла графа? ");
  71. buf = Console.ReadLine();
  72. beg = Convert.ToInt32(buf);
  73. Console.Write("Введите номер конечного узла графа? ");
  74. buf = Console.ReadLine();
  75. en = Convert.ToInt32(buf);
  76. for (i = 0; i < 12; i++)
  77. {
  78. nov[i] = true;
  79. m[i] = 0;
  80. }
  81. int k5 = 0;
  82. int[] s = new int[20];
  83. int s1 = 0;
  84. int[] s5 = new int[10];
  85. nov[11] = false;
  86. x = 1; //Номер очередного маршрута
  87. m[1] = beg; i1 = 2;
  88. y1.nom = beg; //Определяем поле nom узла y1
  89. y1.ki = beg; // Запоминаем номер списка смеж. вершин
  90. y1.kj = 0; // Запоминаем номер текущей позиции в списке
  91. vkl(vstek, y1);
  92. kol = 1;
  93. nov[beg] = false;
  94. nov[en] = false;
  95. i = beg; j = 0;
  96. while (kol != 0)
  97. {
  98. do
  99. {
  100. j++;
  101. int f = 0;
  102. if (p[i, j] == en)
  103. {
  104. k5 = 0;
  105. Console.Write(" путь - {0} -", x); x++;
  106. for (i2 = 1; i2 < i1; i2++)
  107. {
  108. Console.Write(" {0} ", m[i2]);
  109. s[i2 - 1] = m[i2];
  110. k5++;
  111. f = i2;
  112. }
  113. k5++;
  114. s[f] = en;
  115. for (int c = 1; c < k5 - 1; c++)
  116. {
  117. s1 += a[s[c], s[c + 1]];
  118. }
  119. s1 += a[s[0], s[1]];
  120. if ((s[0] != s[k5 - 2]) && (s[1] != en)) { s1 += a[s[k5 - 2], en]; }
  121. Console.Write(" {0}", en);
  122. Console.WriteLine(" Последовательное сопротивление:" + s1);
  123. s1 = 0;
  124. for (int c = 0; c < 20; c++)
  125. {
  126. s[c] = 0;
  127. }
  128. }
  129. }
  130. while ((p[i, j] != 1000) && (!nov[p[i, j]]));
  131. if (p[i, j] != 1000)
  132. if (nov[p[i, j]])
  133. {
  134. y1.ki = i;
  135. y1.kj = j;
  136. i = p[i, j];
  137. y1.nom = i;
  138. vkl(vstek, y1);
  139. j = 0;
  140. kol++;
  141. nov[i] = false;
  142. m[i1] = i;
  143. i1++;
  144. };
  145. if (p[i, j] == 1000)
  146. {
  147. kol--;
  148. if (kol != 0)
  149. {
  150. iskl(vstek);
  151. i = n.ki;
  152. j = n.kj;
  153. i1--;
  154. m[i1] = 0;
  155. nov[n.nom] = true;
  156. }
  157. };
  158. }
  159. Console.WriteLine();
  160. Console.WriteLine("Для продолжения нажмите клавишу Enter");
  161. Console.ReadLine();
  162. }
  163. }
  164. }
Сопротивление цепи где то не обновляется.. или что то такое... Очень рассчитываю на вашу помощь Ход работы программы и сам граф ниже...

Решение задачи: «Найти ошибку в алгоритме обхода графа»

textual
Листинг программы
  1. using System;
  2. using System.Collections;
  3. using System.Linq;
  4. using System.Text;
  5. namespace ConsoleApplication1
  6. {
  7.     class Program
  8.     {
  9.         public static int i, j, k, kol;
  10.         public struct uzel
  11.         {
  12.             public int nom;
  13.             public int ki;
  14.             public int kj;
  15.         };
  16.         public static uzel n = new uzel();
  17.         public static int[] d = new int[12];
  18.         static void vkl(Stack vst, uzel n)
  19.         {
  20.             vst.Push(n);
  21.         }
  22.         static void iskl(Stack vst)
  23.         {
  24.             if (vst == null) Console.WriteLine("Стек пуст !");
  25.             else n = (uzel)vst.Pop();
  26.         }
  27.         public static void Main()
  28.         {
  29.             Stack vstek = new Stack();
  30.             string buf;
  31.             int beg, en, x, i1, i2;
  32.             uzel y1 = new uzel();
  33.             bool[] nov = new bool[12];
  34.             int[,] p = new int[11, 11];
  35.             int[] m = new int[12];
  36.             int[,] a = new int[11, 11]
  37. {{0,10,20,1000,1000,1000,1000,1000,1000,1000,1000},
  38. {10,0,1000,30,1000,1000,1000,1000,1000,1000,1000},
  39. {20,1000,0,10,1000,1000,10,1000,1000,1000,1000},
  40. {1000,10,10,0,20,1000,1000,1000,1000,1000,1000},
  41. {1000,1000,1000,20,0,1000,1000,1000,20,1000,1000},
  42. {1000,1000,1000,1000,1000,0,30,20,1000,1000,1000},
  43. {1000,1000,10,1000,1000,30,0,10,10,30,1000},
  44. {1000,1000,1000,1000,1000,20,10,0,1000,1000,1000},
  45. {1000,1000,1000,1000,20,1000,10,1000,0,20,30},
  46. {1000,1000,1000,1000,1000,1000,30,1000,20,0,1000},
  47. {1000,1000,1000,1000,1000,1000,1000,1000,30,1000,0},};
  48.             string[] sum = new string[10];
  49.             for (i = 0; i < 11; i++)
  50.             {
  51.                 p[i, 0] = i; k = 1;
  52.                 for (j = 0; j < 11; j++)
  53.                     if ((a[i, j] != 1000) && (a[i, j] != 0))
  54.                     {
  55.                         p[i, k] = j;
  56.                         k++;
  57.                     }
  58.                 p[i, k] = 1000;
  59.             }
  60.             for (i = 0; i < 11; i++)
  61.             {
  62.                 k = 0;
  63.                 while (p[i, k] != 1000)
  64.                 {
  65.                     Console.Write(" {0}", p[i, k]);
  66.                     k++;
  67.                 }
  68.                 Console.WriteLine();
  69.             }
  70.             Console.Write("Введите номер начального узла графа? ");
  71.             buf = Console.ReadLine();
  72.             beg = Convert.ToInt32(buf);
  73.             Console.Write("Введите номер конечного узла графа? ");
  74.             buf = Console.ReadLine();
  75.             en = Convert.ToInt32(buf);
  76.             for (i = 0; i < 12; i++)
  77.             {
  78.                 nov[i] = true;
  79.                 m[i] = 0;
  80.             }
  81.             int k5 = 0;
  82.             int[] s = new int[20];
  83.             int s1 = 0;
  84.             int[] s5 = new int[10];
  85.             nov[11] = false;
  86.             x = 1;         //Номер очередного маршрута
  87.             m[1] = beg; i1 = 2;
  88.             y1.nom = beg;  //Определяем поле nom узла y1
  89.             y1.ki = beg;   // Запоминаем номер списка смеж. вершин
  90.             y1.kj = 0;     // Запоминаем номер текущей позиции в списке
  91.             vkl(vstek, y1);
  92.             kol = 1;
  93.             nov[beg] = false;
  94.             nov[en] = false;
  95.             i = beg; j = 0;
  96.             while (kol != 0)
  97.             {
  98.                 do
  99.                 {
  100.                     j++;
  101.                     int f = 0;
  102.                     if (p[i, j] == en)
  103.                     {
  104.                         k5 = 0;
  105.                         Console.Write(" путь - {0} -", x); x++;
  106.                         for (i2 = 1; i2 < i1; i2++)
  107.                         {
  108.                             Console.Write(" {0} ", m[i2]);
  109.                             s[i2 - 1] = m[i2];
  110.                             k5++;
  111.                             f = i2;
  112.                         }
  113.                         k5++;
  114.                         s[f] = en;
  115.                         for (int c = 1; c < k5 - 1; c++)
  116.                         {
  117.                             s1 += a[s[c], s[c + 1]];
  118.                         }
  119.                         s1 += a[s[0], s[1]];
  120.                         //if ((s[0] != s[k5 - 2]) && (s[1] != en)) { s1 += a[s[k5 - 2], en]; }
  121.                         Console.Write(" {0}", en);
  122.                         Console.WriteLine(" Последовательное сопротивление:" + s1);
  123.                         s1 = 0;
  124.                         for (int c = 0; c < 20; c++)
  125.                         {
  126.                             s[c] = 0;
  127.                         }
  128.                     }
  129.                 }
  130.                 while ((p[i, j] != 1000) && (!nov[p[i, j]]));
  131.                 if (p[i, j] != 1000)
  132.                     if (nov[p[i, j]])
  133.                     {
  134.                         y1.ki = i;
  135.                         y1.kj = j;
  136.                         i = p[i, j];
  137.                         y1.nom = i;
  138.                         vkl(vstek, y1);
  139.                         j = 0;
  140.                         kol++;
  141.                         nov[i] = false;
  142.                         m[i1] = i;
  143.                         i1++;
  144.                     };
  145.                 if (p[i, j] == 1000)
  146.                 {
  147.                     kol--;
  148.                     if (kol != 0)
  149.                     {
  150.                         iskl(vstek);
  151.                         i = n.ki;
  152.                         j = n.kj;
  153.                         i1--;
  154.                         m[i1] = 0;
  155.                         nov[n.nom] = true;
  156.                     }
  157.                 };
  158.             }
  159.             Console.WriteLine();
  160.             Console.WriteLine("Для продолжения нажмите клавишу Enter");
  161.             Console.ReadLine();
  162.         }
  163.     }
  164. }

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


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

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

14   голосов , оценка 3.643 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут