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

 

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

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

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

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








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

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




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

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

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

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

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

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




БЕЛГОРОД 2012

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


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


Содержание


Введение

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

.1 Теоремы

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

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

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

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

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

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

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

Заключение

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

Приложение



Введение


Язык С/C++

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

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

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

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

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

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

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

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

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

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

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

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

·передачу параметров <#"justify">Вот некоторые особенности других языков программирования, которых не имеет Си:

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

·поддержка объектно-ориентированного программирования <#"justify">·функции, не возвращающие значение (с типом void) и указатели, не имеющие типа (с типом void *);

·функции, возвращающие объединения <#"justify">граф программа алгоритм

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


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

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

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

= ( X , Г ) ,


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

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

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

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

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

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

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

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

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



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

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

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


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

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

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

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

Орграф G=(V,E), V={v1,v2,v3,v4}, E={(v1,v2), (v1,v4), (v2,v3), (v2,v4), (v3,v4)} представлен графически на рис.3.5.



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

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

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



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

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



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

Пусть v1,v2,…,vn,vn+1 - произвольная последовательность вершин орграфа.

Цепью называется любая последовательность дуг e1,e2,...,en, такая, что концевыми вершинами дуги ei являются вершины vi и vi+1, то есть ei=(vi,vi+1) или ei=(vi+1,vi) для i=1,2,…,n.

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

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

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

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

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

дуги (v2,v1), (v2,v2), (v3,v2), (v3,v4) образуют цепь, соединяющую вершину v1 с вершиной v4;

дуги (v2,v2), (v2,v4), (v4,v3) образуют путь, соединяющий вершины v2 и v3;

дуги (v3,v2), (v2,v4), (v3,v4) образуют цикл с начальной и конечной вершиной v3;

дуги (v3,v2), (v2,v4), (v4,v3) образуют контур с начальной и конечной вершиной v3;

цепь (v2,v1), (v3,v2), (v3,v4), (v4,v3) с начальной вершиной v1 и конечной v3 не является простой, так как содержит внутри себя цикл (v3,v4), (v4,v3).



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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


.1 Теоремы


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

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

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

.Конечная последовательность необязательно различных рёбер E1,E2,...En называется маршрутом длины n, если существует последовательность V1, V2, ... Vn необязательно различных вершин, таких, что


Ei = (Vi-1,Vi ).


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

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

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

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

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


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


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



E2E4E5


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. «Матрица смежности»

V1V2V3V4V5V6V70110001V11010000V21110101V30000000V40010001V50000001V61010110V7

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


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

Е1Е2Е3Е4Е5Е6Е7Е8Е9111000000V1010100000V2001111100V3000000000V4000000110V5000000001V6100001011V7

Если граф 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=||rij||;

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

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

Размер всех матриц 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 на классы взаимодостижимых вершин. Каждый такой класс порождает подграф, который называется сильно связным. Орграф и его сильно связные компоненты показаны на рис. 3.18.

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

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

. Так как rij=qij, то есть R=QT и Q=RT, то, транспонируя матрицу R, получим матрицу контрдостижимости Q.

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

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



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


Таблица 3.5.

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

v1v2v3v4v5v6v7v11111001v21111001v31111001v41111001v51111111v61111111v70000001

Таблица 3.6.

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

v1v2v3v4v5v6v7v11111110v21111110v31111110v41111110v50000110v60000110v71111111

Таблица 3.7.

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

v1v2v3v4v5v6v7v11111000v21111000v31111000v41111000v50000110v60000110v70000001

Анализируя матрицу взаимодостижимости, находим следующие классы взаимодостижимых вершин: {v1,v2,v3,v4}, {v5,v6}, {v7}. Сильносвязные компоненты орграфа представлены выше на рис. 3.18.


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


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

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

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

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

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

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

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

- Connected - Components (G)


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

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

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

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

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


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


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

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

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

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

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

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

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



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

1 1

1 2 1

2 3 0 1

0 4 2

4 3 2

3


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


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


Заключение


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


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


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

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

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

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

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


Приложение


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


#include <stdio.h>N; // Количество вершин в графе

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

#define MAX_EDGES 10 // Максимальное количество ребер, выходящих из одной вершиныedges[MAX_NODES][MAX_EDGES]; // Граф, в котором ищем сильно связные компоненты

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

int state[MAX_NODES]; // Используется в поиске для того, чтобы отмечать посещенные вершиныf[MAX_NODES],last_f=0; // Список предварительной расстановки вершинc=1; // Номер компоненты (увеличиваем его, когда находим новую)

void dfs(int node){[node]=1;

for(int i=0; i<edges_c[node]; i++) // Самый обыкновенный поиск в глубину.(state[edges[node][i]]==0) // Проходим по всем непосещенным вершинам,(edges[node][i]); // заходя в каждую[last_f++]=node; // Предварительная расстановка вершин в списке.

}dfsT(int node){[node]=1;

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

dfsT(edgesT[node][i]); // заходя в каждую("%d %d\n",node,c);

}scc(){ // Strongly Connected Components - функция выделения сильно связных компонент графаi;(i=0; i<N; i++) state[i]=0;(i=0; i<N; i++) // 1-ый поиск в глубину(state[i]++==0) // ...

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

for(i=0; i<N; i++) state[i]=0;(last_f--; last_f>=0; last_f--) // 2-ой поиск в глубину(state[f[last_f]]==0){ // ...

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

}

}main(){i;("%d",&N);(i=0; i<N; i++) edges_c[i]=edgesT_c[i]=0;(i=0; i<N; i++){j;("%d",&edges_c[i]);(j=0; j<edges_c[i]; j++){to;("%d",&to);

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

}

}(); // Найти и вывести сильно связные компоненты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 100struct

{to;w;

} edge;a[N][NE];ne[N];n = 0;v[N];c;hash_table[P];term[N][M];count;(char *s)

{long i, h1 = 0, h2 = 0;(i = 0; s[i]; i++)

{*= 13;+= s[i] % 13;*= 17;+= s[i] % 17;

}%= P;%= P - 1;++;(hash_table[h1] != -1)

{(strcmp (term[hash_table[h1]], s) == 0) return hash_table[h1];+= h2;%= P;

}_table[h1] = n;(term[n], s);n++;

}(int root)

{i;[root] = c;(i = 0; i < ne[root]; i++)(v[a[root][i].to] == 0)(a[root][i].to);("%s\n", term[root]);

}()

{i, j, id1, id2, m;w;term1[M];term2[M];in[MAX_LINE_LENGTH];(i = 0; i < P; i++) hash_table[i] = -1;(i = 0; i < N; i++) ne[i] = 0;(fgets (in, MAX_LINE_LENGTH, stdin) != NULL)

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

{= getid (term1);= getid (term2);[id2][ne[id2]].to = id1;[id2][ne[id2]].w = w;[id2]++;

}

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

{++;(i);

}0;

}


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

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2018 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ