Поиск одного из фундаментальных множеств циклов данного связного неориентированного графа, страница 3

  else fprintf (out,"No cycles.");

  delete rebra;

  delete s.stek;

  delete versh;

  fclose(in);

  fclose(out);

  return (result);

}

5.  Тесты

№	Граф	Исходный файл	Конечный файл
1		5 10 1 2 1 3 1 4 1 5 3 2 3 4 3 5 5 2 5 4 2 4	The cycles are: 1 3 2 1 4 3 2 1 5 4 3 2 3 5 4 2 5 4 3 2 4 3
2		10 12 2 1 2 3 3 1 3 4 7 4 7 5 7 6 5 6 4 10 9 10 9 8 8 10	The cycles are: 1 3 2 7 6 5 10 8 9
3		8 8 1 2 2 3 2 4 4 7 4 8 5 8 6 7 6 5	The cycles are: 4 8 5 6 7
4		4 4 1 2 1 4 4 2 3 2	The cycles are: 1 4 2
5		4 3 1 2 2 3 2 4	No cycles.

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

1.  Иванов Б. Н. Дискретная математика. Алгоритмы и программы. – М.: Лаборатория базовых знаний, 2001.

2.  Кофман А. Введение в прикладную комбинаторику. – М.: Наука, 1975.

7.  Дополнение

Не рекурсивная реализация этого алгоритма выглядит следующим образом:

#include <stdio.h>

struct stack

{ int *stek;

  int top;

} s,p;

int nreb,nver=0;

int **result=NULL,**rebra,*versh;

FILE *in,*out;

void fillmat(int x, int y, int n)

{ int k=0;

  if (x<y)

      while (!(x==rebra[k][0]&&y==rebra[k][1])) k++;

  else

      while (!(x==rebra[k][1]&&y==rebra[k][0])) k++;

  result[k][n]=1;

}

void write (int x,int hstack)

{ static int n=0;

  do { fprintf (out,"%d ",s.stek[hstack]);

       fillmat(s.stek[hstack],s.stek[hstack-1],n);

       hstack--;

      }

  while (s.stek[hstack]!=x);

  fprintf (out,"\n");

  n++;

}

void vvodreber()

{ int i,j,first,second;

  rebra = new int *[nreb];

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

    rebra[i]=new int [3];

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

  {  fscanf (in,"%d",&first);

     fscanf (in,"%d",&second);

     if (first<second)

     { rebra[i][0]=first;

       rebra[i][1]=second;

     }

     else

     { rebra[i][0]=second;

       rebra[i][1]=first;

     }

     rebra[i][2]=0;

  }

}

int** main()

{ in = fopen("graf.txt","r");

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

  int i,j;

  fscanf (in,"%d",&nver);

  fscanf (in,"%d",&nreb);

  vvodreber();

  int cycles=nreb-nver+1;

  if (cycles>0)

  { fprintf (out,"The cycles are:\n");

    versh=new int [nver];

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

      versh[i]=0;

    result= new int *[nreb];

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

      result[i]=new int [cycles];

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

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

       result[i][j]=0;

    s.stek = new int [nver+1];

    p.stek = new int [nver+1];

    int v=1,k;

    s.top = 0;

    p.top = 0;

    s.stek[0]=v;

    p.stek[0]=0;

    while (s.top>=0)

    { versh[v-1]=1;

      v=0;

      for (p.stek[p.top];p.stek[p.top]<nreb&&v==0;p.stek[p.top]++)

      {

       if (rebra[p.stek[p.top]][2]==0)

       { if (rebra[p.stek[p.top]][0]==s.stek[s.top])

                      v=rebra[p.stek[p.top]][1];

         if (rebra[p.stek[p.top]][1]==s.stek[s.top])

                      v=rebra[p.stek[p.top]][0];

       }

      }

      if (v!=0)

      {  rebra[p.stek[p.top]-1][2]=1;

       s.top=s.top+1;

       s.stek[s.top]=v;

       p.top=p.top+1;

       p.stek[p.top]=0;

       if (versh[v-1]!=0) { write (v,s.top);

                        s.top=s.top-1;

                        p.top=p.top-1;

                        v=s.stek[s.top];

                       }

      }

      else { s.top=s.top-1;

           p.top=p.top-1;

           v=s.stek[s.top];

         }

    }

  }

  else fprintf (out,"No cycles.");

  delete rebra;

  delete s.stek;

  delete versh;

  return (result);

  fclose(in);

  fclose(out);

}