Количество компонент связности в дополнении заданного графа

    ВХОДНЫЕ ДАННЫЕ:    n – количество вершин в графе, матрица связности графа.

    ВЫХОДНЫЕ  ДАННЫЕ: количество компонент связности.

    РАБОЧИЕ ДАННЫЕ:

    i – номер вершины, с которой начинается ребро.

    j – номер вершины,  которой заканчивается  ребро.

    kol – количество компонент связности.

    vp[NMAX] –  вектор посещения. 

    АЛГОРИТМ: см. алгоритм 3.7. 

    Алгоритм 3.7. Алгоритм модуля  int  comp_sv(int n, int mtrsv[NMAX][NMAX])

                                                 

    int  comp_sv(int n, int mtrsv[NMAX][NMAX])

        {   объявление переменных i, j, kol и vp[NMAX];

    обнуление в цикле  kol и vp;

          for ( i=0;i<n;i++)

                {  if (vp[i]==0)

                   {      vp[i]=1;

                 for (j=0;j<n;j++)

                  if (mtrsv[i][j]==1)

                      vp[j]=1;  kol++;

                   }

                }возврат  kol;} 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

4. ПОДГОТОВКА К ОТЛАДКЕ ПРОГРАММЫ 

4.1. План отладки 

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

1. Тестирование модуля vvod, при этом создавалась специальная программа, которая выводила матрицу смежности.
2. Тестирование модуля vivod совместно с функцией vvod и matrica_dopolnenii и главной функцией main.
3. Совместное тестирование всех модулей программы на “правильных” тестах.
4. Совместное тестирование всех модулей программы на “неправильных” тестах.

 

4.2. Проектирование тестов программы 

    4.2.1. Тесты черного ящика 

    Для проектирования тестов программы методами черного ящика с помощью эквивалентного разбиения входных/выходных данных на области (классы) эквивалентности составлен список ситуаций, каждая, из которых должна создаваться хотя бы одним тестом. Тестовые ситуации приведены в таблице 4.1., в скобках указаны их номера. 

   Таблица 4.1. 

   Области входных/выходных данных тестов программы 

    Для создания перечисленных тестовых ситуаций разработаны тесты, представленные в таблице 4.2. Входные и выходные данные тестов по возможности выбирались ближе к границам классов эквивалентности. 

Таблица 4.2. 

Тесты чёрного ящика для отладки программы 

           В ребрах вершины обозначаются через тире для наглядности.  

    4.2.2. Тесты белого ящика 

    Разработанные тесты проверены методами белого ящика по критериям охвата основных путей выполнения алгоритмов модулей. В программе имеются составные условия. Поэтому использован метод комбинаторного покрытия условий (см. таблицу 4.3.).

Таблица 4.3. 

    Комбинаторное покрытие условий  тестами белого ящика. 

 

4.3. Отладочные средства 

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

4.4. Отладка программы 

    Программа отлажена по плану на всех предусмотренных  в нем тестах. Результаты тестирования приведены в приложении 7.

    Во  время отладки обнаружены следующие  ошибки:

1. В алгоритме Уоршела написано mtrsv[i][j]=mtrsv[i][j]||mtrsv[i][j] вместо mtrsv[i][j]=mtrsv[i][j]||mtrsv[k][j];
2. Добавлена проверка на дублирование ребер.
3. В модуле comp_sv возникала ошибка неправильного подсчета компонент связности  за счет неверного входного параметра. Не подавалась полученная из модуля matrica_sviaznosti матрица связности, так как данный параметр был объявлен в самой подпрограмме    matrica_sviaznosti и поступал в модуль comp_sv с неверными значениями.
4. Неверный тип модуля  comp_sv.

 
 

Заключение 

    Курсовая  работа выполнена в соответствии с требованиями и в полном объеме.

    Список  литературы

1. Хохлов Д.Г.  Структуры данных и комбинаторные алгоритмы: Учебное пособие. – Казань: КГТУ, кафедра АСОИУ, 2000. – 102 с.
2. Хохлов Д.Г., Захарова З.Х. Практикум по структурам данных и комбинаторным алгоритмам: Учебное пособие. – Казань: КГТУ, кафедра АСОИУ, 2000. – 46 с.
3. Хохлов Д.Г.  Основы технологии модульного программирования: Учебное пособие – Казань: КГТУ, кафедра АСОИУ, 2003. – 64 с.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

   Приложение 1. Системные файлы проекта 

    

1. Файл TROFIMOVA.prj - перечень модулей и библиотек проекта (указывается как имя проекта системе Turbo-C).

    vvod.c

    vivod.c

    matrica_dopolnenii.c

    matrica_sviaznost.c

    comp_sv.c

    main.c

2. Файл graph.h-определения для библиотеки graf.lib

    #ifndef _GRAFH

    #define _GRAFH

    #ifndef NMAX

    #define NMAX 150  /* максимальное количество вершин графа*/

    #endif  

    /*    Прототиты библиотечных функций    */

    vvod (int n,int gr[][NMAX]);

    vivod(int n,int gr[][NMAX]);

    void matrica_dopolnenii(int n,int gr[NMAX][NMAX]);

     void matrica_sviaznosti(int n, int gr[NMAX][NMAX],int mtrsv[NMAX][NMAX]);

      int  comp_sv(int n, int mtrsv[NMAX][NMAX]);

       #endif

3. Файл graf.lib – библиотека функций над графами.

Библиотека создана после компиляции подпрограмм командой вызова библиотекаря.

         
 
 
 
 
 
 
 
 
 
 
 
 
 
 

   Приложение 2. Текст программы модуля main 

   /***********************************************************/

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

   /*                 по программированию на языке высокого уровня          */

   /* Количество компонент связности в дополнении заданного графа*/

   /*                                    Группа 28203  С.Н. Трофимова                         */

   /***********************************************************/

#include <stdio.h>

#include "graf.h"

#define NMAX 150

    void main()

    {  int n;                                               /* количество вершин в графе    */

        int i, j;                                              /* номера вершин в ребре         */