Разработка абстрактного типа данных «Простой граф», страница 13

            int v,i;                //номер вершины для которой создан итератор и номер текущей смежной вершины

      public:

            Iterator(matrixGraph* _g,int _v)//конструктор

            {

                  g=_g;

                  v=_v;

                  i=-1;

            }

            ~Iterator()

            {}

           

            bool beg(int& rez)//установка итератора на первую смежную вершину,

            {

                  if(v>=g->V() || v<0)//проверка параметров

                        return false;

                  i=-1;

                  if(next(rez)) return true;

                  return false;

            }

 

            bool off()//      опрос окончания просмотра смежных вершин,

            {

                  if(i>=g->V())//если итератор не установлен - cur меньше нуля

                        return true;

                  return false;

            }

 

            bool next(int &rez)     //переход к следующей смежной вершине,

            {

                  for(i++;i<g->V();i++)//поиск следующего ненулевого элемента в соответствующей строке

                        if(g->mas->mas[v][i]){

                              rez=i;

                              return true;

                        }

                  return false;

            }

 

            T1& operator *()//      доступ к данным текущего ребра

            {

                  if(v>=g->mas->sz ||v<0 || off() || !g->vz || ((vzmatrix*)g->mas)->ves[v][i]==NULL)//проверка параметров

                        throw 1;

                  return *((vzmatrix*)g->mas)->ves[v][i];//получение данных

            }

      };

 

};

 

#endif

 

DFS.h

#ifndef _Task1

#define _Task1

#define white 1

#define grey 2

#define black 3

#include "graph.h"

#include <VECTOR>

template <class Graph>

class DFS

{

      Graph *G;

      std::vector<int> p,color,d,f;

      int time;

      int cnt;

      std::vector<int> ord;

      std::vector<int> st;

      std::vector<bool> used; //vector of used vertices

public:

      int ve;

      int ed;

      std::vector<std::vector<int> > cycles; //cycles

      DFS(Graph *G1) : st(G1->V(), -1), ord(G1->V(), -1), cnt(0), used(G1->V(),false), p(G1->V()) \

            ,color(G1->V()), d(G1->V()), f(G1->V())

      {

            G=G1;

            ve=ed=0;

            DFS_();

            ed=ed/2;

      }

      ~DFS()

      {

      }

private:

      void DFS_()

      {

            //dfs

            int i;

            for(i=0;i<G->V();i++)

            {

                  color[i]=white;

                  p[i]=-1;

            }

            time=0;

            ord[0]=0;

            st[0]=0;

            for(i=0;i<G->V();i++)

            {

                  if(color[i]==white)

                  {

                        DFS_VISIT(i);

                  }

            }

            //searching non-crossing cycles

            for(i=0;i<G->V();i++)

            {

                  for(int j=0;j<G->V();j++)

                  {

                        if(G->Edge(i,j) && (ord[j] < ord[i]) && (st[i]!=j))      //i-j - back link

                        {

                              int it,end;

                              bool t=true;

                              //first step: check vertices in current cycle if it exists in "used vertices" array

                              it=i;

                              end=j;

                              while (it!=end) {

                                   if(used[it]) t=false;

                                   it=st[it];

                              }

                              if(used[it]) t=false;

                              if(t) //cycle not included used vertices => adding this cycle

                              {