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

            for(A.beg(t);!A.off();A.next(t))

            {

                  if(pre[t]==-1) dfsR2(w,t);

                  else if(post[t]==-1)    //back

                  {

                        obr.push_back(w);

                        obr.push_back(t);

                  }

            }

            post[w]=cntP++;

      }

};

#endif

SPT.h

#ifndef _SPT

#define _SPT

#include "graph.h"

#include <VECTOR>

#include <algorithm>

#include "Edge.h"

template <class Graph>

class SPT

{

      Graph *G;

      std::vector<Edge> spt;

      std::vector<double> wt;

      int depth,cnt,cntP;

      std::vector<int> pre, post;

      std::vector<std::pair<int, int> > backs;

      std::vector<int> parent;

public:

      int ve;

      int ed;

      bool cycle;

      std::vector<int> res;

      SPT(Graph *G1,int s,int wmax) : spt(G1->V()), wt(G1->V(), 10000/*G1->V()*/), parent(G1->V(), -1), pre(G1->V(), -1), post(G1->V(),-1)

      {

            G=G1;

            ve=ed=0;

            cycle=false;

            DFS();

            if (!cycle){

                  SPT_(s);

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

                  {

                        if(s!=i && spt[i].w==i && wt[i]<=wmax) res.push_back(i);

                  }

            }

      }

      ~SPT()

      {

            ;

      }

private:

      void DFS()

      {

            cnt=0;

            cntP=0;

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

            {

                  if(pre[v]==-1)

                  {

                        dfsR(v,v);

                  }

            }

            for(int i=0;i<backs.size();i++)

            {

                  int it,end;

                  it=backs[i].first;

                  end=backs[i].second;

                  while(it!=end)

                  {

                        if(*G->GetEdge(parent[it],it)<0) cycle=true;

                        it=parent[it];

                  }

                  if(*G->GetEdge(backs[i].first,end)<0) cycle=true;

            }

      }

      void dfsR(int v,int w)

      {

            pre[w] = cnt++;

            Graph::Iterator A(G,w);

            if(v!=w) parent[w]=v;

            int t;

            for(A.beg(t);!A.off();A.next(t))

            {

                  if(pre[t]==-1) dfsR(w,t);

                  else if(post[t]==-1)    //back w-t

                  {

                        std::pair<int,int> temp;

                        temp.first=w;

                        temp.second=t;

                        backs.push_back(temp);

                  }

            }

            post[w]=cntP++;

      }

      void SPT_(int s)

      {

            std::queue<int> Q; int N = 0;

            wt[s]=0.0;

            Q.push(s);

            Q.push(G->V());

            while (!Q.empty()) {

                  int v;

                  if((v=Q.front()) == G->V())

                        while ((v=Q.front()) == G->V())

                        {

                              Q.pop();

                              if(N++ > G->V()) return;

                              Q.push(G->V());

                        }

                  else

                        Q.pop();

                  typename graph<double>::Iterator A(G, v);

                  ve++;

                  int t;

                  for(A.beg(t);!A.off();A.next(t))

                  {

                        ed++;

                        int w = t;

                        double P=wt[v]+*G->GetEdge(v,w);

                        if (P<wt[w])

                        {

                              wt[w] = P; Q.push(w);

                              spt[w].v=v;

                              spt[w].w=w;

                              spt[w].weight=*G->GetEdge(v,t);

                        }

                  }

            }

      }

};

#endif