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

Граф программы (граф управления) – это структурная модель программы, которая показывает связь м/ ее элементами. Вершины – операторы разветвления и объединения; дуги – операторы обработки и передачи данных.

Граф представляется в виде упакованной матрицы смежности (УМС) А.

А = {a_ij}

с v вершинами – есть матрица v l, l – max степень выхода i-ой вершины

d_ВХ(v_i) – степень входа и d_ВЫХ(v_i) – степень выхода некоторой вершины графа означает соответственно количество входящих и выходящих из вершины дуг.

Каждая строка i УМС заполняется в произвольном порядке номерами вершин, которые являются смежными с вершиной i.

Представление графов в виде УМС имеет следующие преимущества:

1) для больших графов число столбцов УМС значительно <, чем число столбцов соответствующей матрицы смежности.

2) относительно просто моделируется процесс движения по графу для построения путей.

3) снижается время обработки графов.

За критерий тестирования взят критерий ветвей, где под ветвью программы понимается некоторая последовательность операторов, которые выполняются строго 1 за другим.

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

Множество вершин, у которых степень выхода d_ВЫХ(v_i)>1, вх и вых вершины обозначаются как Д вершины. Тогда путь ДД – это простой путь м/ двумя Д вершинами, такой, что в его пределах нет Д вершин.

Затем определяют циклы, петли и из графа исключаются замыкающие их дуги.

Алгоритм построения min покрытия графа состоит из следующих этапов:

1) просматриваемая i-ая вершина фиксируется, определяется смежная вершина j-ая, номер которой является максимальным среди номеров смежных вершин.

i [1, N-1]       N – количество вершин графа.

2) просматривается дуга v_iv_j. Если количество выходов d_ВЫХ(v_i)>1, а d_ВХ(v_j)>1, то дуга g(v_i,v_j) исключается.

3) Еслт количество d_ВЫХ(v_i)=1, d_ВХ(v_j)>1 и если на пути не имеется дуги типа g, то исключается рассматриваемая дуга типа h (дуга v_iv_j).

4) Подставляется i=j и повторяются этапы 1-3, пока j не станет = номеру конечной или выходной вершины. Пути фиксируются в виде последовательностей значений j.

5) Повторяя-ся 1-4 до тех пор, пока в построенном пути не останется дуг типа g и h.

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

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

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