首页 > 代码库 > 拓扑排序之变量序列算法分析
拓扑排序之变量序列算法分析
拓扑排序之变量序列
巧若拙（欢迎转载，但请注明出处：http://blog.csdn.net/qiaoruozhuo）
题目描述：
假设有n个变量（1<=n<=26，变量名用单个小写字母表示），还有m个二元组（u,v），分别表示变量u小于v。那么，所有变量从小到大排列起来应该是什么样子的呢？
例如有4个变量a,b,c,d，若以知a<b,c<b,d<c，则这4个变量的排序可能是a<d<c<b。尽管还有可能其他的可能，你只需找出其中的一个即可。
输入：
输入为一个字符串，其中包含N+N个字符，依次表示N个关系式（1<=N<=100000），例如序列"abcbdc"表示a<b,c<b,d<c.
输出：
给出一个字符串，其中存储了一个符合要求的变量序列，例如，字符串"adcb"表示a<d<c<b。
算法分析：
这是典型的拓扑排序问题。先简单科普一下，所谓拓扑排序，是指将一个有向无环图G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<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<MAXM; i++)//初始化图
{
GL[i].data = http://www.mamicode.com/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<MAXM; 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<MAXM; i++)//将入度为0的顶点入栈
{
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<MAXM; i++)//将入度为0的顶点入栈
{
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<MAXM; 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<MAXM; 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<MAXM; i++)//将入度为0的顶点入栈
{
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小于顶点数，说明存在环
}
这里只给出了相关函数，完整的测试代码请到巧若拙的博客（http://blog.csdn.net/qiaoruozhuo）查看。
拓扑排序之变量序列算法分析