# Разработка абстрактного типа данных «Простой граф», страница 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