Разработка и реализация на языке высокого уровня алгоритма выделения сильносвязных компонент ориентированного графа - Курсовая работа

Си - стандартизированный процедурный язык программирования, разработанный в начале 1970-х годов сотрудниками Bell Labs Кеном Томпсоном и Деннисом Ритчи как развитие языка Би. Авторы языка хотели, чтобы программы на нем легко компилировались с помощью однопроходного компилятора, чтобы каждой элементарной составляющей программы после компиляции соответствовало весьма небольшое число машинных команд, а использование базовых элементов языка не задействовало библиотеку времени выполнения. К тому же, несмотря на свою низкоуровневую природу, язык позволяет создавать переносимые программы и поддерживает в этом программиста. Си (как и ОС UNIX, с которой он долгое время был связан) создавался программистами и для программистов, круг которых был бы ненамного шире круга разработчиков языка. Си создавался с одной важной целью: сделать более простым написание больших программ с минимумом ошибок по правилам процедурного программирования, не добавляя на итоговый код программ лишних накладных расходов для компилятора, как это всегда делают языки очень высокого уровня, такие как Бейсик.При этом Х называется множеством вершин , а Г - множеством дуг графа G . Любое конечное множество точек (вершин), некоторые из которых попарно соединены стрелками , (в теории графов эти стрелки называются дугами), можно рассматривать как граф. Если в множестве Г все пары упорядочены, то такой граф называют ориентированным. Вершина Х называется инцидентной ребру G , если ребро соединяет эту вершину с какой-либо другой вершиной. Подграфом G(V1, E1) графа G(V, E) называется граф с множеством вершин V1 ?V и множеством ребер (дуг) E?? E, - такими, что каждое ребро (дуга) из E1 инцидентно (инцидентна) только вершинам из V1 .Вершины графа называются смежными , если существует ребро , их соединяющее. Два ребра G1 и G2 называются смежными, если существует вершина, инцидентная одновременно G1 и G2. Каждый граф можно представить в пространстве множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам (или дугам - в последнем случае направление обычно указывается стрелочками).Пусть G(V, E) - связный неориентированный граф, каждому ребру которого приписан некоторый вес отличный от 0 (рис. Существуют различные способы задания графа: в виде матрицы весов, матрицы смежности или инцидентности, списка ребер. Матрицей весов называется квадратная матрица размерности nxn (n-количество вершин), элемент которой стоящий в i строке и j столбце определяется по правилу: Матрица смежности - это булева матрица (иногда ее называют двоичной или битовой) порядка n: R=||r[ij]||, в которой строкам и столбцам поставлены в соответствие вершины графа G, и r[ij]=1,если вершины vi, vj V смежные, и r[ij]=0 в противном случае. 1, матрица смежности имеет вид таблицы 1. Матрица инцидентности - это также булева матрица Q=||q[ij]|| размера nxm, в которой строкам поставлены в соответствие вершины графа, а столбцам - ребра.На практике часто возникают задачи в отыскании сильно связных подграфов (сильно связных компонентов) ориентированного графа. Для определения сильно связных подграфов введем понятие следующих матриц: - матрица достижимости R=||rij||; Размер всех матриц n?n, где n - число вершин графа, элементы матриц определяются следующим образом: rij=1, если вершина j достижима из вершины i, rij=0, если вершина j не достижима из вершины i, qij=1, если вершина i достижима из вершины j, qij=0, если вершина i не достижима из вершины j, hij=1, если вершина j достижима из вершины i и вершина i достижима из вершины j, то есть если rij=1 и qij=1. hij=0, если вершина j не достижима из вершины i или вершина i не достижима из вершины j, то есть если rij=0 или qij=0. Отношение взаимодостижимости, определяемое матрицей H=||hij||, разбивает все множество вершин V орграфа G на классы взаимодостижимых вершин. Анализируя матрицу H, выделяем классы взаимодостижимых вершин и строим сильно связные подграфы исходного орграфа.Итак, чтобы перейти к реализации данного алгоритма, необходимо разделить каждую фазу, обозначенную выше, на определенное количество шагов: Две вершины A,B ориентированного графа называются сильно, связанными если есть пути из Сильно связной компонентой ориентированного графа называют множество вершин графа, в котором для любых двух вершин есть пути сиз первой во вторую и из второй в первую. Многие алгоритмы, работающие на ориентированных графах начинают свою работу с выделения сильно связныхкомпонент: после этого задача решается для каждой компоненты в отдельности, и решения комбинируются.1.) Вводим число вершин в графе. 3.) Вводим вершину, куда ведет связь. P.S Граф задается массивом связей, выходящих из каждой вершины.Преобразования проходят успешно.Курсовой проект выполнен успешно. Программа работает быстро и без сбоев.#define MAX_EDGES 10 // Максимальное количество ребер, выходящих из одной вершины int edges[MAX_NODES][MAX_EDGES]; // Граф, в котором ищем сильно связные компоненты int edges_c[MAX_NODES]; int state[MAX_NODES]; // Используется в по

Содержание

Введение

1. Основные понятия и определения теории графов

1.1 Теоремы

1.2 Способы задания графа

1.3 Сильная связность графов

2. Последовательность выполнения работы

2.1 Построение блок-схем алгоритма

3. Тестирование разработанного программного обеспечения

3.1 Подбор тестовых данных

3.2 Анализ и исправление ошибок

Заключение

Список используемой литературы

Приложение

Язык С/С

Си - стандартизированный процедурный язык программирования, разработанный в начале 1970-х годов сотрудниками Bell Labs Кеном Томпсоном и Деннисом Ритчи как развитие языка Би. Си был создан для использования в операционной системе UNIX. С тех пор он был портирован на многие другие операционные системы и стал одним из самых используемых языков программирования. Си ценят за его эффективность. Он является самым популярным языком для создания системного программного обеспечения. Его также часто используют для создания прикладных программ. Несмотря на то, что Си не разрабатывался для новичков, он активно используется для обучения программированию. В дальнейшем синтаксис языка Си стал основой для многих других языков.

Для языка Си характерны лаконичность, стандартный набор конструкций управления потоком выполнения, структур данных и обширный набор операций.

Язык программирования Си отличается минимализмом. Авторы языка хотели, чтобы программы на нем легко компилировались с помощью однопроходного компилятора, чтобы каждой элементарной составляющей программы после компиляции соответствовало весьма небольшое число машинных команд, а использование базовых элементов языка не задействовало библиотеку времени выполнения. Однопроходный компилятор компилирует программу, не возвращаясь назад, к уже обработанному тексту. Поэтому использованию функции и переменных должно предшествовать их объявление. Код на Си можно легко писать на низком уровне абстракции, почти как на ассемблере. Иногда Си называют «универсальным ассемблером» или «ассемблером высокого уровня», что отражает различие языков ассемблера для разных платформ и единство стандарта Си, код которого может быть скомпилирован без изменений практически на любой модели компьютера. Си часто называют языком среднего уровня или даже низкого уровня, учитывая то, как близко он работает к реальным устройствам. Однако, в строгой классификации, он является языком высокого уровня.

Компиляторы Си разрабатываются сравнительно легко благодаря простоте языка и малому размеру стандартной библиотеки. Поэтому данный язык доступен на самых различных платформах (возможно, круг этих платформ шире, чем у любого другого существующего языка). К тому же, несмотря на свою низкоуровневую природу, язык позволяет создавать переносимые программы и поддерживает в этом программиста. Программы, соответствующие стандарту языка, могут компилироваться на самых различных компьютерах.

Си (как и ОС UNIX, с которой он долгое время был связан) создавался программистами и для программистов, круг которых был бы ненамного шире круга разработчиков языка. Несмотря на это, область использования языка значительно шире задач системного программирования.

Си создавался с одной важной целью: сделать более простым написание больших программ с минимумом ошибок по правилам процедурного программирования, не добавляя на итоговый код программ лишних накладных расходов для компилятора, как это всегда делают языки очень высокого уровня, такие как Бейсик. С этой стороны Си имеет следующие важные особенности: · простую языковую базу, из которой вынесены в библиотеки многие существенные возможности, вроде математических функций или функций управления файлами;

· ориентацию на процедурное программирование, обеспечивающую удобство применения структурного стиля программирования;

· систему типов, предохраняющую от бессмысленных операций;

· использование препроцессора для, например, определения макросов и включения файлов с исходным кодом;

· непосредственный доступ к памяти компьютера через использование указателей;

· минимальное число ключевых слов;

· передачу параметров в функцию по значению, а не по ссылке (при этом передача по ссылке эмулируется с помощью указателей);

· указатели на функции и статические переменные

· области действия имен;

· структуры и объединения - определяемые пользователем собирательные типы данных, которыми можно манипулировать как одним целым;

Вот некоторые особенности других языков программирования, которых не имеет Си: · автоматическое управление памятью;

· поддержка объектно-ориентированного программирования (при этом первые версии C генерировали код программы на языке Си);

· замыкание ;

· вложенные функции (существуют компиляторы языка Си реализующие эту функцию, например компилятор GNU );

· полиморфизм функций и операторов ;

· встроенная поддержка многозадачности и сети

· функции высшего порядка

· карринг.

После появления язык Си был хорошо принят, потому что он позволял быстро создавать компиляторы для новых платформ, а также позволял программистам довольно точно представлять, как выполняются их программы. Благодаря этому программы, написанные на Си, эффективнее написанных на многих других языках. Как правило, лишь оптимизированный вручную код на ассемблере может работать еще быстрее, потому что он дает полный контроль над машиной, однако развитие современных компиляторов вместе с усложнением современных процессоров сократило этот разрыв.

Одним из последствий высокой эффективности и переносимости Си стало то, что многие компиляторы, интерпретаторы и библиотеки других языков высокого уровня часто выполнены на языке Си.

После публикации K&R C в язык было добавлено несколько возможностей, поддерживаемый компиляторами AT&T и некоторых других производителей: · функции, не возвращающие значение (с типом void) и указатели, не имеющие типа (с типом void *);

· функции, возвращающие объединения и структуры;

· имена полей данных структур в разных пространствах имен для каждой структуры;

· присваивания структур;

· спецификатор констант (const);

· стандартная библиотека , реализующая большую часть функций, введенных различными производителями;

· перечислимый тип (enum);

· дробное число одинарной точности (float). граф программа алгоритм

Курсовой проект выполнен успешно. Программа работает быстро и без сбоев. Блок-схема простая и достаточно понятная. Среда программирования Eclipse универсальна и очень удобна. Простой, понятный интерфейс и хорошее быстродействие помогают разрабатывать программы разной сложности. Универсализм программы дает возможность разрабатывать программные приложения не только на языке «С» и «C »

1.) Семакин И.Г. Основы программирования [Текст] - М.: КОМПЬЮТЕРПРЕСС, 2004. - 170 с.

2.) Макарова С.В. Информатика М [Текст] / Под ред. Б.В. Лукашова. - М.:Информатика, 2009. - 176 с.

3.) Панасенко, Л.Г. Программирование на Си[Текст] // Под ред. А.В. Иванова.- М.:Информатика, 2008. - 45 с.

4.) Партыка, Т.Л. Основы алгоритмирования Учеб.пособие [Текст] / Партыка, Т.Л. - М.: Форум, 2005. - 142 с.

5.) Програмирование на СИ ИНФРА-М [Текст] / Под ред. Власенко, П.Г.. - М.:Информатика, 2009. - 109 с..