文章详情

  • 游戏榜单
  • 软件榜单
关闭导航
热搜榜
热门下载
热门标签
php爱好者> php文档>疑问版的拓扑排序

疑问版的拓扑排序

时间: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;
}

相关阅读 更多 +
排行榜 更多 +
枪战大乱斗2

枪战大乱斗2

飞行射击 下载
猎鸭挑战安卓版

猎鸭挑战安卓版

飞行射击 下载
空军

空军

飞行射击 下载