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