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

Министерство образования и науки Российской Федерации

Новосибирский Государственный Технический Университет

Кафедра прикладной математики

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

по дисциплине «Структуры данных и алгоритмы»

Факультет: ПМИ

               Группа   ПМИ-71

Студент:

Рябинкин С. А.

Преподаватель:

Шапошникова Т. А.

Новосибирск

2008

1)  Условие задачи

Задан орграф с циклами. Проверить, можно ли удалить одну вершину так, чтобы в полученном орграфе не было циклов.

2)  Формализация задачи

Дан орграф с циклами. Нужно проверить: можно ли удалить одну вершину так, чтобы полученный граф стал ациклическим.

3)  Анализ задачи

Дано: G(V,E)-орграф

Результат:Graph is empty, если V=0

                      Atomic graph, если V=1

                      No such vertexes, если вершин удовлетворяюших условию не найдено

                       Such vertexes- найдены вершины, удовлетворяющие условию

Метод решения:

 Строим список вершин, которые состоят в циклах. Очевидно, что только при удалении вершин, находящихся в цикле граф может стать ациклическим.

Затем проверяем граф на ацикличность, последовательно удаляя по одной вершине, состоящей в цикле.

Структура main

ЕСЛИ (input()==0) вовращаем 0;

       clear(); Очищаем память

       create_stack(&cicles,n);//создадим хранилища

       create_stack(&st,n);

 ЕСЛИ( !find_vercicles())

{printf("No cicles. Check input data.\n");return 0;}

 check_vers();

output();//выводим

clearmem();//очищаем память

return 1;

4)Структуры данных

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

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

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

    Так как нам требуется построить граф, то для задания вершины используем структуру:

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

{   int number;    //номер

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

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

};

  Для хранения вершин, состоящих в цикле, будем использовать стек:

struct stack{    //Структура стека

  int head;           //вершина стека

  int* data;               //данные, хранимые в стеке

  int maxin;               //максимально элементов в стеке

};

5) Структура программы

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

#include<conio.h>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

struct stack{    //Структура стека

  int head;           //вершина стека

  int* data;               //данные, хранимые в стеке

  int maxin;               //максимально элементов в стеке

};

void create_stack(stack *s,int n){   // функция создание стека

  s->data=(int*)calloc(n,sizeof(int));

  s->head=0;

  s->maxin=n;

}

int is_empty(stack s){    //функция проверки пуст ли стек

  if(s.head==0) return 1;

  return 0;

}

int is_full(stack s){                     //функция проверки полон ли стек

  if(s.head==s.maxin) return 1;

  return 0;

}

void in_stack(stack *s,int numb){   //функция добавления элемента в стек

  if(!is_full(*s)){

              s->data[s->head]=numb;

              s->head++;

              }

  else printf("Error! Stack is full.\n");

}

int out_stack(stack *s){               //функция удаление элемента из стека

  if(!is_empty(*s)){

              int k;

              k=s->data[s->head-1];

              s->head--;

              return k;

  }

  else printf("Error!Stack is empty.\n");

  return -1;

}

void destroy_stack(stack *s){                 //очистка стека

  free(s->data);

}

int is_instack(stack s,int k){

  int i;

  for(i=0;i<s.head;i++)

              if(s.data[i]==k) return 1;

  return 0;

}

#include<string.h>

#include"Stack.h"

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

{   int number;   //номер

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

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

};

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

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

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

stack cicles;   //здесь будем хранить вершины, которые есть в циклах

stack st;   //здесь будем хранить порядок обхода

int *result;   //здесь будем хранить результат

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

int f;   //переменная поиска

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);    //считываем кол-во вершин

  if(n==0) {printf("Graph is empty.\n");   //пустой граф

                getch();

                return 0;}

  if(n==1) {printf("Atomic graph.\n");   //атомарный граф

                getch();

                return 0;}

  ob=(graph_v*)calloc(n,sizeof(graph_v));   //выделяем память под граф

  mark=(int*)calloc(n,sizeof(int));   //и массив марок