#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;
}
為了驗證程序的正確性，故做以下測試：
輸入部分為：
輸出部分為：
其中前兩個數代表兩個頂點之間的通路，后兩個數分別代表最早開始時間和最遲開始時間 帶有*的通路組成關鍵路徑；
思考：在做這個的時候，我突然覺得拓撲排序和單元最短路好像有某種相似，究竟是不是這樣呢？希望網路上的朋友能幫我解答這個問題。多謝！