#include<iostream>
#include<cmath>
#include<algorithm>
#include<stack>
#include<fstream>
using namespace std;
#define MAX 100000
struct node
{
int v;
int w;
node *next;
};
node adj[MAX];
node reversed_adj[MAX];
int indegree[MAX];
int ve[MAX];
int vl[MAX];
void initial(int n)
{
int i;
for(i=1;i<=n;i++)
{
adj[i].v=i;
adj[i].w=-1;
reversed_adj[i].v=i;
reversed_adj[i].w=-1;
adj[i].next=NULL;
reversed_adj[i].next=NULL;
}
}
void findindegree(node adj[],int n)
{
int i;
for(i=1;i<=n;i++)
indegree[i]=0;
for(i=1;i<=n;i++)
{
node *p=adj[i].next;
while(p!=NULL)
{
indegree[p->v]++;
p=p->next;
}
}
}
void creat(node adj[],node reversed_adj[],int n)
{
fstream file("test.txt");
int i;
cout<<"您将建立一个具有"<<n<<"个顶点的邻接表,请依次输入边和权值，并以0 0 0结束"<<endl;
for(i=1;;i++)
{
int a,b,c;
printf("请输入第%d条边以及权值(u v w):",i);
file>>a>>b>>c;
cout<<endl;
if(a==0&&b==0&&c==0)
break;
node *p;
node *q;
/**//////////////////////
p=&adj[a];
q=new node;
q->v=b;
q->w=c;
q->next=p->next;
p->next=q;
/**/////////////////////
p=&reversed_adj[b];
q=new node;
q->v=a;
q->w=c;
q->next=p->next;
p->next=q;
/**////////////////////
}
}
void topsort(node adj[],int n,int v[],int x)
{
int i;
node *p;
stack<int>mystack;
while(!mystack.empty())
mystack.pop();
findindegree(adj,n);
for(i=1;i<=n;i++)
v[i]=x;
for(i=1;i<=n;i++)
{
if(indegree[i]==0)
{
mystack.push(i);
}
}
/**/////////////////////////////
while(mystack.size()!=0)
{
i=mystack.top();
mystack.pop();
for(p=adj[i].next;p!=NULL;p=p->next)
{
indegree[p->v]--;
if(indegree[p->v]==0)
mystack.push(p->v);
if(x==0)
{
if(v[i]+p->w > v[p->v])
{
v[p->v]=v[i]+p->w;
}
}
else
{
if(v[i]-p->w < v[p->v])
v[p->v]=v[i]-p->w;
}
}
}
}
void printedg(node adj[],int n,int ve[],int vl[])
{
int i;
node *p;
int k;
int e;
int l;
for(i=1;i<=n;i++)
{
p=adj[i].next;
while(p!=NULL)
{
k=p->v;
e=ve[i];
l=vl[k]-p->w;
cout<<i<<' '<<k<<' '<<e<<' '<<l;
if(e==l) cout<<"*";
cout<<endl;
p=p->next;
}//while
}//for
}
int main ()
{
int n;
cout<<"请输入顶点数n:";
cin>>n;
initial(n);
creat(adj,reversed_adj,n);//建立邻接表和逆邻接表
topsort(adj,n,ve,0);
topsort(reversed_adj,n,vl,ve[n]);
printedg(adj,n,ve,vl);
system("pause");
return 0;
}
为了验证程序的正确性，故做以下测试：
输入部分为：
输出部分为：
其中前两个数代表两个顶点之间的通路，后两个数分别代表最早开始时间和最迟开始时间 带有*的通路组成关键路径；
思考：在做这个的时候，我突然觉得拓扑排序和单元最短路好像有某种相似，究竟是不是这样呢？希望网路上的朋友能帮我解答这个问题。多谢！