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

Конечный файл:

The cycles are:

1 4 2

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

Берём первую вершину и по первому ребру в списке рёбер, содержащему вершину 1, переходим в следующую вершину. В нашем случае это вершина 2. Далее выбираем первое ребро, содержащее вершину 2. Это ребро 1 – 2, но мы его уже использовали, а значит переходим на следующее ребро, инцидентное 2, а именно 2 – 4. По нему мы попадаем в вершину 4. Первое ребро списка, инцидентное ей, это ребро 1 – 4. Мы попадаем в вершину 1, но она уже помечена, а значит мы нашли один фундаментальный цикл. Очередное ребро, инцидентное вершине 4, 2 – 4. Оно уже использовано, а других рёбер с вершиной 4 нет, значит возвращаемся в вершину 2. Из вершины 2 по ребру 2 – 3 переходим в вершину 3. Единственное ребро, инцидентное вершине 3, (2 – 3) уже использовано, значит возвращаемся в вершину 2. Не использованных рёбер, инцидентных 2, нет, поэтому возвращаемся в вершину 1. Ребро 1 – 4, инцидентное вершине 1, уже использовано, других рёбер, инцидентных ей нет, значит алгоритм завершён.

	1		3

 

Остовное дерево в этом случае имеет вид

 

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

#include <stdio.h>

struct stack

{ int *stek;

  int hstack;

} s;

int nreb,nver=0;

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

FILE *in,*out;

/*---------- Запись ребра x – y в матрицу циклов ------------*/

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;

  hstack--;

  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 CYCLE(int x)

{ int v;

  versh[x-1]=1;

  int k=0;

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

  {  v=0;

     if (rebra[k][2]==0)

     { if (rebra[k][0]==x) v=rebra[k][1];

       if (rebra[k][1]==x) v=rebra[k][0];

     }

     if (v!=0)

     {  rebra[k][2]=1;

     s.stek[s.hstack]=v;

     s.hstack=s.hstack+1;

     if (versh[v-1]==0) CYCLE(v);

     else write(v,s.hstack);

     s.hstack=s.hstack-1;

     }

  }

}

/*---------- Ввод рёбер и упорядочивание вершин в них -------*/

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];

    s.hstack = 1;

    s.stek[0]=1;

    CYCLE(1);

    s.hstack--;

  }