Проверка возможности удаления из заданного графа (не дерево) одной вершины (вместе с инцидентными ей ребрами), чтобы в результате получилось дерево, страница 2

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

Внутреннее представление

В программе граф представлен следующей структурой данных:

struct graph {

        int number;

        int deg;

        int* smezh;} – структура вершины графа.

int number – целое число. Номер вершины

int deg – целое число. Степень вершины

int* smezh – указатель на целый тип. Массив смежных вершин. Память не выделяется, если степень 0.

Граф хранится в динамическом массиве объектов структуры graph (graph* verch). 

Далее строится двумерный динамический массив типа int, организованный как матрица достижимости (переменная int** matd – указатель на этот массив).

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

Внутреннее представление

Результаты работы хранятся в одномерных динамических массивах типа int – R и P.

Внешнее представление

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

4. Подпрограммы. Их взаимодействие и взаимосвязь.

intinput() – подпрограмма ввода графа. Возвращает 1, если ввод произошел удачно, и 0, если введенный граф некорректен или возникла ошибка при открытии файла.

voidclear() – подпрограмма очистки массива марок.

void goth(int numb) – подпрограмма обхода в глубину.

Входные переменные:

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

int goneall() - поиск не пройденных вершин. Возвращает 0, если есть «нарушитель», и 1, если все нормально.

void output() – подпрограмма вывода.

int find_vertex() – подпрограмма поиска вершины, с которой можно начинать обход.

int is_svyaz(int numbs) – проверка графа на связность.

Входные переменные:

int numbs - номер вершины, которая была удалена из графа.

intnumb_rebs(intnumbs) – проверка согласованности числа ребер и вершин. Сумма степеней вершин должна быть равна удвоенному количеству ребер.

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

intnumbs– количество ребер.

voidin_result(intnumb) – добавление вершины в результат: если при её удалении граф становится деревом (т.е. выполняется условие отсутствия циклов и связности), то увеличиваем значение счетчика на 1.

main – головная функция, связывающая между собой все подпрограммы.

5. Алгоритм.

Задание графа списком смежности;

// очистка марок

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

  mark [V]= белая;}

// поиск не пройденных вершин:

{i;

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

      { if (существует вершина со степенью mark[V]=0)

      «нарушено условие связности»;

      еlse «нет не пройденных вершин»;}}

// обход графа в глубину – только вершина, имеющая метку 2 не будет проходиться:

{if  (mark u є [V]=0)

{mark [u] =1;

  for (i=0; i<степени [V]; i++)

  mark [u]=2;}}

// вывод

{if ( “количество вершин” =0) “граф пустой”;

 else {“вывод вершин”;

          for (i=0; i<“количество вершин”;i++)

                 “вывод  i”;

          иначе “граф задан не верно”;}}

// находим вершину, с которой начинается обход

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

 if (mark [V]=0) возврат mark [V];

 иначе “нет такой вершины”;}

// проверкa графа на связность:

{помечаем предполагаемую удаляемую вершину mark [u]=2;

 обходим граф;

 if (пройдены все вершины)

 «граф связен»;

 else «граф не cвязен»; }

// подсчет количества рёбер – удаление рёбер, инцидентных с удаленной вершиной

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

        “суммируем степени вершин”;

  “сумма степеней вершин равна удвоенному количеству рёбер”;

“ отнять инцидентные удаленной вершине рёбра”;}

// добавление вершины в результат

{“счетчик ++”;}

6. Текст программы

#include<conio.h>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

struct graph_v//структура вершины графа

{   int number;//номер

            int degree;//степень

            int* nears;//список смежности};

graph_v *ob;//указатель на массив вершин

int n;//число вершин

int* mark;//массив марок

int* result;//результат

int numb_res=0;//и количество вершин в результате

int input(){//подпрограмма ввода

            int i;

            char inpname[30];

            FILE *f;

            printf("Enter the name of input file:\n");

            scanf("%s",inpname);

            if ((f = fopen(inpname, "r"))== NULL)

                           {printf("Cannot open input file!\n");

                        getch();

                        return 0;}

            fscanf(f,"%d",&n);//считываем кол-во вершин