#include <iostream>
#include <stack>
using namespace std;
const int MAX=100;
int ve[MAX]={0},vl[MAX]={0}; //最早发生时间ve,最迟发生时间vl.
int vexnum;
class Graph{
public:
Graph();
~Graph();
bool TopologicalSort();
void CriticalPath();
private:
typedef struct ArcNode{
int adjvex;
ArcNode *next;
int info;
//权值
}ArcNode;
ArcNode *p;
typedef struct Vnode{
char data;
ArcNode *firstarc;
}Vnode;
Vnode AdjList[MAX];
int D[MAX];
//D储存所有结点的入度值,
stack<int>S,T;
};
Graph::Graph(){
cout<<"Please input node numbers[<100] : ";
cin>>vexnum;
int i,j=0,k=0;
for(i=0,j=65;i<vexnum;++i,++j)
{
D[i]=0;
AdjList[i].data=j;
//A,B,C,D,E,F;
AdjList[i].firstarc=NULL;
}
cout<<"Node was initializated(For Example:A(0),B(1),C(2).....)."<<endl;
cout<<"Input arcinfo(For Example:0 1 10),if stop input,input EOF: "<<endl;
while(cin>>i>>j>>k)
{
p=new ArcNode;
p->adjvex=j;
p->info=k;
p->next=AdjList[i].firstarc;
AdjList[i].firstarc=p;
++D[j];
}
}
Graph::~Graph(){
int i;
for(i=0;i<vexnum;++i)
{
while(AdjList[i].firstarc)
{
p=AdjList[i].firstarc;
AdjList[i].firstarc=p->next;
delete p;
}
}
system("pause");
}
bool Graph::TopologicalSort(){
cout<<"Topolagical sort is: ";
int i,count=0,k,j;
for(i=0;i<vexnum;++i)
if(!D[i])
S.push(i);
while(!S.empty())
{
j=S.top();
T.push(j);
//保存拓扑序列
S.pop();
cout<<AdjList[j].data<<" ";
++count;
for(p=AdjList[j].firstarc;p;p=p->next)
{
//求最早发生时间
k=p->adjvex;
if(!(--D[k])) S.push(k);
if(ve[j]+p->info>ve[k]) ve[k]=ve[j]+p->info;
}
}
if(count<vexnum)
return false;
else
return true;
}
void Graph::CriticalPath(){
cout<<endl;
int i,j,k,dut=0,ee,el;
j=ve[0];
for(i=1;i<vexnum;++i)
if(ve[i]>j)
j=ve[i];
for(i=0;i<vexnum;++i)
vl[i]=j;
while(!T.empty())
{
j=T.top();
T.pop();
for(p=AdjList[j].firstarc;p;p=p->next)
{
k=p->adjvex;
dut=p->info;
if(vl[k]-dut<vl[j])
//求最迟发生时间
vl[j]=vl[k]-dut;
}
}
for(j=0;j<vexnum;++j)
for(p=AdjList[j].firstarc;p;p=p->next)
{
k=p->adjvex;
dut=p->info;
//得到关键路径
ee=ve[j];
el=vl[k]-dut;
if(ee==el)
cout<<j<<" --> "<<k<<",["<<dut<<"],"<<ee<<","<<el<<" *."<<endl;
}
}
int main(){
Graph G;
if(G.TopologicalSort())
G.CriticalPath();
else
cout<<"\nTopolagical sort is fail.The Graph is loop."<<endl;
return 0;
}
/*Please input node numbers[<100] : 9
Node was initializated(For Example:A(0),B(1),C(2).....).
Input arcinfo(For Example:0 1 10),if stop input,input EOF:
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
4 6 9
4 7 7
3 5 2
5 7 4
6 8 2
7 8 4
^Z
Topolagical sort is: A B C E G D F H I
0 --> 1,[6],0,0 *.
1 --> 4,[1],6,6 *.
4 --> 7,[7],7,7 *.
4 --> 6,[9],7,7 *.
6 --> 8,[2],16,16 *.
7 --> 8,[4],14,14 *.
请按任意键继续. . .
*/
对的贴出来 ,早上起来后 改的！
2008-05-10 22:48
