Поиск всех вершин орграфа, от которых существует путь заданной длины к выделенной вершине, страница 2

void FindVertexs(int *G, int *weight, int vertex, int num, int len, int path, int *IsVis, int *res, int curV, int start);

#endif /* __FUNCTIONS__ */

Модуль, включающий в себя функции программы:

#include "functions.h"

void ReadGraph(FILE *file, int *num, int **G, int **weight)

{

      int count; /* обыкновенный счетчик */

      char curStr[STR_SIZE]; /* текущая строка */

      fgets(curStr, STR_SIZE, file);

      sscanf(curStr, "%d", num);

      *G = (int *)calloc((*num)*(*num), sizeof(int));

      *weight = (int *)malloc((*num)*(*num)*sizeof(int));

      for(count = 0; count < (*num)*(*num); ++count)

      {

            (*weight)[count] = INT_MAX;

      }

      while(fgets(curStr, STR_SIZE, file) != NULL)

      {

            int ver[2]; /* две текущие вершины */

            int w; /* вес текущего ребра */

            sscanf(curStr, "%d - %d : %d", &ver[0], &ver[1], &w);

            (*G)[ver[0]*(*num) + ver[1]] = 1;

            (*weight)[ver[0]*(*num) + ver[1]] = w;

      }

};

void FindVertexs(int*G, int *weight, int vertex, int num, int len, int path, int *IsVis, int *res, int curV, int start)

{

      int cnt;

      if(path == len && curV == vertex)

      {

            res[start] = 1;

      }

      for(cnt = 0; cnt < num; cnt++)

      {

            if(G[curV*num + cnt] == 1 && !IsVis[cnt])

            {

                  IsVis[cnt] = 1;

                  FindVertexs(G, weight, vertex, num, len, path + weight[curV*num + cnt], IsVis, res, cnt, start);

                  IsVis[cnt] = 0;

            }

      }

};

Модуль с основной программой(main):

#include <stdlib.h>

#include <stdio.h>

#include "functions.h"

int main(int argc, char **argv)

{

      FILE *fin; /* файл откуда читаем граф */

      FILE *swe; /* файл куда помещаем результат */

      int vertex; /* вершина для которой нужно все сделать */

      int length; /* необходимая длина пути */

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

      int *G; /* массив ребер; 1 - есть ребро, 0 - нет ребра */

      int *weight; /* веса ребер, если ребра нет то INT_MAX */

      int *IsVis; /* массив посещенных вершин */

      int *result; /* массив достижимых вершин */

      int cnt; /* счетчик */

      do

      {

            if(argc > 4)

            {

                  printf("Too many arguments:\n-[filename] -[vertex] -[length]\n");

                  break;

            }

            if(argc < 4)

            {

                  printf("Too few arguments:\n-[filename] -[vertex] -[length]\n");

                  break;

            }

            fin = fopen(argv[1], "rb");

            if(fin == NULL)

            {

                  printf("Can not open \"%s\"\n", argv[1]);

                  break;

            }

            sscanf(argv[2], "%d", &vertex);

            sscanf(argv[3], "%d", &length);

            ReadGraph(fin, &num, &G, &weight);

            IsVis = (int *)calloc(num, sizeof(int));

            result = (int *)calloc(num, sizeof(int));

            for(cnt = 0; cnt < num; cnt++)

            {

                  if(cnt != vertex)

                  {

                        IsVis[cnt] = 1;

                        FindVertexs(G, weight, vertex, num, length, 0, IsVis, result, cnt, cnt);

                        IsVis[cnt] = 0;

                  }

            }

            swe = fopen("out.txt", "w");

            for(cnt = 0; cnt < num; cnt++)

            {

                  if(result[cnt] == 1)

                  {

                        fprintf(swe,"%d\n", cnt);

                  }

            }

            fclose(fin);

            fclose(swe);

            free(weight);

            free(IsVis);

            free(result);

            free(G);

      } while(0);

      return 0;

};

7.  Тесты

№	Дано в файле	Входные данные	Графическое представление	Выходные данные	Комментарии
1	5 1 – 2 : 3 2 – 3 : 3 3 – 4 : 3 4 – 5 : 3 5 – 2 : 3	In.txt 4 6		2	Работа программы при нормальных условиях
2	5 1 – 2 : -9 2 – 3 : -2 3 – 4 : -7 3 – 5 : 8 5 – 2 : 3	In.txt 5 -3		1	Работа программы с отрицательными весами
3	6 0 - 1 : 2 1 - 2 : 3 2 - 3 : 4 3 - 4 : 5 4 - 1 : 6 5	In.txt 5 6			Работа программы при существовании изолированных вершин
4
5

8.  Вывод

Программа работает правильно на всех проведенных тестах.

9.  Список используемой литературы

1.  «Практикум на ЭВМ. Алгоритмы» П 691 Учебное пособие / В.П. Хиценко, Т.А. Шапошникова  - Новосибирск: Изд-во НГТУ, 2004. - 112 с.

2.  «Структуры данных и алгоритмы» С 873 Методические указания к КР для студентов I курса / В.П. Хицен ко, Т.А. Шапошникова – Новосибирск: Изд-во НГТУ, 2008 г. 56 с.