Найти ошибку в алгоритме обхода графа - C#
Формулировка задачи:
Всё работает нормально, но почему то он Выводит не правильные значения...
Вот код:
Сопротивление цепи где то не обновляется.. или что то такое... Очень рассчитываю на вашу помощь
Ход работы программы и сам граф ниже...
Листинг программы
- 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();
- public static int[] d = new int[12];
- 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[12];
- int[,] p = new int[11, 11];
- int[] m = new int[12];
- int[,] a = new int[11, 11]
- {{0,10,20,1000,1000,1000,1000,1000,1000,1000,1000},
- {10,0,1000,30,1000,1000,1000,1000,1000,1000,1000},
- {20,1000,0,10,1000,1000,10,1000,1000,1000,1000},
- {1000,10,10,0,20,1000,1000,1000,1000,1000,1000},
- {1000,1000,1000,20,0,1000,1000,1000,20,1000,1000},
- {1000,1000,1000,1000,1000,0,30,20,1000,1000,1000},
- {1000,1000,10,1000,1000,30,0,10,10,30,1000},
- {1000,1000,1000,1000,1000,20,10,0,1000,1000,1000},
- {1000,1000,1000,1000,20,1000,10,1000,0,20,30},
- {1000,1000,1000,1000,1000,1000,30,1000,20,0,1000},
- {1000,1000,1000,1000,1000,1000,1000,1000,30,1000,0},};
- string[] sum = new string[10];
- for (i = 0; i < 11; i++)
- {
- p[i, 0] = i; k = 1;
- for (j = 0; j < 11; j++)
- if ((a[i, j] != 1000) && (a[i, j] != 0))
- {
- p[i, k] = j;
- k++;
- }
- p[i, k] = 1000;
- }
- for (i = 0; i < 11; 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 < 12; i++)
- {
- nov[i] = true;
- m[i] = 0;
- }
- int k5 = 0;
- int[] s = new int[20];
- int s1 = 0;
- int[] s5 = new int[10];
- nov[11] = 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++;
- int f = 0;
- if (p[i, j] == en)
- {
- k5 = 0;
- Console.Write(" путь - {0} -", x); x++;
- for (i2 = 1; i2 < i1; i2++)
- {
- Console.Write(" {0} ", m[i2]);
- s[i2 - 1] = m[i2];
- k5++;
- f = i2;
- }
- k5++;
- s[f] = en;
- for (int c = 1; c < k5 - 1; c++)
- {
- s1 += a[s[c], s[c + 1]];
- }
- s1 += a[s[0], s[1]];
- if ((s[0] != s[k5 - 2]) && (s[1] != en)) { s1 += a[s[k5 - 2], en]; }
- Console.Write(" {0}", en);
- Console.WriteLine(" Последовательное сопротивление:" + s1);
- s1 = 0;
- for (int c = 0; c < 20; c++)
- {
- s[c] = 0;
- }
- }
- }
- 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();
- }
- }
- }
Решение задачи: «Найти ошибку в алгоритме обхода графа»
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();
- public static int[] d = new int[12];
- 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[12];
- int[,] p = new int[11, 11];
- int[] m = new int[12];
- int[,] a = new int[11, 11]
- {{0,10,20,1000,1000,1000,1000,1000,1000,1000,1000},
- {10,0,1000,30,1000,1000,1000,1000,1000,1000,1000},
- {20,1000,0,10,1000,1000,10,1000,1000,1000,1000},
- {1000,10,10,0,20,1000,1000,1000,1000,1000,1000},
- {1000,1000,1000,20,0,1000,1000,1000,20,1000,1000},
- {1000,1000,1000,1000,1000,0,30,20,1000,1000,1000},
- {1000,1000,10,1000,1000,30,0,10,10,30,1000},
- {1000,1000,1000,1000,1000,20,10,0,1000,1000,1000},
- {1000,1000,1000,1000,20,1000,10,1000,0,20,30},
- {1000,1000,1000,1000,1000,1000,30,1000,20,0,1000},
- {1000,1000,1000,1000,1000,1000,1000,1000,30,1000,0},};
- string[] sum = new string[10];
- for (i = 0; i < 11; i++)
- {
- p[i, 0] = i; k = 1;
- for (j = 0; j < 11; j++)
- if ((a[i, j] != 1000) && (a[i, j] != 0))
- {
- p[i, k] = j;
- k++;
- }
- p[i, k] = 1000;
- }
- for (i = 0; i < 11; 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 < 12; i++)
- {
- nov[i] = true;
- m[i] = 0;
- }
- int k5 = 0;
- int[] s = new int[20];
- int s1 = 0;
- int[] s5 = new int[10];
- nov[11] = 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++;
- int f = 0;
- if (p[i, j] == en)
- {
- k5 = 0;
- Console.Write(" путь - {0} -", x); x++;
- for (i2 = 1; i2 < i1; i2++)
- {
- Console.Write(" {0} ", m[i2]);
- s[i2 - 1] = m[i2];
- k5++;
- f = i2;
- }
- k5++;
- s[f] = en;
- for (int c = 1; c < k5 - 1; c++)
- {
- s1 += a[s[c], s[c + 1]];
- }
- s1 += a[s[0], s[1]];
- //if ((s[0] != s[k5 - 2]) && (s[1] != en)) { s1 += a[s[k5 - 2], en]; }
- Console.Write(" {0}", en);
- Console.WriteLine(" Последовательное сопротивление:" + s1);
- s1 = 0;
- for (int c = 0; c < 20; c++)
- {
- s[c] = 0;
- }
- }
- }
- 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();
- }
- }
- }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д