Объектно-ориентированное программирование» для студентов специальности 5В070300 «Информационные системы» идля оп 6В06120 «Информационные системы» Шымкент 2022
жүктеу/скачать 1,44 Mb.
|
На рис.12.1 цикл Гамильта обозначен плоской линией. Существует много определений структуры, такой как ветви. Приведем два определения ветвей через связанный граф. Ответвление-это связанный граф, число дуг которого вместе меньше числа потолков. Ветви-это связанный граф, который не имеет петель. При решении» графических «задач усложнение алгоритма зависит от его» машинного «представления, т. е. в зависимости от типа» графической " задачи в памяти ЭВМ используется определенная форма представления графа.Способы визуализации графа в памяти компьютера 12.2.1 отображение графа в виде матрицы стыковки (матрицы инцидентностей). Приведите простой неориентированный граф, показанный на рис. 12.2. Рисунок 12.2-простой неориентированный граф По теории графов в памяти ЭВМ в качестве классического метода отображения графа используется матрица стыковки. В такой матрице число строк соответствует числу перекрытий, а число столбцов-числу графов. Если потолок и стена являются стыковыми, то на пересечении колонны и дороги пишется 1, в противном случае пишется 0. Для простейшего неориентированного графа, представленного на рис.12.2, можно построить матрицу стыковки, представленную в табл. 12.1. Таблица 12.1-Матрица стыковки Если дуга «выходит» из соответствующего потолка, то в ориентировочном графе направление дуги в матрице стыковки равно 1, Если дуга «входит» в соответствующий потолок, то минус 1. Рассмотрим матрицу стыковки для ориентированного графа, представленную на рис. 12.3 Рисунок 12.3-ориентированный граф Матрица стыковки ориентированного графа представлена в таблице 12.2. Таблица 12.2-матрица стыковки ориентированного графа Следует отметить, что матрицы стыковки считаются одним из недопустимых способов хранения графов в памяти ЭВМ, так как ее значения не дают достоверной информации. Например, в самой матрице невозможно определить, связаны ли 1-й и 2-й крыши. 12.2.2 отображение графа через матрицу. В коррумпированной матрице количество строк и столбцов равно количеству перекрытий. На пересечении располагается значение, характеризующее связь этих потолков, например, если стена, то равное 1, Если стена отсутствует, то 0. Для ориентированных графов число строк и столбцов в матрице равно числу вершин. На перекрестке располагается значение, характеризующее связь этих потолков, например, если между соответствующими потолками имеется связь, равная 1, Если связи нет, то 0. Матрица коррупции для графа, представленная на рис.12.2, представлена в таблице 12.3. 12.3-кесте –матрица Матрица для ориентированного графа, представленная на рисунке 12.3, соответствует таблице 12.4. Таблица 12.4-матрица ориентированного графа 12.2.3 отображение графа в виде списка пар. Отображение графа в виде списка коррупциогенных пар потолков. Например, графы, представленные выше, могут быть представлены списком коррупциогенных пар потолков. 1-граф 2-граф 1) 1 – 2 1 – 2 2) 1 – 4 1 – 3 3) 1 – 5 3 – 2 4) 2 – 3 3 – 4 5) 2 – 4 5 – 4 6) 3 – 5 5 – 6 7) 3 – 6 6 – 5 8) 4 – 5 1– 2 9) 5 – 6 1– 2 Эти списки могут быть отображены в памяти ЭВМ в виде двумерного массива. Хранение графов в памяти ЭВМ таким образом считается наиболее эффективным, но не всегда приемлемым для работы. 12.2.4 отображение графы в виде списка коррумпированных потолков. В некоторых отчетах для графов требуется отображение графских потолков в виде списочной структуры графских потолков. Например, стек, очередь, простой список. В этом случае обычно создается массив по темам списков коррупционеров. Например, граф, представленный на рис. 12.2, может быть записан в виде массива заголовков, списка соседних вершин графа, как показано ниже: M[1]->1->2->4->5->NULL; M[2]->2->1->3->4->NULL; M[3]->3->2->5->6->NULL; M[4]->4->1->2->5->NULL; M[5]->5->3->4->6->NULL; M[6]->6->3->5->NULL; Граф, представленный на рис. 12.3, может быть записан в виде массива заголовков, списка соседних вершин графа, как показано ниже: M[1]->1->2->3->NULL; M[2]->2->NULL; M[3]->3->2->4->NULL; M[4]->4->NULL; M[5]->5->4->6->NULL; M[6]->6->5->NULL; Данная форма отображения графа подходит для выполнения различных алгоритмов перемещения графа. Алгоритмы для графов. Алгоритмы прохождения графов Есть группа транспортных отчетов, которые требуют «сканирования» всех потолков графа. Кроме того, каждый потолок должен быть «рассмотрен» только один раз. В теории графов известны два основных алгоритма перемещения графов: перемещение графа по «глубине» и по «горизонтали». В первом случае алгоритм использует структуру типа стека, а во втором – структуру типа очереди. С точки зрения» алгоритмизации «первому случаю можно придать большее значение, так как в нем записывается алгоритм» возврата", используемый в сложных структурах.Графты «тереңдігі» бойынша жүріп өту алгоритмінің жұмысын 13.1-суретте көрсетілген, күрделілігі орташа мысалда қарастырайық. Рисунок 13.1-график средней сложности Алгоритм перемещения графа по «глубине» использует понятие «новых» потолков графа, т. е. «нерассмотренных» потолков. Рассмотрим его работу: - все холмы графа объявляются «новыми «(в алгоритме Дейкстра используется термин» временными"). Мы начинаем просмотр графа с определенного потолка, например, после того, как мы смотрим на него с 0-го холма, мы помечаем его как «не новый; - из всего нового списка, соединенного с заданным потолком, выбираем самый низкий потолок. В рассматриваемом примере это потолок 1; - объявляем его первым, после просмотра отмечаем его «не новым; – если у рассматриваемого потолка нет новых натяжных потолков, то возвращаемся к предыдущему потолку (работа стека); - процесс повторяется до тех пор, пока не появятся» новые " потолки. Используя рассмотренный алгоритм на графике, представленном на рис. 13.1, получим схему сканирования потолков:. 0 – 1 – 3 – 4 – 5 – 7 – 8 – 6 – 2 – 12 – 11 – 9 – 10. При рассмотрении графа по "горизонтали «также используется понятие» новые" потолки графа. Рассмотрим его работу: - все холмы графа объявляются «новыми". Начнем прохождение графа с определенного первого холма, например, с 0-го холма. После того, как он осмотрел потолок (нажимаем на номер потолка), помечаем его как " не новый; - список всех новых натяжных потолков, связанных с просмотренным потолком, выстраиваем очередь в порядке возрастания: 1 – 3 – 11; - выбираем из очереди потолок (на этом примере это потолок 1), смотрим его, отмечаем «не новый». Весь список коррупционеров, связанных с рассмотренным списком, выстраиваем в очередь в порядке возрастания: 3-11; - процессграф повторяется до тех пор, пока в нем не появятся холмы. Рассмотренных потолков графа:0 – 1 – 3 – 11 – 4 – 6 – 9 – 10 – 5 – 8 – 12 – 2 – 7. Рассмотрим программное выполнение алгоритма перемещения графа по «глубине» на примере графа, показанного на рис.13.1. Код программы: using System; using System.Collections; using System.Text; namespace ConsoleApplication1 { class Program { public static int i, j, k, n,kol; static void vkl(Stack vst, int n) { vst.Push(n); } static void iskl(Stack vst) { if (vst == null) Console.WriteLine("Stek bos!"); else n = (int)vst.Pop(); } public static void Main() { Stack vstek = new Stack(); //int i, j, k, n; bool[] nov = new bool[13]; int[,] p = new int[13, 13]; int[,] a = new int[13, 13] {{0,1,1000,1,1000,1000,1000,1000,1000,1000,1000, 1, 1000 }, {1,0,1000,1,1000,1000,1000,1000,1000,1000,1000,1000, 1000}, {1000,1000,0,1000,1000,1000,1,1000,1000,1000,1000,1000,1000}, {1,1,1000,0,1,1000,1,1000,1000,1000,1000,1,1000}, {1000,1000,1000,1,0,1,1,1000,1,1000,1000,1000, 1}, {1000,1000,1000,1000,1,0,1000,1,1,1000,1000,1000,1000}, {1000,1000,1,1,1,1000, 0,1000,1000,1000,1000,1000,1000}, {1000,1000,1000,1000,1000,1,1000,0,1,1000,1000,1000,1000}, {1000,1000,1000,1000,1,1,1000,1,0,1000,1000,1000,1000}, {1000,1000,1000,1000,1000,1000,1000,1000,1000,0,1,1,1000}, {1000,1000,1000,1000,1000,1000,1000,1000,1000,1,0,1,1000}, {1,1000,1000,1,1000,1000,1000,1000,1000,1,1,0,1000}, {1000,1000,1000,1000,1,1000,1000,1000,1000,1000,1000,1000,0}, }; for (i = 0; i < 13; i++) { p[i,0] = i;k=1; for (j = 0; j < 13; j++) if ((a[i, j] != 1000) && (a[i, j] != 0)) { p[i,k]=j; k++; } p[i,k]=1000; } for (i = 0; i < 13; i++) { k = 0; while (p[i,k] != 1000) { Console.Write(" {0}", p[i,k]); k++; } Console.WriteLine(); } // графты жүріп өту bool b; // Бастапқы шарттарды беру for (i = 0; i < 13; i++) nov[i] = true; vkl(vstek,p[0,0]); kol = 1; Console.Write(" {0}", p[0, 0]); nov[0] = false; // графты «тереңдігі» бойынша жүріп өтуциклі while (kol != 0) { i = (int)vstek.Peek(); if (p[i,0] == 1000) b = false; else b = !nov[p[i,0]]; // графтың жаңа төбесін іздеу k = 0; while (b == true) { k++; if (p[i,k] == 1000) b = false; else { b = !nov[p[i,k]]; if (nov[p[i, k]]) { vkl(vstek, p[i, k]); kol++; } } } if (p[i,k] != 1000) // егер графтың жаңа төбесі табылса { i = p[i,k]; Console.Write(" {0}", i); nov[i] = false; } else // тізімде жаңа төбе жоқ болса, алдынғы төбеге оралу керек { iskl(vstek); i = n; kol--; } } Console.WriteLine(); Console.WriteLine("Enter pernesin basiniz "); Console.ReadLine(); } } } жүктеу/скачать 1,44 Mb. Достарыңызбен бөлісу:
|