拓扑排序的三种方法 拓扑排序 c

拓扑排序

通常,这样的线性序列称为满足拓扑次序(TopologicalOrder)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义:

  若集合X上的关系是R是自反的、反对称的和传递的,则称R是集合X上的偏序关系。

  设R是集合X上的偏序(Partial Order),如果对每个x,y属于X必有xRy 或yRx,则称R是集合X上的全序关系。

  注意:

  ①若将图中顶点按拓扑次序排成一行,则图中所有的有向边均是从左指向右的。

  ②若图中存在有向环,则不可能使顶点满足拓扑次序。

  ③一个DAG的拓扑序列通常表示某种方案切实可行

本节说明了如何用深度优先搜索,对一个有向无回路图进行拓扑排序。有向无回路图又称为dag。对这种有向无回路图的拓扑排序的结果为该图所有顶点的一个线性序列,满足如果G包含(u,v),则在序列中u出现在v之前(如果图是有回路的就不可能存在这样的线性序列)。一个图的拓扑排序可以看成是图的所有顶点沿水平线排成的一个序列,使得所有的有向边均从左指向右。因此,拓扑排序不同于通常意义上对于线性表的排序。

有向无回路图经常用于说明事件发生的先后次序,图1给出一个实例说明早晨穿衣的过程。必须先穿某一衣物才能再穿其他衣物(如先穿袜子后穿鞋),也有一些衣物可以按任意次序穿戴(如袜子和短裤)。图1(a)所示的图中的有向边(u,v)表明衣服u必须先于衣服v穿戴。因此该图的拓扑排序给出了一个穿衣的顺序。每个顶点旁标的是发现时刻与完成时刻。图1(b)说明对该图进行拓扑排序后将沿水平线方向形成一个顶点序列,使得图中所有有向边均从左指向右。

下列简单算法可以对一个有向无回路图进行拓扑排序。

procedure Topological_Sort(G);begin 1.调用DFS(G)计算每个顶点的完成时间f[v]; 2.当每个顶点完成后,把它插入链表前端; 3.返回由顶点组成的链表;end;

图1(b)说明经拓扑排序的结点以与其完成时刻相反的顺序出现。因为深度优先搜索的运行时间为θ(V+E),每一个v中结点插入链表需占用的时间为θ(1),因此进行拓扑排序的运行时间θ(V+E)。

图1 早晨穿衣的过程

为了证明算法的正确性,我们运用了下面有关有向无回路图的重要引理。

引理1

有向图G无回路当且仅当对G进行深度优先搜索没有得到反向边。

证明:

→:假设有一条反向边(u,v),那么在深度优先森林中结点v必为结点u的祖先,因此G中从v到u必存在一通路,这一通路和边(u,v)构成一个回路。

←:假设G中包含一回路C,我们证明对G的深度优先搜索将产生一条反向边。设v是回路C中第一个被发现的结点且边(u,v)是C中的优先边,在时刻d[v]从v到u存在一条由白色结点组成的通路,根据白色路径定理可知在深度优先森林中结点u必是结点v的后裔,因而(u,v)是一条反向边。(证毕)

定理1

Topological_Sort(G)算法可产生有向无回路图G的拓扑排序。

证明:

假设对一已知有问无回路图G=(V,E)运行过程DFS以确定其结点的完成时刻。那么只要证明对任一对不同结点u,v∈V,若G中存在一条从u到v的有向边,则f[v]<f[u]即可。考虑过程DFS(G)所探寻的任何边(u,v),当探寻到该边时,结点v不可能为灰色,否则v将成为u的祖先,(u,v)将是一条反向边,和引理1矛盾。因此,v必定是白色或黑色结点。若v是白色,它就成为u的后裔,因此f[v]<f[u]。若v是黑色,同样f[v]<f[u]。这样一来对于图中任意边(u,v),都有f[v]<f[u],从而定理得证。(证毕)

另一种拓扑排序的算法基于以下思想:首先选择一个无前驱的顶点(即入度为0的顶点,图中至少应有一个这样的顶点,否则肯定存在回路),然后从图中移去该顶点以及由他发出的所有有向边,如果图中还存在无前驱的顶点,则重复上述操作,直到操作无法进行。如果图不为空,说明图中存在回路,无法进行拓扑排序;否则移出的顶点的顺序就是对该图的一个拓扑排序。

下面是该算法的具体实现:

procedure Topological_Sort_II(G);begin  1  for 每个顶点u∈V[G] do d[u]←0;  //初始化d[u],d[u]用来记录顶点u的入度2  for 每个顶点u∈V[G] do3    for 每个顶点v∈Adj[u] do d[v]←d[v]+1;  //统计每个顶点的入度4  CreateStack(s);  //建立一个堆栈s5  for 每个顶点u∈V[G] do    6    if d[u]=0 then push(u,s);  //将度为0的顶点压入堆栈7  count←0;     8  while (not Empty(s)) do     begin9      u←top(s);  //取出栈顶元素10     pop(s);     //弹出一个栈顶元素11     count←count+1;12     R[count]←u;   //线性表R用来记录拓扑排序的结果13     for 每个顶点v∈Adj[u] do //对于每个和u相邻的节点v             begin14                 d[v]←d[v]-1;15                 if d[v]=0 then push(v,s);  //如果出现入度为0的顶点将其压入栈                 end;                         end;         16 if count<>G.size then writeln('Error! The graph has cycle.')17                  else 按次序输出R;end;

上面的算法中利用d[u]来记录顶点u的入度,第2-3行用来统计所有顶点的入度,第5-6行将入度为0的顶点压入堆栈,第8-15行不断地从栈顶取出顶点,将该顶点输出到拓扑序列中,并将所有与该顶点相邻的顶点的入度减1,如果某个顶点的入度减至0,则压入堆栈,重复该过程直到堆栈空了为止。显而易见该算法的复杂度为O(VE),因为第2-3行的复杂性就是O(VE),后面8-15行的复杂性也是O(VE)。这个算法虽然简单,但是没有前面一个算法的效率高。

//=========================================================================================

PKU 1094 题目大意: 题目给定两个数字n(2<=n<=26)代表字母表里的前n个大写字母,m代表有m个关于前n个字母的偏序,
问是否能确定这n个大写字母的一个全序关系。
若能确定,输出:Sorted sequence determined after xxx relations:yyy...y.
不能确定,输出:Sorted sequence cannot be determined.
出现矛盾,输出:Inconsistency found after xxx relations.
注:xxx代表一共用了几个偏序关系,yyy代表全序关系。 拓扑排序是有向图的一个重要操作。在给定的有向图G中,若顶点序列vi1,vi2,...,vin
满足下列条件:若在有向图G中从顶点vi到顶点vj有一条路径,则在序列中顶点vi必在顶点vj
之前,便称这个序列为一个拓扑序列。算法思想:
首先选择一个无前驱的顶点(即入度为0的顶点,图中至少应有一个这样的顶点,否则肯定
存在回路),然后从图中移去该顶点以及由他发出的所有有向边,如果图中还存在无前驱的顶点,
则重复上述操作,直到操作无法进行。如果图不为空,说明图中存在回路,无法进行拓扑排序;
否则移出的顶点的顺序就是对该图的一个拓扑排序。
注意点:
1、排序结果唯一输出时还有一个句点
2、一旦得出唯一的序列或是矛盾就可以忽略后面的输入
拓扑排序的三种方法 拓扑排序 c

#include <iostream>
#include <list>
#include <stack>
using namespace std;list<int>lst;//无前趋的顶点优先的拓扑排序方法
int TopologicalSort( int c1[][30], int into1[], int n)//拓扑排序返回 (-1排序不唯一, 0有环, 1排序唯一) 
{
int i, j;
int a[30][30],into[30];for(i=1; i<=n;i++) //复制当前偏序矩阵和各点入度记录
{
for(j=1; j<=n; j++)
a[i][j] = c1[i][j];
into[i] = into1[i];
}stack<int>stk;
for (i = 1; i<= n; i++) //无前趋的顶点入栈
if(into[i]==0)
stk.push(i);

int count = stk.size();
if(count == 0)
return -1;

lst.clear();
while(!stk.empty())//不断删除无前趋的顶点及其指出的边
{
int u = stk.top(); stk.pop(); lst.push_back(u); //线性表R用来记录拓扑排序的结果 for(i=1; i<=n; i++) //对于每个和u相邻的节点i
{
if(a[u][i] >0)
{
//a[u][i]--; WA3 在此处
into[i]--;
if(into[i]== 0)//如果出现入度为0的顶点将其压入栈
stk.push(i);
}
}
if(stk.size() > count)//WA2 删除点之后如果出现多于一个的无前趋点,则要更新count
count = stk.size();
}for(i=1; i<=n; i++)
if(into[i] != 0)
return 0; //有环

if(count ==1) //排序唯一
return 1;

if(count >1) //排序不唯一
return -1;
}int main()
{
int i,j,n,m;
while(scanf("%d%d",&n,&m)&& !(m==0&& n==0))
{
getchar();

int c[30][30], into[30];
memset(c,0,sizeof(c));
memset(into, 0, sizeof(into)); for(i=1; i<=m;i++) //WA1 边读入边检测
{
char a,b;
scanf("%c%*c%c",&a,&b);getchar();
int x = a-65+1;
int y = b-65+1;
if(c[x][y] == 0)
{
c[x][y] =1;
into[y]++;
}


if(TopologicalSort(c, into, n)== 0) //有环
{
printf("Inconsistency found after %d relations.n", i);
for( i=i+1;i<=m; i++) //忽略后面的输入
{
scanf("%c%*c%c",&a,&b);
getchar();
}
break;
}

if(TopologicalSort(c, into, n)== 1) //可以拓扑唯一排序则输出结果
{
printf("Sorted sequence determined after %d relations: ", i);
while(!lst.empty())
{
printf("%c", lst.front()+64);
lst.pop_front();
}
printf(".n"); //注意有个句点 for(i=i+1; i<=m; i++) //忽略后面的输入
{
scanf("%c%*c%c",&a,&b);
getchar();
}
break;
}

if(i==m&& TopologicalSort(c, into, n)==-1) //最后一次判断排序不唯一
puts("Sortedsequence cannot be determined.");
}

//cout<<TopologicalSort(c, into,n)<<endl;
}
}

  

爱华网本文地址 » http://www.413yy.cn/a/25101011/84852.html

更多阅读

教你如何禁用U盘、屏蔽USB端口的三种方法 游戏端口被屏蔽

在企业里面,有时候我们处于电脑自身安全、商业机密保护的需要,常常要禁用电脑USB接口,尤其是禁用带有USB存储功能的设备,如U盘、移动硬盘和手机存储卡等,但同时又不能完全屏蔽USB接口的使用,因为现在很多的鼠标和键盘都是USB端口。这种情

怎样办理手机号实名登记的三种方法 台胞证手机号实名登记

怎样办理手机号实名登记的三种方法——简介虽然手机号实名制已经开始了好久,手机实名也在全国范围内实施,新入网用户,现在得必须提供并登记真实身份信息,而现在还是有很多没有实名登记的老用户,有些朋友就会觉得去营业厅办理挺麻烦的,或者

XP、win7系统锁定计算机的三种方法 xp系统怎么锁定屏幕

XP、win7系统锁定计算机的三种方法——简介当我们需要暂时离开一下而又不想关电脑时,为了确保电脑的安全,最好是锁定计算机,避免资料泄露等危害,下面就让小编介绍三种锁定计算机的方法。XP、win7系统锁定计算机的三种方法——工具/原料

常用缓解压力的三种方法 精 压力缓解

现在社会生活节奏加快,人们受到一些挫折以后,基本上没有什么修养缓和的时间,只能睡一觉然后投入到明天的工作中。这样的生活持续下去,压力就会慢慢的积累,那些本来微小的压力积累起来就会造成严重的问题。很多时候,人们都是被一棵稻草压倒

声明:《拓扑排序的三种方法 拓扑排序 c》为网友仰面清风分享!如侵犯到您的合法权益请联系我们删除