Медиана графа
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
Графом (неориентированным графом) G(V,E) называется совокупность двух множеств, где V – конечное непустое множество элементов, называемых вершинами, а E – множество неупорядоченных пар различных элементов множества V (эти пары называются ребрами). Граф, состоящий из одной вершины, называется тривиальным.
Говорят, что ребро e = (u, v) соединяет вершины u и v. Ребро e и вершина u (а также e и v) называются инцидентными, а вершины u и v смежными. Ребра инцидентные одной и той же вершине также называются смежными.
Расстояние между двумя вершинами – это длина кратчайшего пути, соединяющего эти вершины.
Обход графа – это некоторое систематическое прохождение его вершин (и/или ребер). Обходя граф, мы двигаемся по ребрам (дугам) и проходим все вершины. При этом можно получить много информации, которая необходима для дальнейшей обработки графа, поэтому обход графа является основой многих алгоритмов исследования структуры графа.
Цель:
Найти медиану графа, т.е. такую его вершину, что сумма его расстояний от неё до остальных минимальна.
Данная цель достигается решением следующих задач:
- выбор алгоритма
- выбор метода решения
- разработка на языке программирования С
- проектирование тестов
ВЫБОР АЛГОРИТМА
Постановка задачи
Разработанная программа находит медиану в заданном графе с количеством вершин n<= 10.
В программе используются следующие определения . Граф – это пара (V, E), где V – конечное непустое множество вершин, а E – множество неупорядоченных пар <u, v> вершин из V, называемых ребрами. Рассматривается класс графов без петель, т.е. ребер, в которых u = v.
Путь, соединяющий вершины u и v, - это последовательность вершин v0, v1, . . . , vk(k>= 0) такая, что v = u, v = v и для любого i (0 <= i<= k-1) вершины vi и vi+1 соединены ребром.
Длина пути v0, v1, … , vk равна k (количеству ребер). Путь замкнут, если v0 = vk. Путь называется простым, если все вершины различны. Расстояние – это длина кратчайшего пути между вершинами. Граф связан, если для любых пар вершин <u, v> существует соединяющий их путь. Медианой графа называют такую вершину, что сумма расстояний от нее до остальных минимальна.
Решаемая задача иллюстрируется на рис. 2.1.
Рис. 2.1
Обращение к программе
Вызов программы происходит в программной среде MS-DOS, так как язык программирования, на котором написана программа (TURBO C) позволяет писать программы только под эту операционную систему. Файл, реализующий данную программу, называется zulka.exe.
Входные данные
Входные данные программы представляют собой граф. Граф представляется в виде перечня ребер, перед которым указывается количество вершин. Каждое ребро задается парой номеров вершин. Вершины нумеруются от 0 до n-1, где n – количество вершин графа (n<=20). Ребра можно задавать в произвольном порядке. Все числа разделяются пробелами и/или переводом строки (клавиша <Enter>).
При вводе данных с клавиатуры после ввода всех данных нажимается <Ctrl-Z> (обозначает конец файла) и <Enter>.
Например, граф, показанный на рис. 2.1, можно ввести с клавиатуры следующим образом:
5
0 1
0 2
0 3
1 4
1 3
2 3
3 4
<Ctrl-Z><Enter>
Другой вариант ввода:
0 1 0 2 0 3 1 4 1 3 2 3 3 4<Ctrl-Z><Enter>
Выходные данные
Результатом работы программы является текст, содержащий матрицу смежности и матрицу весов входного графа, и последовательность сообщений, выводимых на экран дисплея. Возможные сообщения приведены в разделе 2.5.
Результаты обработки графа, показанного на рис. 2.1, приведены на рис. 2.2. Сделано предупреждение, т.к. ребро 1-4 введено дважды.
Введите граф (количество вершин от 1 до 20):
5
Введите последовательность ребер:
0 1
0 2
0 3
1 4
1 3
2 3
3 4
4 1 ^Z
Матрица весов:
0 |
0 |
1 |
2 |
3 |
4 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
2 |
1 |
0 |
0 |
1 |
0 |
3 |
1 |
1 |
1 |
0 |
1 |
4 |
0 |
1 |
0 |
1 |
0 |
Предупреждение: было дублирование ребер (игнорировалось).
Медиана – 3, расстояние – 4.
Рис. 2.2. Пример результата работы программы
Сообщения
В угловых скобках указаны названия вставляемых в сообщения величин.
Информационные сообщения
- Медиана - <вершина>, расстояние - <длина>;
- Введите граф (количество вершин от 1 до 20);
- Введите последовательность ребер.
При вводе с клавиатуры необходимо ввести целое число, затем вводить пары целых чисел – номера вершин графа, по правилам, описанным в 2.3.
Сообщения об ошибках
- Ошибка: нет входных данных;
- Ошибка: количество вершин должно быть от 1 до 20.
- Ошибка: ребро должно содержать две вершины.
- Ошибка: недопустимое количество вершин (1<=n<=20)
- Предупреждение: было дублирование ребер (игнорировалось).
РАЗРАБОТКА ПРОГРАММЫ НА ЯЗЫКЕ ПРОГРАММИРОВАНИЯ C
Метод решения задачи
У графа длина (вес) пути определяется как сумма длин его ребер. Расстояние D[i][j] между вершинами i и j – длина кратчайшего пути между ними. Считают, что расстояние от вершины до нее самой равно нулю: D[i][i] = 0. У не взвешенного графа вес ребра равен 1; длина пути и расстояние измеряются числом ребер.
Кратчайший путь в графе от заданной вершины до одной или до всех вершин можно найти методом обхода в ширину. Кратчайшие пути и расстояния между всеми вершинами быстрее определяются через матрицу расстояний или алгоритм Флойда.
Обозначим D(k) [i][j] – длина кратчайшего пути от вершины I к вершине j через вершины из множества {1, … , k}.
Тогда без промежуточных вершин:
D(-1)[i][j] = W[i][j]
где W – матрица весов с бесконечными весами отсутствующих ребер.
Если кратчайший путь от вершины i к вершине j через множество вершин {1, …, k-1, k} не содержит вершины k, то
D(k)[i][j] = D(k-1)[i][j],
иначе его можно разделить на два пути, проходящих через {1, …, k-1}: от вершины i до вершины k и от вершины k до вершины j , причем:
D(k)[i][j] = D(k-1)[i][k] + D(k-1)[k][j].
отсюда:
D(k)[i][j] = min (D(k-1)[i][j], D(k-1)[i][k] + D(k-1)[k][j])
Расстояние между вершинами i и j равно:
D[i][j] = D(n-1)[i][j].
Отсюда получен алгоритм Флойда (1) для вычисления расстояний D[i][j] между всеми парами вершин графа.
Алгоритм 1. Вычисления расстояний D[i][j] между всеми парами вершин графа
D = W; /* Матрица весов (отсутствие ребра -0) */
for (i=0; i<n; i++) D[i][i] = 0; /* если D[i][i] бесконечны */
for (k=0; k<n; k++)
for (i=0; i<n; i++)
if (D[i][k] != 0)
for (j=0; j<n; j++)
D[i][j] = min (D[i][j], D[i][k] + D[k][j]);
Структура программы
Структура программы показана на рис. 1
Рис. 1. Модульная структура программы
Программа состоит из трех функционально-прочных модулей: glav – главная программа, vv_m_sm – ввод графа, obrab – вывод матрицы расстояний.
Сопряжения модулей программы описаны в таб. 3.1. Все данные между модулями передаются только в виде параметров, глобальных переменных в программе нет. Модуль main сцеплен с модулями vv_m_sm и obrab по формату.
Таблица 1
Сопряжения модулей
№ |
Входные данные |
Выходные данные | |
1 |
Количество вершин. |
матрица смежности, код ошибки. | |
2 |
Номер сообщения |
- | |
3 |
Количество вершин, матрица смежности. |
Матрица расстояний | |
Все модули транслировались отдельно. Модули obrab, vv_m_sm помещены в проект zulka.prj, и для их использования требуется включить в программу созданный в курсовой работе файл заголовков graf.h командой
#include "graf.h"
Для записи алгоритмов использован псевдокод на базе языка Си.
Описание модулей
1) glav– главный модуль
ОБРАЩЕНИЕ ИЗ MSDOS: zulka
ЗАГОЛОВОК: void main ( )
ФУНКЦИЯ: Ввод графа, вычисление медианы графа, вывод результата.
ВХОДНЫЕ ДАННЫЕ: Нет.
ВЫХОДНЫЕ ДАННЫЕ: z – медиана, mdl - расстояние.
ЗНАЧЕНИЕ: Нет.
РАБОЧИЕ ДАННЫЕ:
g– матрица смежности графа;
n- количество вершин;
d – матрица расстояний;
i, j– номера вершин;
dl– сумма расстояний;
z – вычисляемая вершина;
mdl – признак не связанности;
kz- код завершения подпрограммы;
Алгоритм модуля main
puts (“\n Задача: Найти медиану графа , т. е. такую его вершину, что сумма расстояний от нее до остальных вершин минимальна \n”);
puts (“\nВведите граф (количество вершин от 1 до 20): \n”);
Ввод n;
if(n>NMAX || n< 1)
{puts (“\nОшибка: количество вершин должно быть от 1 до: \n”);
puts (“\nРешение прекращено \n”);
}
else
kz=vv_m_sm(n,g); /* ввод графа */
if(kz>1)
{Вывод сообщения kz;
puts (“\nРешение прекращено \n”);
}
else
{if(kz==1)
puts (“\nПредупреждение: было дублирование ребер \n”);
obrab(n,g,d); /* Вызов матрицы расстояний */
for(i = 0; i< n; i++)
{ dl=0;
for(j = 0; j < n; j++)
{ if(d[i][j]!=0)
dl = dl + d[i][j];
}
if(dl < mdl)
{ mdl = dl;
z = i;
}
}
printf("\n Медиана - %d, расстояние- %d\n",z,mdl); /* Вывод медианы */
printf (“\nРешение прекращено \n”);
}
getch();
}
2) vv_m_sm – ввод графа
ЗАГОЛОВОК: void vv_m_sm (int n, int g[][NMAX])
ФУНКЦИЯ: Ввод графа в виде перечня ребер, перед которым указывается количество вершин n, и его преобразование в матрицу смежности g. NMAX – максимальное количество вершин.
ВХОДНЫЕ ДАННЫЕ: n – количество вершин.
ВЫХОДНЫЕ ДАННЫЕ:
n – количество вершин;
g – матрица смежности графа.
ЗНАЧЕНИЕ:
- ввод завершен без ошибок;
- ввод завершен, но
было повторение ребер (
- ошибка: входной файл пуст (ввод прекращен);
- ошибка: недопустимый номер вершины (ввод прекращен);
- ошибка: только одна
вершина в ребре (ввод
РАБОЧИЕ ДАННЫЕ:
i - номер вершины, с которой начинается вводимое ребро;
j - номер вершины, в которой заканчивается вводимое ребро;
pr- было повторение ребер.
Алгоритм модуля vv_m_sm
if (конец входного файла)
return 2; /* входной файл пуст */
pr=0;
puts ( “\nВведите последовательность графа, в конце <Ctrl+Z> \n”);
обнуление матрицы g;
while (не конец входного файла) ввод i;ввод j;
if (конец входного файла)return 5; /* только одна вершина в ребре */
{if (i не допустимо) return 4; /*недопустимый номер вершины*/
if (было ребро i-j) pr = 1; /* повторение ребер */
g[i][j]=g[j][i] = 1;
}
return pr; /* 0 - успех или 1 - было повторение ребер */
3) obrab – вывод матрицы расстояний
ЗАГОЛОВОК: void obrab (int n, int g[][NMAX], int d[][NMAX])
ФУНКЦИЯ: Вывод матрицы расстояний d с количеством вершин n.
ВХОДНЫЕ ДАННЫЕ:
n – количество вершин;
g – матрица смежности графа
ВЫХОДНЫЕ ДАННЫЕ: матрицы расстояний
ЗНАЧЕНИЕ: Нет.
РАБОЧИЕ ДАННЫЕ:
i - номер вершины, с которой начинается вводимое ребро;
j - номер вершины, в которой заканчивается вводимое ребро;
k – множество вершин.
Алгоритм модуля obrab
for(i = 0; i< n; i++)
for(j = 0; j < n; j++)
d[i][j] = g[i][j];
for(i = 0; i< n; i++)
d[i][i] = 0;
for(k = 0; k < n; k++)
for(i = 0; i< n; i++)
if(d[i][k] != 0)
for(j = 0; j < n; j++)
if(d[i][k] + d[k][j]< d[i][j])
d[i][j] = d[i][k] + d[k][j];
puts ("\nМатрица расстояний \n"); /* вывод матрицы расстояний*/
for(i=0;i<n;i++)
printf("%2.1d ",i);
printf("\n┌");
for(i=0;i<7;i++)
printf("─");
for(j=0;j<n;j++)
{printf("\n%d:і",j);
for(i=0;i<n;i++)
printf("%2.1d ",d[i][j]);
}
}
ОТЛАДКА ПРОГРАММЫ
План отладки
Трудность отладки данной программы состоит в том, что она имеет несколько громоздких модулей, работу которых совместно очень трудно проверить. Необходимо проверить каждый модуль в отдельности, что и применялось при отладке. Отладка производилась по следующим пунктам:
- Тестирование модуля ввода графа, при этом создавалась специальная программа, которая выводила матрицу смежности.
- Тестирование модуля обработки графа совместно с функцией ввода и главной функцией.
- Совместное тестирование всех модулей программы.
ПРОЕКТИРОВАНИЕ ТЕСТОВ
Тесты черного ящика
Тестирование чёрного ящика — стратегия (метод) тестирования функционального поведения объекта (программы, системы) с точки зрения внешнего мира, при котором не используется знание о внутреннем устройстве тестируемого объекта. Под стратегией понимаются систематические методы отбора и создания тестов для тестового набора.
Для проектирования тестов программы методами черного ящика с помощью эквивалентного разбиения входных/выходных данных на области (классы) эквивалентности составлен список ситуаций, каждая из которых должна создаваться хотя бы одним тестом. Тестовые ситуации приведены в табл. 2, в скобках указаны их номера.
Таблица 2
Области входных/выходных данных тестов программы
Входное/выходное условие (значение) |
«Правильные» классы эквивалентности |
«Неправильные» классы эквивалентности |
Количество вершин n |
1… NMAX (1) |
<1 (2) , >NMAX (3) |
Количество вершин в ребре |
2 (4) |
< 2 (5),> 2 (6) |
Номер вершины |
О..n-l (7) |
<0 (8), >n-1 (9) |
Сообщения программы |
1 (10), 2 (11), 6 (12), 9(13) |
3 (14), 4(15), 5(16), 7(17), 8 (18), 10(19) |
Входные данные |
существуют (20) |
не существуют (21) |
Выходные данные |
существуют (22), |
не существует (23) |
Для создания перечисленных тестовых ситуаций разработаны тесты, представленные в табл. 3. Входные и выходные данные тестов по возможности выбирались ближе к границам классов эквивалентности.
Таблица 3
Тесты черного ящика для отладки программы
№ |
Вход |
Выход |
Основные ситуации |
1 |
n =0 |
Сообщения: 1, 2, 3, 7 |
2, 10, 11, 14, 17, 20, 23 |
2 |
n =NMAX+1 |
Сообщения: 1, 2, 3, 7 |
3, 10, 11, 14, 17, 20, 23 |
3 |
n =5 Ребра: 0-1 1-0 0-2 0-3 1-3 1-4 2-3 3-4 |
Медиана-3, расстояние - 4 Сообщения: 1, 2, 6, 8, 9 |
1, 4, 7, 10, 11, 12, 18, 13, 20, 22 |
4 |
n =5 Ребра: -0 0-2 0- 0-3 |
Сообщения: 1, 2, 6, 5, 7 |
5, 10, 11, 12, 16, 17, 20, 23 |
5 |
n =5 Ребра: -0 0-3-1 0-4 |
Сообщения: 1, 2, 6, 5,7 |
5, 6, 10, 11, 12, 16, 17, 20, 23 |
6 |
n =5 Ребра: <Ctrl+Z> |
Сообщения: 1, 2, 6, 10, 7 |
10, 11, 12, 19, 17, 20, 23 |
7 |
n =5 Ребра: 1-6 2-3 4-4 |
Сообщения: 1, 2, 6, 4, 7 |
9, 10, 11,12, 15, 17, 20, 23 |
8 |
n =5 Ребра: (-1)-3 1-3 3-2 0-2 2-4 |
Сообщения: 1, 2, 6, 4, 7 |
8, 10, 11, 12, 15, 17, 20, 23 |
9 |
n =5 Ребра: (-1)-3 7-(-2) 3-2 3-4 3-5 |
Сообщения: 1, 2, 6, 4, 7 |
8, 9, 10, 11, 12, 15, 17, 20, 23 |
10 |
n =5 Ребра: 0-1-2 0-2 2-1 2-3 |
Сообщения: 1, 2, 6, 5, 7 |
6, 10, 11, 12, 16, 17, 20, 23 |
11 |
n =5 Ребра: 0-1 0-2 0-3 1-3 1-4 2-3 3-4 |
Медиана-3, расстояние - 4 Сообщения: 1, 2, 6, 9 |
1, 4, 7, 10, 11, 12, 18, 13, 20, 22 |
12 |
n =5 Ребра: 0-1 0-2 0-3 1-3 1-4 2-3 |
Медиана-3, расстояние - 4 Сообщения: 1, 2, 6, 9 |
1, 4, 7, 10, 11, 12, 18, 13, 20, 22 |
В ребрах вершины обозначаются через тире для наглядности.
Тесты белого ящика.
Тесты белого ящика — тестирование кода на предмет логики работы программы и корректности её работы с точки зрения компилятора того языка на котором она писалась.
Техника тестирования по принципу Белого ящика, позволяет проверить внутреннюю структуру программы. Исходя из этой стратегии тестировщик получает тестовые данные путем анализа логики работы программы.
Таблица 4
Комбинаторное покрытие условий тестами черного ящика
Модуль |
Элементарное условие |
Номера тестов | |
Истина |
Ложь | ||
main |
n<1 |
1 |
2, 3, 4 и др. |
main |
n>NMAX |
2 |
1, 3, 4 и др. |
main |
kz>1 |
4, 5, 7, 8, 9, 10 |
3, 11, 12 |
main |
kz == 4 |
7, 8, 9 |
3, 11, 12 |
main |
kz == 5 |
4, 5, 6, 10 |
3, 7, 8, 9 |
main |
kz== 1 |
3 |
11 |
main |
i< n |
3, 7, 8, 9, 11, 12 |
9 |
main |
j < n |
3, 4, 5, 8, 11, 12 |
7, 9 |
main |
dl < mdl |
3, 7, 11, 12 |
1, 2, 4 и др. |
vv_m_sm |
i<n |
3, 7, 8, 9, 11, 12 |
9 |
vv_m_sm |
j<n |
3, 4, 5, 8, 11, 12 |
7, 9 |
vv_m_sm |
i ==j |
7 |
3, 4, 5 и др. |
vv_m_sm |
while(scanf(“%d%d”,&i,&j)==2) |
3, 11, 12 |
4, 5, 6 и др. |
vv_m_sm |
i< 0 |
8, 9 |
3, 7, 11 и др. |
vv_m_sm |
i>= n |
9 |
3, 4, 5 и др. |
vv_m_sm |
j < 0 |
9 |
3, 4, 5 и др. |
vv_m_sm |
j >= n |
7, 9 |
3, 4, 5 и др. |
vv_m_sm |
g[i][j] ==1 |
3 |
4, 5, 6 и др. |
vv_m_sm |
pp<= 0 |
6 |
3, 4, 5 и др. |
vv_m_sm |
p == 1 |
4, 5 |
3, 6, 7 и др. |
vv_m_sm |
p > 2 |
10 |
3, 4, 5 и др. |
obrab |
i< n |
3, 7, 8, 9, 11, 12 |
9 |
obrab |
j < n |
3, 4, 5, 8, 11, 12 |
7, 9 |
Obrab |
k < n |
3, 4, 5, 7, 8, 9, 11, 12 |
7, 9 |
Obrab |
d[i][k] != 0 |
3, 11 |
12 |
Obrab |
d[i][k]+d[k][j] < d[i][j] |
3, 11 |
3, 11, 12 |
ЗАКЛЮЧЕНИЕ
В ходе курсовой работы была написана программа на языке программирования C, которая находит медиану графа, то есть такую его вершину, что сумма его расстояний от нее до остальных минимальна.
В программе используются следующие определения как граф, путь, длина пути, расстояние, медиана графа.
У графа длина (вес) пути определяется как сумма длин его ребер. Расстояние D[i][j] между вершинами i и j – длина кратчайшего пути между ними. Считается, что расстояние от вершины до нее самой равно нулю: D[i][i] = 0. У не взвешенного графа вес ребра равен 1; длина пути и расстояние измеряются числом ребер.
Кратчайший путь в графе от заданной вершины до одной или до всех вершин можно найти методом обхода в ширину. Кратчайшие пути и расстояния между всеми вершинами быстрее определяются через матрицу расстояний или алгоритм Флойда. В данной курсовой работе при нахождении медианы графа используется алгоритм Флойда. Который формулируется так: пусть в элементе матрицы A[i, j] хранится длина кратчайший пути из вершины i в вершину j, который проходит через некоторые вершины с номерами, не превосходящими k – 1. Если же длины пути из вершины i в вершину k и пути из вершины k в вершину j таковы, что их сумма меньше, чем значение данного элемента матрицы, то его следует переопределить.
Программа состоит из трех функционально-прочных модулей: glav – главная программа, vv_m_sm – ввод графа, obrab – вывод матрицы расстояний.
Все данные между модулями передаются только в виде параметров, глобальных переменных в программе нет. Модуль main сцеплен с модулями vv_m_sm и obrab по формату.
Курсовая работа выполнена в соответствии с требованиями в полном объёме.
ЛИТЕРАТУРА
- Хохлов Д.Г. Структуры данных и комбинаторные алгоритмы: Учебное пособие - Казань: КГТУ, кафедра АСОИУ, 2010. 102 с.
- Хохлов Д.Г., Захарова З.Х. Практикум по структурам данных и комбинаторным алгоритмам: Учебное пособие. - Казань: КГТУ, кафедра АСОИУ, 2009. - 46 с.
- Хохлов Д.Г. Основы технологии модульного программирования: Учебное пособие – Казань: КГТУ, кафедра АСОИУ, 2011. 64 с.
ПРИЛОЖЕНИЕ 1
Системные файлы проекта
- Файл zulka.prj – перечнь модулей проекта
Main.c
Vv_m_sm.c
Obrab.c
- Файл graf.h
/* graf.h */
/* Определения для функции обработки графов */
#ifndef _GRAFH
#define _GRAFH
#ifndefNMAX
#defineNMAX20 /*максимальное количество вершин графа*/
ПРИЛОЖЕНИЕ 2
Текст программы модуля glav
#include <stdio.h> #include "graf.h"
void main()
{int g[NMAX][NMAX] ={0}; /* matrica smezhnosti grafa */
int d[NMAX][NMAX]; /* matrica rasstoyanii*/
int n,i,j; /* kol-vovershin, nomera vershin*/
int dl=0, z=0; /* min. dlina, vichislaemaya vershina*/
int mdl=99, kz; /*priznak ne svyaznosti, kod zavershenia podprogrammi*/
int status;
clrscr();
puts ("\n Zadacha: naiti mediany grafa, t.e. takyu ego vershiny, chto summa ego rasstoyanii ot nee do ostalnix minimalna \n"); /* vivod zadania*/
puts ("\n Vvedite graf (kol-vo vershin ot 0 do 20): \n"); /* vvedite kol-vo vershin*/
scanf("%d",&n);
if(n>NMAX || n < 1)
{puts ("\n Oshibka: kol-vovershin ot 1 do:\n");
printf("%d",NMAX); /* Oshibka: kol-vo vershin ot 1 do: NMAX */
puts ("\n Reshenie precrasheno\n");
getch();
exit(status-'0'); /*Reshenie precrasheno */
}
else
kz=vv_m_sm(n,g); /* vvod grafa */
if(kz>1)
{if(kz==4)
puts ("\n Oshibka: nomer vershini dolzhen bit ot 0 do : \n");
printf(" %d",n-1); /*Oshibka: nedopustimii nomer */
if(kz==5)
puts ("\n Oshibka: rebro dolzhno soderzhat dve vershini \n") /* Oshibka:kol-vo vershin>2 ili<2*/
puts ("\n Reshenie precrasheno\n");
}
else
{ if(kz==1) /* dublirovanie reber */
puts ("\n Preduprezhdenie: bilo dublirovanie reber \n");
obrab(n,g,d); /* vizov funkcii obrab */
for(i = 0; i< n; i++)
{dl=0;
for(j = 0; j < n; j++) /* vichislenie */
{ if(d[i][j]!=0)
dl = dl + d[i][j]; /* vershini s */
}
if(dl > mdl) /* minimalnim */
{mdl = dl;
z = i;} /* rasstoyaniem */
}
printf("\n Mediana : %d , Rasstoyanie : %d\n",z,mdl); /*vivod minimalnogo rasstoyania*/
}
getch();
}
ПРИЛОЖЕНИЕ 3
Тест программы модуля vv_m_sm.
#include<stdio.h>
#include "graf.h"
vv_m_sm (int n, int g[][NMAX])
{int i, j; /* nomera strok i stolbcov matrici cmezhnosti */
int pr=0; /* priznak dublirovania reber */
int p, pp; /* proverka kol-va versin, ....*/
int status;
puts ("\n Vvedite posledovatelnoct grafa, v konce<Ctrl+Z>\n"); /* vvod reber grafa */
for(i=0; i<n; i++)
for(j=0; j<n; j++)
g[i][j]=0; /* obnulenie grafa */
while((p=scanf("%d%d",&i,&j))=
{if(p<2)
{printf("p1=%d",p);
return 5;}
pp++;
if(i<0 || i>=n || j<0 || j>=n) return 4; /* nedopustimii №*/
{ if(g[i][j]=g[j][i]) pr=1 /*dublirovanie reber*/
g[i][j]=1;
g[j][i]=1; }
return pr;
if(pp<=0)
{puts ("\n Oshibka: net vxodnix dannix\n");
puts ("\n Reshenie prekrasheno\n");
getch();
exit(status-'0'); }
return pr;
ПРИЛОЖЕНИЕ 4
Текст программы модуля obrab
#include "graf.h"
void obrab (int n, int g[][NMAX], int d[][NMAX])
{int i, j; /* nomer vershin, nachalnoi i konecnoi*/
int k; /*nomer vershini is mnozhestva k */
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
d[i][j] = g[i][j]; /*prisvaivanie matr. passtoyanii mart. vesov*/
for(i = 0; i < n; i++)
d[i][i] = 0; /*passtoanie ot versh. do nee camoi = 0 */
for(k = 0; k < n; k++)
for(i = 0; i < n; i++)
if(d[i][k]!=0)
for(j=0;j<n; j++)
{if(d[i][k]+d[k][j]<d[i][j]) /
d[i][j]=(d[i][j],d[i][k]+d[k][
}
puts ("\n Matrica rasstoyanii\n"); /* vivod matr. rasstoyanii*/
for(i=0;i<n; i++)
printf(" %d",i);
printf( "\n ");
for(i=0;i<7;i++)
printf("");
for(j=0;j<n; j++)
{printf("\n%d:і",j);
for(i=0;i<n; i++)
printf("%d ",d[i][j]);
}
}
ПРИЛОЖЕНИЕ 5
Результаты тестирования программы
Тестирование всей программы с файлом проекта zulka.prj на "правильных" тестах.
Тест 1
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
0
Ошибка: количество вершин должно быть от 1 до: 20
Решение прекращено
Тест 2
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
21
Ошибка: количество вершин должно быть от 1 до: 20
Решение прекращено
Тест 3
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
4
Введите последовательность графа, в конце <Ctrl+Z>:
0 1
0 2
0 3
1 3^ Z
Матрица расстояний:
0 |
1 |
2 |
3 | |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
2 |
1 |
0 |
0 |
1 |
3 |
1 |
1 |
1 |
0 |
Медиана – 0, расстояние – 3
Тест 4
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
5
Введите последовательность графа, в конце <Ctrl+Z>:
0
0 2
0
0-3 ^ Z
Ошибка: ребро должно содержать две вершины
Решение прекращено
Тест 5
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
5
Введите последовательность графа, в конце <Ctrl+Z>:
0
0-3-1
0 4 ^ Z
Ошибка: ребро должно содержать две вершины
Решение прекращено
Тест 6
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
5
Введите последовательность графа, в конце <Ctrl+Z>:
<Ctrl+Z>
Ошибка: нет входных данных
Решение прекращено
Тест 7
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
5
Введите последовательность графа, в конце <Ctrl+Z>:
1 6
2-3
4-4 ^ Z
Ошибка: номер вершины должен быть от 0 до: 4
Решение прекращено
Тест 8
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
5
Введите последовательность графа, в конце <Ctrl+Z>:
-1 3
1 3
3 2
0 2
2 4 ^ Z
Ошибка: номер вершины должен быть от 0 до: 4
Решение прекращено
Тест 9
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
5
Введите последовательность графа, в конце <Ctrl+Z>:
-1 3
7 (-2)
3 2
3 4
3 5 ^ Z
Ошибка: номер вершины должен быть от 0 до: 4
Решение прекращено
Тест 10
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
5
Введите последовательность графа, в конце <Ctrl+Z>:
012
0 2
2 1
2 3 ^ Z
Ошибка: номер вершины должен быть от 0 до: 4
Решение прекращено
Тест 11
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
Введите граф (количество вершин от 1 до 20):
7
Введите последовательность графа, в конце <Ctrl+Z>:
0 1
0 6
1 6
2 6
2 3
2 4
6 3
3 4
6 4
4 5
6 5
^Z
Матрица расстояний:
0 |
1 |
2 |
3 |
4 |
5 |
6 | |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
2 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
3 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
4 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
5 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
6 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
Медиана – 6, расстояние – 6
Тест 12
Задача: Найти медиану графа, т.е., такую его вершину, что сумма его расстояний от нее до остальных вершин минимальна
- Медиаобраз В. Жириновского в СМИ
- Медиаобразование
- Медиаобразование в современных условиях
- Медиаобразование и проблема экранного насилия
- Медиаплан для ОАО «Сибтелеком»
- Медиапланирование
- Медиапланирование
- Медецинские услуги
- Медецинское страхование в России и пути его развития
- Медиавирусы
- Медиаисследования
- Медиа как инструмент продвижения бизнеса
- Медиаконцерн «Аргументы и факты» в информационном поле России
- Медиалингвистика: системный подход к изучению языка СМИ
