加载中…
个人资料
_陌上花开7_
_陌上花开7_
  • 博客等级:
  • 博客积分:0
  • 博客访问:68,244
  • 关注人气:29
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

拓扑排序算法(toposort)

(2013-08-15 22:40:49)
标签:

拓扑

排序

aov

it

分类: 数据结构

拓扑排序算法(toposort)

首先来说图的邻接表存法:

顶点表结点:vertex + firstedge

边表结点:adjvex + next

其中:vertex为数据域,存放顶点信息

      firstedge为指针域,指向边表中第一个结点;

      adjvex为邻接点域,存放该节点的邻接点在顶点表中的下标

      next为指针域,指向边表中的下一个结点

用C++实现:

struct ArcNode                   //定义边表结点
{
 int adjvex;                 //邻接点域
 ArcNode *next;
};

struct VertexNode                 //定义定点表
{
 int vertext;
 ArcNode *firstedge;
};

在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,称这样的有向图为顶点表示活动的网,简称AOV网(activity on vertex network)

设G=(V,E)是一个有向图,V中的顶点序列v0,v1,…,vn-1称为一个拓扑序列(topologicl order),当且仅当满足下列条件:若从顶点Vi到Vj有一条路径,则在顶点序列中顶点Vi和Vj之前。对一个有向图构造拓扑序列的过程称为拓扑序列(topological sort)。

整个算法的时间复杂度为O(n+e)  n个顶点,e条弧

算法的伪代码:

1.栈S初始化,累加器count初始化;

2.扫描顶点表,将没有前驱(即入度为0)的顶点压栈;

3.当栈S非空时循环

  3.1  j=栈顶元素出栈,输出顶点j;count++;

  3.2 对顶底j的每一邻接点k执行下述操作:

      3.2.1  将顶点k的入度减1;

      3.2.2  如果顶点k的入度为0,则将顶点k入栈;

4.if(count

 

举个例子:

拓扑排序算法(toposort)


拓扑排序算法(toposort)

拓扑排序算法(toposort)

拓扑排序算法(toposort)

拓扑排序算法(toposort)

拓扑排序算法(toposort)


 

上述过程的具体C++实现:


头文件ALGraph.h

//----------------------------------------------------//

//---------------求出一个拓扑排序序列-----------------//

#ifndef ALGRAPH_H
#define ALGRAPH_H_
const int MaxSize=10;             //图中最大的顶点数
struct ArcNode                   //定义边表结点
{
 int adjvex;                 //邻接点域
 ArcNode *next;
};

struct VertexNode                 //定义定点表
{
 int vertext;
 ArcNode *firstedge;
 int in;                  //入度的个数
};

class ALGraph
{
 public:
  ALGraph();                       //默认构造函数
  ALGraph(int a[],int n,int e);   //构造函数,建立一个有n个顶点e条边的图
  ~ALGraph();
  void TopSort(ALGraph G);              //核心算法
 private:
  VertexNode adjlist[MaxSize];       //存放顶点表的数组
  int vertexNum,arcNum;             //图的顶点数和边数
};

#endif


 

ALGraph.cpp源文件内容
#include<iostream>
#include"ALGraph.h"
#include<stack>

using namespace std;
ALGraph::ALGraph()
{
 for ( int i=0;i
 {
  adjlist[i].vertext=0;
  adjlist[i].firstedge=NULL;
 }
  vertexNum=0;
  arcNum=0;
}

ALGraph::ALGraph(int a[],int n,int e)    //构造函数 
{
 vertexNum=n;
 arcNum=e;
 for ( int i=0;i<vertexNum;i++)

 {
  adjlist[i].vertext=a[i];
  adjlist[i].firstedge=NULL;
  adjlist[i].in=0;
 }
 

 for (int k=0;k<arcNum;k++)

 {
  int i,j;
  cout<<"输入 "<<k+1<<" 条边的顶点:"<<endl;
  cin>>i>>j;                                    //输入边所依附的两个顶点的编号
  adjlist[j].in++;
  ArcNode *s=new ArcNode;                      
  s->adjvex=j;                                   //生成一个边表结点s
  s->next=adjlist[i].firstedge;               //将节点s插入到第i个边表的表头,即插到前

                                               //一个插入数据的前面
  adjlist[i].firstedge=s;                      
 }
}

ALGraph::~ALGraph()
{
 
}
void ALGraph::TopSort(ALGraph G)
{

 
 int count=0;

 stack<int> S;

 for(int i=0;i<G.vertexNum;i++)
  if(G.adjlist[i].in==0)
   S.push(i);
 
//   cout<<S.top();
//   S.pop();
//  
//   cout<<S.top();
//   S.pop();
  
  while(S.empty()==false)
  {
   int m=S.top();
   S.pop();
   std::cout<<G.adjlist[m].vertext<<"---";
   count++;
   ArcNode *p;
   p=G.adjlist[m].firstedge;
   while (p!=NULL)
   {
    int k=p->adjvex;
    G.adjlist[k].in--;
    if (G.adjlist[k].in==0)
     S.push(k);
     
    p=p->next;
    
   }
  }
  if(count<G.vertexNum)
   std::cout<<"有回路";
}

 

主函数topsort.cpp源文件

#include<iostream>
#include "ALGraph.h"


int main()
{
 //初始化
 int b[MaxSize];
 for(int i=0;i
 {
  b[i]=i;
 }

 ALGraph G(b,6,9);
 G.TopSort(G);
 
 return 0;
}

运行结果

拓扑排序算法(toposort)

现在出现的问题,按图中的分析结果应该是4---2---1---3---5---0---

结果为啥会出现不一样呢?

经分析发现,这个结果也是一种拓扑排序,出现这种结果的原因时我们在输入顶点信息的顺序,我们在输入D到A和D到F的过程中,我们先输入的是D到A的即3到0的,后输入的是D到F的即3到5的,由于我们的构造函数时节点s插入到第i个边表的表头,即插到前一个插入数据的前面,也就说明了离源节点D最近的是后来输入的F而不是先输入的A,这样,存入栈的时候就先存的是F后存的是A,这样在出栈是A就先出栈,而F后出栈了

经测试确实是这样:

拓扑排序算法(toposort)




0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有