|
|
| |
|
| |
| |
| 拓扑排序算法 |
|
[ 2008-9-16 19:44:00 | By: wantnon ] |
1,求G中各顶点入度;
入度为0者加入S;
如果S为空,有环,退出。
2,从S中任取一点输出到S';
更新各顶点入度;
入度为0者加入S;
如果S为空且G-S-S'不为空,有环,退出;
如果S为空且G-S-S'为空,排序完毕,终止;
返回2;
此时S'中所存即为拓扑排序结果。
注：
1，S'保存当前已摘掉的顶点。
2，S保存当前G-S'中无前驱顶点。
C++程序：
＃i nclude<iostream.h>
TopolSort(double vvmat[][MAXNL+1],int Nv)
{
int i,j;
int S_[MAXNL+1]={0};//保存已摘掉的顶点(终止时为所求结果)
int nS_=0;//S_的大小
int S[MAXNL+1]={0};//保存未摘掉的顶点中入度为0者
int nS=0;//S的大小
int indeg[MAXNL+1]={0};//各点剩余入度
//初始化indeg
for(i=1;i<=Nv;i++)//搜各顶点
{//求顶点i的入度
int sum=0;
for(j=1;j<=Nv;j++)//搜点i的邻接点
if(vvmat[j][i])sum++;
indeg[i]=sum;//得到顶点i的入度
if(indeg[i]==0)//如果入度为0,则加入到S
S[++nS]=i;
}//indeg初始完毕
if(nS==0)//如果S为空,说明根本不存在源
{
cout<<"错误:有环! 1"<<endl;
exit(1);
}
//循环
while(1)
{
//从S中任取一个顶点输出到S_
int ver=S[nS--];
S_[++nS_]=ver;
//更新indeg
for(i=1;i<=Nv;i++)//搜ver的邻接点
{
if(vvmat[ver][i])
{//如果i是ver的邻接点
indeg[i]--;
if(indeg[i]==0)//如果i的入度为0,则加进S
S[++nS]=i;
}
}
if(nS==0)
{
if(Nv-nS-nS_==0)
{
break;
}else
{
cout<<"错误:有环! 2"<<endl;
exit(1);
}
}
}
//输出结果
for(i=1;i<=Nv;i++)
cout<<S_[i]<<"→";
cout<<endl;
}
|
|
| | |
|
