## 离散作业之无环图两点间路径数目

2018年05月11日 ⁄ 综合 ⁄ 共 1962字 ⁄ 字号 评论关闭

Write a program that takes as input a directed acyclic graph G = (V, E) and two

vertices s and t, and returns the number of paths from s to t in G.

void Graph::initDFS(){
initBFS();
for(int i=0;i<nodeCounts;i++){
graNodes[i].fin=INF;
}
}

bool Graph::DFS(){
initDFS();
int time=0;
for(int i=0;i<nodeCounts;i++){
if(graNodes[i].color==WHITE)
DFSVisit(&graNodes[i],&time);
}
return true;
}

void Graph::DFSVisit(Node* uNode, int* time){
uNode->color=GRAY;
(*time)++;
uNode->level=(*time);
if((*ivl)->color==WHITE){
(*ivl)->pre=uNode->nodeID;
DFSVisit(*ivl,time);
}
}
uNode->color=BLACK;
(*time)++;
uNode->fin=(*time);
//cout<<"*"<<uNode->nodeID<<"*"<<uNode->level<<"*"<<uNode->fin<<endl;
}

int Graph::Paths(int s,int t){
if(s>=nodeCounts || t>=nodeCounts){
cout<<"输入的节点不在图中"<<endl;
return 0;
}

DFS();

int sT=graNodes[s].fin;
//cout<<sT<<endl;
int tT=graNodes[t].fin;
//cout<<tT<<endl;
if(sT<=tT){
cout<<"终点比起点先结束"<<endl;
return 0;
}

for(int i=0;i<nodeCounts;i++){
graNodes[i].justPaths=JUST;
}
graNodes[s].justPaths=1;

deque<Node*> blocks;
blocks.clear();
blocks.push_back(&graNodes[s]);

Node* tempNode;
int time;

int num=sT-tT;
int* dequeNode=new int[num];

for(int i=0;i<num;i++)
dequeNode[i]=INF;

for(int i=0;i<nodeCounts;i++){
time=graNodes[i].fin-tT;
if(time<num && time>0){
dequeNode[time]=graNodes[i].nodeID;
}
}

for(int i=num-1;i>0;i--){
int id=dequeNode[i];
if(id!=-1){
blocks.push_back(&graNodes[id]);
}
}

while(!blocks.empty()){
tempNode=blocks.front();
//cout<<"xjt"<<tempNode->nodeID<<endl;
time=tempNode->fin;
blocks.pop_front();