频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
拓扑排序之变量序列算法分析
2014-11-18 11:45:39           
收藏   我要投稿

拓扑排序之变量序列

巧若拙(欢迎转载,但请注明出处:https://blog.csdn.net/qiaoruozhuo)

题目描述:

假设有n个变量(1<=n<=26,变量名用单个小写字母表示),还有m个二元组(u,v),分别表示变量u小于v。那么,所有变量从小到大排列起来应该是什么样子的呢?

例如有4个变量a,b,c,d,若以知a

输入:

输入为一个字符串,其中包含N+N个字符,依次表示N个关系式(1<=N<=100000),例如序列"abcbdc"表示a

输出:

给出一个字符串,其中存储了一个符合要求的变量序列,例如,字符串"adcb"表示a

算法分析:

这是典型的拓扑排序问题。先简单科普一下,所谓拓扑排序,是指将一个有向无环图G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若 ∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(TopoiSicaiOrder)的序列,简称拓扑序列。

我们先将变量作为顶点输入到图数据结构中。表示图的数据结构有多种,由于本题对应的是稀疏图,应该以边为主要研究对象,所以可以把数据结构设置为邻接表或边表集。

我们先来看邻接表数据结构:

typedef char VertexType; //顶点类型由用户自定义

typedef int EdgeType; //边上的权值类型由用户自定义

typedef struct EdgeNode{ //边表结点

intadjvex; //邻接点域,存储该顶点对应的下标

// EdgeTypeweight; //权值,对于非网图可以不需要

structEdgeNode *next; //链域,指向下一个邻接点

} EdgeNode;

typedef struct VertexNode{ //顶点表结点

VertexTypedata; //顶点域,存储顶点信息

intin; //存储顶点入度的数量

EdgeNode*firstEdge; //边表头指针

} VertexNode;

由于变量名用单个小写字母表示,我们可以设置一个大小为26的数组存储顶点;又由于26个字母不见得都会出现,故我们设置一个全局变量int book[MAXM]= {0}; 用来标记某字母是否出现。

首先创建一个图,读入顶点和边信息。代码如下:

/*

函数名称:CreateGraph

函数功能:把顶点和边信息读入到表示图的邻接表中

输入变量:char *data:存储了N个关系式的字符串

VertexNode *GL : 顶点表数组

输出变量:表示图的顶点表数组

返回值:int :顶点数量

*/

intCreateGraph(char *data, VertexNode *GL)

{

int i, u, v;

int count = 0;//记录顶点数量

EdgeNode *e;

for (i=0; i

{

GL[i].data = i + 'a';

GL[i].in = 0;

GL[i].firstEdge = NULL;

book[i] = 0;

}

for (i=0; data[i]!='\0'; i+=2)//每次读取两个变量

{

u = data[i] - 'a'; //字母转换为数字,'a'对应0,'b'对应1,以此类推

v = data[i+1] - 'a';

book[u] = book[v] = 1;

e =(EdgeNode*)malloc(sizeof(EdgeNode)); //采用头插法插入边表结点

if (!e)

{

puts("Error");

exit(1);

}

e->adjvex = v;

e->next = GL[u].firstEdge;

GL[u].firstEdge = e;

GL[v].in++;

}

for (i=0; i

{

if (book[i] != 0)

count++;

}

return count;

}

拓扑排序算法其实非常简单,只需要搜索入度为0的弧尾顶点,然后将其对应的弧头顶点入度减1,如果该弧头顶点入度也变成了0,就将其存储到栈(或队列)中。搜索的方法有深度优先和广度优先两种。代码分别如下:

/*

函数名称:TopoLogicalSort_DFS

函数功能:拓扑排序,采用深度优先搜索获取拓扑序列

输入变量:char *topo:用来存储拓扑序列的字符串

VertexNode *GL : 顶点表数组

int n:顶点个数

输出变量:用来存储拓扑序列的字符串

返回值:int :拓扑排序成功返回真,若存在环则返回假

*/

int TopoLogicalSort_DFS(char *topo,VertexNode *GL, int n)

{

inti, u, v, top;

intcount = 0; //用于统计输出顶点的个数

EdgeNode*e;

intStack[MAXM];

for(top=i=0; i

{

if(book[i] != 0 && GL[i].in == 0)

{

Stack[top++]= i;

}

}

while(top > 0)//采用深度优先搜索获取拓扑序列

{

u= Stack[--top];

topo[count++]= u + 'a';

for(e=GL[u].firstEdge; e!=NULL; e=e->next)//将u的邻接点入度减1,并将入度为0的顶点入栈

{

v= e->adjvex;

if(--GL[v].in == 0)

Stack[top++]= v;

}

}

topo[count]= '\0';

return(count == n);//如果count小于顶点数,说明存在环

}

/*

函数名称:TopoLogicalSort_BFS

函数功能:拓扑排序,采用广度优先搜索获取拓扑序列

输入变量:char*topo:用来存储拓扑序列的字符串

VertexNode *GL : 顶点表数组

int n:顶点个数

输出变量:用来存储拓扑序列的字符串

返回值:int :拓扑排序成功返回真,若存在环则返回假

*/

int TopoLogicalSort_BFS(char *topo,VertexNode *GL, int n)

{

inti, u, v, front, rear;

EdgeNode*e;

front= rear = 0;

for(i=0; i

{

if(book[i] != 0 && GL[i].in == 0)

{

topo[rear++]= i + 'a';

}

}

while(front < rear)//采用广度优先搜索获取拓扑序列

{

u= topo[front++] - 'a';

for(e=GL[u].firstEdge; e!=NULL; e=e->next)//将u的邻接点入度减1,并将入度为0的顶点入栈

{

v= e->adjvex;

if(--GL[v].in == 0)

topo[rear++]= v + 'a';

}

}

topo[rear]= '\0';

return(rear == n);//如果count小于顶点数,说明存在环

}

我们也可以用边表集来表示图,数据结构如下:

typedef struct Edge{ //边集数组

intu, v; //弧尾和弧头

intnext; //指向同一个弧尾的下一条边

// EdgeTypeweight; //权值,对于非网图可以不需要

} EdgeLib;

为了表示顶点信息,我们还需要设置两个数组:int In[MAXM], first[MAXM]; //分别存储顶点的入度和第一条边信息。

边表集实现拓扑排序的算法和邻接表非常相似,也是先读入图的顶点和边信息,然后进行拓扑排序。代码如下:

/*

函数名称:CreateGraph_2

函数功能:把顶点和边信息读入到表示图的边表集中

输入变量:char*data:存储了N个关系式的字符串

int In[]:存储了顶点的入度信息

int first[]:指向以该顶点为弧尾的第一条边

EdgeLib edge[]:存储了边信息的边表集

输出变量:表示图的边表集数组

返回值:int :顶点数量

*/

int CreateGraph_2(char *data, int In[], intfirst[], EdgeLib edge[])//创建一个图

{

inti, j;

intcount = 0;//记录顶点数量

for(i=0; i

{

first[i]= -1;

book[i]= 0;

In[i]= 0;

}

for(j=i=0; data[i]!='\0'; i+=2,j++)//每次读取两个变量

{

edge[j].u= data[i] - 'a'; //字母转换为数字,'a'对应0,'b'对应1,以此类推

edge[j].v= data[i+1] - 'a';

book[edge[j].u]= book[edge[j].v] = 1;

edge[j].next= first[edge[j].u];

first[edge[j].u]= j;

In[edge[j].v]++;

}

for(i=0; i

{

if(book[i] != 0)

count++;

}

returncount;

}

/*

函数名称:TopoLogicalSort

函数功能:拓扑排序,采用广度优先搜索获取拓扑序列

输入变量:char*topo:用来存储拓扑序列的字符串

EdgeLib edge[]:存储了边信息的边表集

int In[]:存储了顶点的入度信息

int first[]:指向以该顶点为弧尾的第一条边

int n:顶点个数

输出变量:用来存储拓扑序列的字符串

返回值:int :拓扑排序成功返回真,若存在环则返回假

*/

int TopoLogicalSort(char *topo, EdgeLibedge[], int In[], int first[], int n)

{

inti, u, front, rear;

front= rear = 0;

for(i=0; i

{

if(book[i] != 0 && In[i] == 0)

{

topo[rear++]= i + 'a';

}

}

while(front < rear)//采用广度优先搜索获取拓扑序列

{

u= topo[front++] - 'a';

for(i=first[u]; i!=-1; i=edge[i].next)

{

if(--In[edge[i].v] == 0)

topo[rear++]= edge[i].v + 'a';

}

}

topo[rear]= '\0';

return(rear == n);//如果count小于顶点数,说明存在环

}

这里只给出了相关函数,完整的测试代码请到巧若拙的博客(https://blog.csdn.net/qiaoruozhuo)查看。

点击复制链接 与好友分享!回本站首页
上一篇:柜位预测(一)——显示柜位曲线图
下一篇:算法重拾之路——快速排序
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站