疑问版的拓扑排序
时间:2010-12-02 来源:microsoftmvp
#include "CQueue.h"
#include<iostream>
using namespace std;
struct node
{
node(int i,node* n)
{
item=i;
next=n;
}
int item;
node* next;
};
typedef node* PNode;
int main()
{
CQueue q(200);//队列大小为200
int Counter=0;
int i;
int v;
int w;
int NumVertex;//点的数目
cout<<"您要处理的图有多少个点"<<endl;
cin>>NumVertex;
if(NumVertex<=0)
return 0;
PNode *p=new PNode[NumVertex];
int *Indegree=new int[NumVertex];
int *TopNum=new int[NumVertex];
memset(TopNum,0,sizeof(TopNum));
//初始化入度
memset(Indegree,0,sizeof(Indegree));
//初始邻接表指针
memset(p,0,sizeof(p));
cout<<"请输入您的边,以v-w形式,中间用空格隔开"<<endl;
cout<<"输入-1 -1结束输入"<<endl;
do
{
cin>>v>>w;
if(v==-1&&w==-1)break;
if(v<0||w<0||v>=NumVertex||w>=NumVertex)
{
cout<<"输入有误!"<<endl;
}
else
{
p[v]=new node(w,p[v]);
Indegree[w]++;
}
}while(1);
for(i=0;i<NumVertex;i++)
{
if(!Indegree[i])
{
q.Enqueue(Indegree[i]);
}
}
while(!q.IsEmpty())
{
v=q.Dequeue();
TopNum[v]=++Counter;
node* temp=p[v];
while(temp)
{
w=temp->item;
if(--Indegree[w]==0)
{
q.Enqueue(w);
}
temp=temp->next;
}
}
if(Counter!=NumVertex)
{
cout<<"输入的图有环!!!"<<endl;
return 0;
}
//输出拓扑序列
for(i=0;i<NumVertex;i++)
{
cout<<TopNum[i]<<" ";
}
//回收内存
//回收邻接表对应内存的代码略显复杂
delete []Indegree;
delete []TopNum;
return 0;
}