Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

БЕЛГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ (НИУ «БелГУ»)

ФАКУЛЬТЕТ КОМПЬЮТЕРНЫХ НАУК И ТЕЛЕКОММУНИКАЦИЙ

КАФЕДРА ПРИКЛАДНОЙ ИНФОРМАТИКИ

Курсовая работа

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

Студент дневного отделения

1 курса группы 141104

Чистякова Егора Евгеньевича

Научный руководитель:

Старший преподаватель

Гурьянова Ирина Владимировна

БЕЛГОРОД 2012

Постановка задачи

В данной курсовой работе требуется разработать и реализовать на языке высокого уровня алгоритм выделения сильносвязных компонент ориентированного графа.

Содержание

Введение

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

1.1 Теоремы

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

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

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

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

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

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

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

Заключение

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

Приложение

Введение

Язык С/C++

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

· замыкание;

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

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

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

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

· карринг.

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

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

После публикации K&R C в язык было добавлено несколько возможностей, поддерживаемый компиляторами AT&T и некоторых других производителей:

· функции, не возвращающие значение (с типом void) и указатели, не имеющие типа (с типом void *);

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

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

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

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

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

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

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

граф программа алгоритм

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

Теория графов представляет собой раздел математики, имеющий широкое практическое применение. В её терминах формулируется большое число задач, связанных с дискретными объектами. Такие задачи возникают при проектировании интегральных схем и схем управления, электрических цепей, блок-схем программ, в экономике, статистике, химии, биологии и в других областях. Теория графов становится одной из существенных частей математического аппарата кибернетики, языком дискретной математики.

В отличие от других научных дисциплин, теория графов имеет вполне определенную дату рождения. Первая работа по теории графов, написанная швейцарским математиком Леонардом Эйлером (1707-1783), была опубликована в 1736 году в Трудах Академии наук в Санкт-Петербурге.

Граф - Пара объектов

G = ( X , Г ) ,

где Х - конечное множество ,а Г -конечное подмножество прямого произведения Х*Х . При этом Х называется множеством вершин , а Г - множеством дуг графа G .

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

Если в множестве Г все пары упорядочены, то такой граф называют ориентированным.

Дуга- ребро ориентированного графа.

Вершина Х называется инцидентной ребру G , если ребро соединяет эту вершину с какой-либо другой вершиной.

Подграфом G(V₁, E₁) графа G(V, E) называется граф с множеством вершин V₁ ?V и множеством ребер (дуг) E_?? E, - такими, что каждое ребро (дуга) из E₁ инцидентно (инцидентна) только вершинам из V₁ . Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф).

Мультиграф - это пара (V,E), где V - непустое множество, а E - семейство подмножеств множества V^{2}.

Употребление термина “семейство” вместо “подмножество” означает, что элементы множества V^{2} могут в E повторяться, то есть допускаются кратные рёбра.

Пример мультиграфа показан на рис. 3.3.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

Такой граф называется псевдографом. Его пример приведен на рис. 3.4.

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Различают также ориентированные и смешанные графы.

Пусть V⁽²⁾ - множество упорядоченных пар элементов множества V. Тогда ориентированный граф (или орграф) - это пара (V,А), где V - множество вершин, АV⁽²⁾ - множество ориентированных рёбер, которые называются дугами.

Если пара (v₁,v₂) - дуга, то вершины v₁ и v₂ называются её началом и концом соответственно.

На рисунке дуги отмечаются стрелками, указывающими направление от начала к концу.

Орграф G=(V,E), V={v₁,v₂,v₃,v₄}, E={(v₁,v₂), (v₁,v₄), (v₂,v₃), (v₂,v₄), (v₃,v₄)} представлен графически на рис.3.5.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Ориентированный мультиграф и ориентированный псевдограф определяются аналогично.

Смешанные графы имеют как дуги, так и неориентированные рёбра.

Пример смешанного графа представлен на рис. 3.6.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Ради сокращения речи термин “граф” употребляется вместо терминов “мультиграф”, ”орграф” и др., но подобные случаи либо специально оговариваются, либо ясны из контекста.

Часто каждой дуге графа ставят в соответствие одно или несколько чисел. Такой граф называется взвешенным (или сетью). Пример взвешенного графа представлен на рис. 3.7.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рассмотрим некоторые понятия теории графов.

Пусть v₁,v₂,…,v_n,v_n+1 - произвольная последовательность вершин орграфа.

Цепью называется любая последовательность дуг e₁,e₂,...,e_n, такая, что концевыми вершинами дуги e_i являются вершины v_i и v_i+1, то есть e_i=(v_i,v_i+1) или e_i=(v_i+1,v_i) для i=1,2,…,n.

Цепь, для которой e_i=(v_i,v_i+1) при всех i=1,2,…,n, называется путём.

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

Контуром называется путь, у которого начальная и конечная вершины совпадают.

Цепь, путь, цикл или контур называются простыми, если они не содержат внутри себя циклов.

У графа, изображенного на рис. 3.8.

- дуги (v₂,v₁), (v₂,v₂), (v₃,v₂), (v₃,v₄) образуют цепь, соединяющую вершину v₁ с вершиной v₄;

- дуги (v₂,v₂), (v₂,v₄), (v₄,v₃) образуют путь, соединяющий вершины v₂ и v₃;

- дуги (v₃,v₂), (v₂,v₄), (v₃,v₄) образуют цикл с начальной и конечной вершиной v₃;

- дуги (v₃,v₂), (v₂,v₄), (v₄,v₃) образуют контур с начальной и конечной вершиной v₃;

- цепь (v₂,v₁), (v₃,v₂), (v₃,v₄), (v₄,v₃) с начальной вершиной v₁ и конечной v₃ не является простой, так как содержит внутри себя цикл (v₃,v₄), (v₄,v₃).

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Граф называется связным, если в нем для каждой пары вершин найдётся соединяющая их цепь.

Связный и несвязный граф представлен на рис.3.9.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Любой граф можно рассматривать как некоторую совокупность связных графов. Каждый из этих графов называется компонентом исходного графа.

Несвязный граф, изображённый на рис. 3.9, имеет два компонента.

Множество дуг, исключение которых из графа увеличивает число его компонентов, называется разрезом.

Для связного графа, изображенного на рис. 3.9, разрезом является выделенная дуга e, так как её удаление увеличивает число компонентов до двух.

Пусть G=(V,E), VV, тогда граф, множество вершин которого совпадает с V, а множество дуг включает все дуги множества E с концевыми вершинами в V, называется подграфом графа G, порождённым V.

Пусть EE, тогда граф, для которого множество дуг совпадает с E, а множество вершин включает вершины, инцидентные дугам из E, называется подграфом графа G, порождённым E.

Граф называется полным, если любые две его вершины смежные.

Граф G называется пустым, если в нём нет рёбер.

Граф, который не содержит циклов, называется ациклическим.

Связный неориентированный ациклический граф называется деревом, множество деревьев называется лесом.

Если рёбра, составляющие дерево, заменить ориентированными дугами, то получим ориентированное дерево. Если из контекста ясно, о каком дереве идет речь, то в дальнейшем слово «ориентированное» будем опускать.

Для ориентированного дерева имеет смысл ввести понятие корня. Минимальное по мощности множество вершин ориентированного дерева, из которых существуют пути во все оставшиеся вершины, будем называть множеством корней.

Покрывающим (остовным) деревом графа G называется дерево, являющееся подграфом графа G и содержащее все его вершины.

Если граф G несвязен, то множество, состоящее из основных деревьев каждой компоненты, называется покрывающим (остовным) лесом.

Обобщением графа является гиперграф.

В гиперграфе, в отличие от графа, рёбрами могут быть не только двухэлементные, но и любые подмножества вершин.

Подобные объекты в математике известны давно, однако введение термина “гиперграф” связано с успешным рассмотрением на них ряда важных понятий и методов теории графов.

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

1.1 Теоремы

1. Вершины графа называются смежными , если существует ребро , их соединяющее.

2. Два ребра G₁ и G₂ называются смежными, если существует вершина, инцидентная одновременно G₁ и G₂.

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

4. Конечная последовательность необязательно различных рёбер E₁,E₂,...E_n называется маршрутом длины n, если существует последовательность V₁, V₂, ... V_n необязательно различных вершин, таких, что

E_i = (V_i-1,V_i ).

1. Если совпадают, то маршрут замкнутый.

2. Маршрут, в котором все рёбра попарно различны, называется цепью.

3. Замкнутый маршрут, все рёбра которого различны, называется циклом. Если все вершины цепи или цикла различны, то такая цепь или цикл называются простыми.

4. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом.

5. Степень вершины - число ребер, которым инцидентна вершина V, обозначается D(V).

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

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

E2 E4 E5

E3

E1 E7

E6

E8

E9

Рис. 1«Пример неориентированного графа»

Матрицей весов называется квадратная матрица размерности nхn (n- количество вершин), элемент которой стоящий в i строке и j столбце определяется по правилу:

Матрица смежности - это булева матрица (иногда ее называют двоичной или битовой) порядка n: R=||r[ij]||, в которой строкам и столбцам поставлены в соответствие вершины графа G, и r[ij]=1,если вершины vi, vjV смежные, и r[ij]=0 в противном случае. Так для неориентированного графа, представленного на рис. 1, матрица смежности имеет вид таблицы 1.

Таблица 1. «Матрица смежности»

V1	V2	V3	V4	V5	V6	V7
0	1	1	0	0	0	1	V1
1	0	1	0	0	0	0	V2
1	1	1	0	1	0	1	V3
0	0	0	0	0	0	0	V4
0	0	1	0	0	0	1	V5
0	0	0	0	0	0	1	V6
1	0	1	0	1	1	0	V7

Матрица инцидентности - это также булева матрица Q=||q[ij]|| размера nxm, в которой строкам поставлены в соответствие вершины графа, а столбцам - ребра. Если граф - неориентированный ,то матрица инцидентности такого графа является булевой матрицей, в которой q[ij]=1, если вершина vi инцидентна ребру еj, и q[ij]=0 в противном случае. Так для неориентированного графа, представленного на рис. 1, матрица инцидентности имеет вид, как в таблице 2.

Таблица 2. «Матрица инцидентности»

Е1	Е2	Е3	Е4	Е5	Е6	Е7	Е8	Е9
1	1	1	0	0	0	0	0	0	V1
0	1	0	1	0	0	0	0	0	V2
0	0	1	1	1	1	1	0	0	V3
0	0	0	0	0	0	0	0	0	V4
0	0	0	0	0	0	1	1	0	V5
0	0	0	0	0	0	0	0	1	V6
1	0	0	0	0	1	0	1	1	V7

Если граф G является разреженным, то есть число ребер m значительно меньше величины (число ребер полного графа

),

то эффективным представлением графа является список его ребер, задаваемый парами вершин. Для этого формируют два массива: (,…, ) и (,…, ). Каждый элемент в массиве есть метка вершины, а i-e ребро графа выходит из вершины . Например неориентированный граф, представленный на рис. 1 будет представлен следующими двумя массивами:

g = (1, 1, 1, 2, 2, 3, 3, 3, 3, 5, 5, 6, 7)

h = (2, 3, 7, 1, 3, 3, 1, 5, 7, 3, 7, 7, 6)

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

На практике часто возникают задачи в отыскании сильно связных подграфов (сильно связных компонентов) ориентированного графа.

Для определения сильно связных подграфов введем понятие следующих матриц:

- матрица достижимости R=||r_ij||;

- матрица контрдостижимости Q=||q_ij||;

- матрица взаимодостижимости H=||h_ij||.

Размер всех матриц nn, где n - число вершин графа, элементы матриц определяются следующим образом:

r_ij=1, если вершина j достижима из вершины i,

r_ij=0, если вершина j не достижима из вершины i,

q_ij=1, если вершина i достижима из вершины j,

q_ij=0, если вершина i не достижима из вершины j,

h_ij=1, если вершина j достижима из вершины i и вершина i достижима из вершины j, то есть если r_ij=1 и q_ij=1.

h_ij=0, если вершина j не достижима из вершины i или вершина i не достижима из вершины j, то есть если r_ij=0 или q_ij=0.

Отношение взаимодостижимости, определяемое матрицей H=||h_ij||, разбивает все множество вершин V орграфа G на классы взаимодостижимых вершин. Каждый такой класс порождает подграф, который называется сильно связным. Орграф и его сильно связные компоненты показаны на рис. 3.18.

Для алгоритмизации процесса выделения сильно связных подграфов выполним следующие действия:

1. Используя технику поиска в глубину или в ширину, найдем матрицу достижимости R.

2. Так как r_ij=q_ij, то есть R=Q^T и Q=R^T, то, транспонируя матрицу R, получим матрицу контрдостижимости Q.

3. Из матриц R и Q получим матрицу взаимодостижимости H.

4. Анализируя матрицу H, выделяем классы взаимодостижимых вершин и строим сильно связные подграфы исходного орграфа.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Для орграфа, изображенного на рис. 3.18, матрица достижимости R, контрдостижимости Q и взаимодостижимости H представлены в табл.3.5 - 3.7 соответственно.

Таблица 3.5.

Матрица достижимости орграфа, изображенного на рис. 3.18

	v1	v2	v3	v4	v5	v6	v7
v1	1	1	1	1	0	0	1
v2	1	1	1	1	0	0	1
v3	1	1	1	1	0	0	1
v4	1	1	1	1	0	0	1
v5	1	1	1	1	1	1	1
v6	1	1	1	1	1	1	1
v7	0	0	0	0	0	0	1

Таблица 3.6.

Матрица контрдостижимости орграфа, изображенного на рис. 3.18

	v1	v2	v3	v4	v5	v6	v7
v1	1	1	1	1	1	1	0
v2	1	1	1	1	1	1	0
v3	1	1	1	1	1	1	0
v4	1	1	1	1	1	1	0
v5	0	0	0	0	1	1	0
v6	0	0	0	0	1	1	0
v7	1	1	1	1	1	1	1

Таблица 3.7.

Матрица взаимодостижимости орграфа, изображенного на рис. 3.18

	v1	v2	v3	v4	v5	v6	v7
v1	1	1	1	1	0	0	0
v2	1	1	1	1	0	0	0
v3	1	1	1	1	0	0	0
v4	1	1	1	1	0	0	0
v5	0	0	0	0	1	1	0
v6	0	0	0	0	1	1	0
v7	0	0	0	0	0	0	1

Анализируя матрицу взаимодостижимости, находим следующие классы взаимодостижимых вершин: {v₁,v₂,v₃,v₄}, {v₅,v₆}, {v₇}. Сильносвязные компоненты орграфа представлены выше на рис. 3.18.

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

Итак, чтобы перейти к реализации данного алгоритма, необходимо разделить каждую фазу, обозначенную выше, на определенное количество шагов:

Две вершины A,B ориентированного графа называются сильно, связанными если есть пути из A в B и из B в A. Отношение сильной связанности транцитивно, то есть если A сильно связана с B, а B сильно связана с C, то A сильно связана с C.

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

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

Граф задается массивом связей, выходящих из каждой вершины.

Для выделения сильно связных компонент используют два поиска в глубину.

1-ый раз на исходном графе, 2-ой на транспонированном (исходный граф, в котором обращены все разрешенные направления).

Strongly - Connected - Components (G)

1. С помощью DFS(G), для каждой вершины u, найти время окончания обработки - f[u]

2. Построить G^T - транспонированный граф

3. Вызвать DFS(G^T), при этом в его внешнем цикле перебирать вершины в порядке убывания величины f[u] (вычисленной в 1-ой строке)

4. Сильно связными компонентами будут деревья поиска, построенные на шаге 3.

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

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

Теперь требуется протестировать программу примером, для того чтобы выявить ошибки и исправить их если они допущены.

1.) Вводим число вершин в графе.

2.) Вводим начальную вершину, из которой будет выходить ребро.

3.) Вводим вершину, куда ведет связь.

· На выходе мы получаем сильносвязный компонент ориентированного графа.

P.S Граф задается массивом связей, выходящих из каждой вершины.

Для упрощения ввода, вершины считаются пронумерованными от 0 и далее. Для работы с вершинами, которые задаются, например, строковыми именами, следует обратить внимание на топологическую сортировку.



Входные данные: Выходные данные:

5 1 1

1 1 2 1

2 2 3 0 1

1 0 4 2

1 4 3 2

1 3

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

Листинг программы рабочий. Преобразования проходят успешно. Ошибок в коде нет. Вносить коррективы не нужно.

Заключение

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

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

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

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

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

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

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

Приложение

Листинг программы

#include <stdio.h>

int N; // Количество вершин в графе

#define MAX_NODES 100 // Максимальное количество вершин

#define MAX_EDGES 10 // Максимальное количество ребер, выходящих из одной вершины

int edges[MAX_NODES][MAX_EDGES]; // Граф, в котором ищем сильно связные компоненты

int edges_c[MAX_NODES];

int edgesT[MAX_NODES][MAX_EDGES]; // Транспонированый граф

int edgesT_c[MAX_NODES];

int state[MAX_NODES]; // Используется в поиске для того, чтобы отмечать посещенные вершины

int f[MAX_NODES],last_f=0; // Список предварительной расстановки вершин

int c=1; // Номер компоненты (увеличиваем его, когда находим новую)

void dfs(int node){

state[node]=1;

for(int i=0; i<edges_c[node]; i++) // Самый обыкновенный поиск в глубину.

if (state[edges[node][i]]==0) // Проходим по всем непосещенным вершинам,

dfs(edges[node][i]); // заходя в каждую

f[last_f++]=node; // Предварительная расстановка вершин в списке.

}

void dfsT(int node){

state[node]=1;

for(int i=0; i<edgesT_c[node]; i++) // Самый обыкновенный поиск в глубину в транспонированном графе.

if (state[edgesT[node][i]]==0) // Проходим по всем непосещенным вершинам,

dfsT(edgesT[node][i]); // заходя в каждую

printf("%d %d\n",node,c);

}

void scc(){ // Strongly Connected Components - функция выделения сильно связных компонент графа

int i;

for(i=0; i<N; i++) state[i]=0;

for(i=0; i<N; i++) // 1-ый поиск в глубину

if (state[i]++==0) // ...

dfs(i); // Предварительная расстановка вершин.

for(i=0; i<N; i++) state[i]=0;

for(last_f--; last_f>=0; last_f--) // 2-ой поиск в глубину

if (state[f[last_f]]==0){ // ...

dfsT(f[last_f]); // Окончательное выделение сильно связных компонент

c++; // увеличиваем номер следующей компоненты

}

}

int main(){

int i;

scanf("%d",&N);

for(i=0; i<N; i++) edges_c[i]=edgesT_c[i]=0;

for(i=0; i<N; i++){

int j;

scanf("%d",&edges_c[i]);

for(j=0; j<edges_c[i]; j++){

int to;

scanf("%d",&to);

edges[i][j]=to; // Построение исходного графа

edgesT[to][edgesT_c[to]++]=i; // Построение транспонированного графа

}

}

scc(); // Найти и вывести сильно связные компоненты

return 0;

}

Топологическая сортировка

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define M 15

#define N 1000

#define NE 100

#define P 10007

#define MAX_LINE_LENGTH 100

typedef struct

{

int to;

int w;

} edge;

edge a[N][NE];

int ne[N];

int n = 0;

int v[N];

int c;

int hash_table[P];

char term[N][M];

int count;

int

getid (char *s)

{

unsigned long i, h1 = 0, h2 = 0;

for (i = 0; s[i]; i++)

{

h1 *= 13;

h1 += s[i] % 13;

h2 *= 17;

h2 += s[i] % 17;

}

h1 %= P;

h2 %= P - 1;

h2++;

while (hash_table[h1] != -1)

{

if (strcmp (term[hash_table[h1]], s) == 0) return hash_table[h1];

h1 += h2;

h1 %= P;

}

hash_table[h1] = n;

strcpy (term[n], s);

return n++;

}

void

dfs (int root)

{

int i;

v[root] = c;

for (i = 0; i < ne[root]; i++)

if (v[a[root][i].to] == 0)

dfs (a[root][i].to);

printf ("%s\n", term[root]);

}

int

main ()

{

int i, j, id1, id2, m;

int w;

char term1[M];

char term2[M];

char in[MAX_LINE_LENGTH];

for (i = 0; i < P; i++) hash_table[i] = -1;

for (i = 0; i < N; i++) ne[i] = 0;

while (fgets (in, MAX_LINE_LENGTH, stdin) != NULL)

{

if(sscanf (in, "%s%s", term1, term2) == 2)

{

id1 = getid (term1);

id2 = getid (term2);

a[id2][ne[id2]].to = id1;

a[id2][ne[id2]].w = w;

ne[id2]++;

}

}

c = 0;

for (i = 0; i < n; i++) v[i] = 0;

for (i = 0; i < n; i++) if (v[i] == 0)

{

c++;

dfs (i);

}

return 0;

}

Размещено на Allbest.ru